K-Clique in Connected Graphs

Question

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?

Answer 1

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.

Answer 2

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.