K-Clique in Connected Graphs

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?

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

• In bounded tree-width graphs is not $n^t$, it's $O(t^t n)$. – user742 Dec 14 '12 at 20:46
• @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)$. – 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.

• 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$:en.wikipedia.org/wiki/Parameterized_complexity#W.5B1.5D. – user742 Dec 14 '12 at 10:17
• @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. – usul Dec 14 '12 at 16:22
• 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? – Paul Manta Dec 14 '12 at 17:35
• 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! – usul Dec 14 '12 at 17:58