Which is the complexity of counting the number of vertex covers of trees? Is it still #P-complete, as for general graphs?
$\begingroup$
$\endgroup$
asked Mar 19, 2011 at 18:45
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
2
The complement of a vertex cover is an independent set. Your question is therefore equivalent to asking whether counting independent sets is #P-complete on trees.
The answer to this question is NO, it is not #P-complete: there is actually a polynomial-time algorithm to count the number of solutions.
- S. D. Noble, Evaluating a Weighted Graph Polynomial for Graphs of Bounded Tree-Width, The Electronic Journal of Combinatorics 16(1) R64, 2009. (link)
Noble actually shows much more. Suppose the class of graphs under consideration has treewidth at most $k$. Then the weighted graph polynomial $U$, which evaluated at a certain point yields the number of independent sets of a graph, can be evaluated in $O(a_k n^{2k+3})$ operations at any point. Here $a_k$ depends only on $k$ and $n$ is the number of vertices in the input graph. Hence there is a polynomial-time algorithm to count the number of vertex covers on trees (or any other class of graphs of bounded treewidth).
On the other side, it is interesting to ask: what is the smallest class that is known to be #P-complete?
Theorem (Greenhill, 2000): counting independent sets in 3-regular graphs is #P-complete. (link).
In the comments Colin McQuillan pointed out an even stronger result:
- Mingji Xia, Wenbo Zhao, #3-Regular Bipartite Planar Vertex Cover is #P-Complete, TAMC 2006, 356–364.
Note that wall graphs are 3-regular (if their corners are joined up), bipartite, and planar, but they have arbitrarily large treewidth.
Finally, a different graph polynomial $R_2$ yields the number of independent sets in a bipartite graph. This was posed as an open question:
Question (Ge and Štefankovič, 2010): is the exact evaluation of the $R_2$ polynomial easy for bounded tree-width graphs? (link)
answered Mar 19, 2011 at 21:32
-
2$\begingroup$ Counting independent sets is also #P-hard for bipartite planar 3-regular graphs: Mingji Xia, Wenbo Zhao: #3-Regular Bipartite Planar Vertex Cover is #P-Complete. TAMC 2006: 356-364 $\endgroup$ Commented Mar 21, 2011 at 13:11
-
$\begingroup$ @Colin: wall graphs are bipartite planar 3-regular, so this isn't surprising. Thanks for the pointer! $\endgroup$ Commented Mar 21, 2011 at 14:14
$\begingroup$
$\endgroup$
8
The DP for vertex cover on trees breaks the cases into two disjoint settings, one where the root node of the subtree is picked for the cover, and one where it isn't. This suggests that it should be adaptable to the counting version: the disjointness means you can merely add the contributions from the subcases.
answered Mar 19, 2011 at 20:09
-
$\begingroup$ @Suresh: I was thinking about what happens if we use this approach with a chain tree. In such a case recursively selecting the root should yield an exponential running time. But if we recursively select the middle node of the chain, then the running time is linear. It's amazing how such a slight variation could affect the running time so dramatically. $\endgroup$ Commented Mar 20, 2011 at 20:18
-
1
-
$\begingroup$ @Suresh: Maybe I've used an "invented" term (although I recall to having heard it in the past). By "chain tree" I mean a tree where every node has exactly one child (except the only one leaf). Example: $V = \{1,2,3,4,5\}$, $E=\{ \{1,2\}, \{2,3\}, \{3,4\}, \{4,5\} \}$. $\endgroup$ Commented Mar 21, 2011 at 9:07
-
-
1$\begingroup$ Moreover what's happening there is the Fibonacci problem, where direct application of recursion from the root causes exponential running time. In this case, and in general, you always work bottom up in the DP to make sure it runs efficiently. $\endgroup$ Commented Mar 21, 2011 at 14:31
$\begingroup$
$\endgroup$
Should be in P even on graphs of bounded treewidth
$\begingroup$
$\endgroup$
Find any solution in O(N) time using the greedy algorithm (keep moving the leaves, select parent of a leaf if the leaf is not selected or covered.)
Initialize a counter vector to ones for the selected nodes. Check the selected nodes in vertex cover one by one and determine if you release that node and select any of its un-selected neighbors without violating the vertex cover. For each move increase the corresponding counter by one. Number of the vertex cover should be the product of the counter.
(Please let us know if you find any counter example.)
