# 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).

• A graph in which each pair of vertices is connected is called a clique. Quite a lot of clique problems are NP-hard. – Jakube Aug 8 '18 at 7:55
• Are there any other conditions on the subgraphs? With the current specifications you could just use every vertex as a trivial subgraph. Or greedily choose pairs of connected vertices as graphs, ... – Jakube Aug 8 '18 at 7:57
• To have as small number of cliques as possible. – Karel Macek Aug 8 '18 at 8:49
• @KarelMacek Does each point have to be part of a subgraph, i.e. should the subgraphs form a partition? If this is the case, I'm pretty sure that there are no polynomial algorithms. Not without any more restrictions or special types of graphs. – Jakube Aug 8 '18 at 9:36
• And otherwise there is the trivial solution of take no subgraph at all. – Jakube Aug 8 '18 at 10:08

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.

There is no polynomial algorithm for the problem you mentioned (assuming $P\neq NP$).

You can use an algorithm for the problem you mentioned to compute the chromatic number of a given graph $G=(V,E)$.

Here is how: On input $G=(V,E)$, take the compliment graph $\overline{G}=(V,\overline{E})$ (where $\overline{E}$ is the compliment of $E$), so a partition of $\overline{G}$ into $k$ subgraphs is equivalent to $k$-coloring of $G$:

Given "super strongly connected" partition of $\overline{G}$ into $k$ subgraphs, you can color the vertices of each subgraph with a different color and get $k$-coloring of $G$.

In the other direction, given a $k$-coloring of $G$, you can partition $\overline{G}$ according to the colors ($\overline{G}_i$ would be the subgraph containing all vertices which are colored with the $i$th color) and get a "super strongly connected" partition of $\overline{G}$ into $k$ subgraphs.