3
$\begingroup$

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

$\endgroup$
6
  • 3
    $\begingroup$ A graph in which each pair of vertices is connected is called a clique. Quite a lot of clique problems are NP-hard. $\endgroup$
    – Jakube
    Aug 8, 2018 at 7:55
  • 1
    $\begingroup$ 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, ... $\endgroup$
    – Jakube
    Aug 8, 2018 at 7:57
  • $\begingroup$ To have as small number of cliques as possible. $\endgroup$ Aug 8, 2018 at 8:49
  • 1
    $\begingroup$ @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. $\endgroup$
    – Jakube
    Aug 8, 2018 at 9:36
  • 1
    $\begingroup$ And otherwise there is the trivial solution of take no subgraph at all. $\endgroup$
    – Jakube
    Aug 8, 2018 at 10:08

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.