A question about the clique problem (specifically k-clique). Is there any algorithm that takes advantage of the properties of connected graphs to find cliques of a given size k, if such cliques exist?

  • $\begingroup$ Is a graph without an island a connected graph? $\endgroup$ – Merbs Dec 14 '12 at 1:04
  • $\begingroup$ @Merbs Yes, I edited the question. $\endgroup$ – Paul Manta Dec 14 '12 at 6:22
  • $\begingroup$ Does this Wikipedia subsection on cliques of fixed size answer your question? $\endgroup$ – Merbs Dec 14 '12 at 6:33
  • $\begingroup$ @Merbs Not really, but I suppose you mean to say that there's nothing about connected graphs that makes this problem easier? $\endgroup$ – Paul Manta Dec 14 '12 at 6:48

As pointed out in the previous answer, you cannot do very well if you simply assume that your input is a connected graph. However, you can do better if you make certain assumptions on your graph's structure. That is, one can ask: given a class of graphs $\mathcal G$, will the clique problem be solvable in polynomial time, assuming that all inputs are contained in $\mathcal G$?

The answer turns out to be positive for a nice class (or should I say classes) of graphs: graphs whose treewidth is bounded by a constant.

Without getting into too much detail (see http://en.wikipedia.org/wiki/Tree_decomposition for more details), the tree-width of a graph is a measure of how much it "resembles" a tree. Trees have a treewidth of 1, whereas cliques have a treewidth of $n-1$ (where $n$ is the number of vertices).

The clique problem is $\mathcal O(t^t n)$ on graphs whose treewidth is at most $t$.

Treewidth is believed to be the "right" measure for graphs problems (although more complex measures do exist): Courcelle's Theorem (see http://en.wikipedia.org/wiki/Courcelle's_theorem) states that any graph property that can be succinctly expressed via some logical parameters can be solved in polynomial time on graphs with treewidth bounded by a constant. This includes vertex cover, clique, independent set, and many others.

This means that many NP-hard graph problems are fixed parameter tractable, with treewidth being the parameter.

Hope this helps.

| cite | improve this answer | |
  • $\begingroup$ In bounded tree-width graphs is not $n^t$, it's $O(t^t n)$. $\endgroup$ – user742 Dec 14 '12 at 20:46
  • $\begingroup$ @SaeedAmiri, yes, you're of course correct. I'll correct it. However, it should be mentioned that deciding whether a graph has treewidth of $t$ is $\mathcal O(n^t)$. $\endgroup$ – Spark Dec 15 '12 at 9:48

This seems like a fair/good question to me, but I think the answer must be negative. Here's my argument.

Suppose you had an algorithm $A$ for solving CLIQUE on connected graphs (somehow taking advantage of the connectivity property). Then I can construct an algorithm $B$ for solving CLIQUE on general graphs that is essentially no slower than $A$. I'll just find the connected components of the graph in linear time, then call $A$ on each connected component. The running time will be linear in the input plus the time of all the calls I make to $A$. In particular, if my input happens to be a connected graph already, then my general algorithm $B$ runs in time $O(|V| + |E| + Time(A))$.

This argument tells us two things. First, the best possible algorithm $A$ for your problem gets no more than an additive linear speedup over the best possible algorithm $B$ for CLIQUE applied to your problem, so we've bounded the "advantage" of knowing the input is connected to at most additive linear. Second, your problem is NP-hard because we can reduce CLIQUE in polynomial time to a polynomial number of calls to your problem. This unfortunately means that additive linear speedup is probably not much of an advantage in the scheme of things.

Edit - This only referred to CLIQUE and not $k$-CLIQUE (where we fix $k$ and only let the input vary with the size of the graph). The answer depends slightly on $k$ because for e.g. $k=2$ the connected-graph algorithm runs in constant time (the answer is yes). However, the answer is largely the same -- for moderately large values of $k$, your running time of algorithm $A$ will be $O(g(k)(|V|+|E|))$ for some very large constant $g(k)$ (unless P\poly=NP); and then it doesn't matter much if algorithm $B$ loses another $|V|+|E|$ for scanning the input first.

| cite | improve this answer | |
  • $\begingroup$ if there is an algorithm with running time $O(f(k)n^{O(1)})$, it doesn't solves general clique problem, but it's good for fixed k, but $k$-clique belongs to $W[1]$:en.wikipedia.org/wiki/Parameterized_complexity#W.5B1.5D. $\endgroup$ – user742 Dec 14 '12 at 10:17
  • $\begingroup$ @Saeed Good point, my answer is only about clique and not $k$-clique. I think the general answer should be the same (a linear pass to identify connected components does not greatly affect the time complexity), but I'll edit my answer. $\endgroup$ – usul Dec 14 '12 at 16:22
  • 1
    $\begingroup$ Good point. Do you know, are there any (nontrivial) types of graphs for which the clique problem, where k is an input variable, can be solved in polynomial time? $\endgroup$ – Paul Manta Dec 14 '12 at 17:35
  • $\begingroup$ I don't know, but I'm not that well-versed in graph algorithms. I think that's a great question -- I'm very curious about the answer. Perhaps this is worth posting a separate question for? Intuitively, such a graph would have to rule out the things that make clique hard, which seems tough to do , so my gut guess would be there aren't any, but I don't know! $\endgroup$ – usul Dec 14 '12 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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