Super-strongly connected components?

I face a problem that is related to (strongly) connected components. Let $G=(V,E)$ be an undirected graph.

I want to find subgraphs $G_1,G_2, \dots,G_n$ of $G$ such that

• they do not overlap (i.e. don't share any nodes)

• each two nodes in a subgraph are connected by an edge, i.e. $\forall i \forall n,m\in V_i$ then $\{m,n\}\in E_i$ where $G_i=(V_i,E_i)$.

My question is: How to solve this problem? Is there any specific name of this problem?

Edit: The graph I am dealing with is very sparse. Coloring based approximations may not work as the complement graph would be huge (not able to store it in memory).

This is called the Minimal Clique Cover Problem, and is NP-hard: as a matter of fact, the decision version ("can I do it with only $k$ subgraphs?") is one of Karp's original 21 Problems, the ones that first defined NP-completeness.

Since it's linked to graph coloring, you can't even get a good approximation in polynomial time, unfortunately: everything about this problem is hard.

For further reading, your "super-strongly connected components" are generally called cliques, and a clique cover is a way to "cover" the entire graph with non-overlapping cliques. A minimal clique cover uses the smallest possible number of cliques to do it.

StackExchange Computer Science Q#96070, answer score: 4