patternMinor
K-Clique in Connected Graphs
Viewed 0 times
connectedgraphsclique
Problem
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?Solution
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.
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.
Context
StackExchange Computer Science Q#7393, answer score: 5
Revisions (0)
No revisions yet.