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$
$\endgroup$
4
-
$\begingroup$ Is a graph without an island a connected graph? $\endgroup$– MerbsDec 14, 2012 at 1:04
-
$\begingroup$ @Merbs Yes, I edited the question. $\endgroup$– Paul MantaDec 14, 2012 at 6:22
-
$\begingroup$ Does this Wikipedia subsection on cliques of fixed size answer your question? $\endgroup$– MerbsDec 14, 2012 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 MantaDec 14, 2012 at 6:48
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ In bounded tree-width graphs is not $n^t$, it's $O(t^t n)$. $\endgroup$– user742Dec 14, 2012 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$– SparkDec 15, 2012 at 9:48
$\begingroup$
$\endgroup$
4
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.
-
$\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$– user742Dec 14, 2012 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$– usulDec 14, 2012 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$ Dec 14, 2012 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$– usulDec 14, 2012 at 17:58