1
$\begingroup$

The number $C$ of vertex covers of a graph $G = (V, E)$ can be either polynomial in $|V|$ or superpolynomial in $|V|$. $C$ being superpolynomial in $|V|$ doesn't necessarily mean that $C$ is hard to determine. For instance, consider the graph $G = (V, E)$ where $|V| = 2n$ and $E$ is defined as $E = \{ \{ i,j \} | i \mod 2 = 1 \land j = i + 1 \}$: such graph has a number of vertex covers $C=3^{|E|} = 3^{\frac{|V|}{2}}$ which is both superpolynomial in $|V|$ and very easy to determine. On the other hand, knowing in advance that $C$ is polynomial in $|V|$ allows us to use brute force keeping the running time polynomial in $|V|$. So it seems that determing $C$ is hard only if it is superpolynomial in $|V|$, but not always (as the above example demonstrates).

Questions

  1. Is it possible to determine in advance if $C$ is polynomial in $|V|$ or superpolynomial in $|V|$? Is there any known result linking some parameter of the graph with the number of its vertex covers? An example of such result would be: "Every graph with $\frac{|E|}{|V|} \geq 4$ has not more than $n^{\frac{|E|}{|V|}}$ vertex covers". Another example would be: "Every graph with $\frac{|E|}{|V|} < 2$ has not less than $1.18^{\sqrt{|E|}}$ vertex covers". How $C$ varies with $G$? Clearly, the more edges $G$ has, the less vertex covers it has: did anyone formalized this trivial fact, showing precisely how $C$ decreases as $|E|$ increases? Which other parameters affect $C$, and how? I mean, from a pure empirical point of view, it's almost evident that a graph with $\frac{|E|}{|V|} \geq 5$ has not so many vertex covers, where "not so many" means "certainly polynomial in $|V|$".
  2. When $C$ is superpolynomial in $|V|$ brute force is useless. However, I wonder if, as in the above example, it is always true that $C$ being superpolynomial intrinsically implies the presence of "multiplying blocks" (I don't know how to state this more formally), which in turns would mean that the set of all vertex covers is easy to represent (in other words, it is compactly representable). Is there any known result in this spirit?
$\endgroup$
  • $\begingroup$ What do you mean by "in advance" in question 1? Particularly, would running the brute force algorithm for some polynomial number of steps not be considered "in advance"? $\endgroup$ – Holger Mar 9 '11 at 15:00
  • $\begingroup$ @Holger: By "in advance" I mean before running the counting procedure. If we know in advance that $C$ is polynomial in $|V|$, then we can use brute force without any risk; on the other hand, if we know in advance that $C$ is superpolynomial in $|V|$ then we can't use brute force and we must invent something else. Concerning the second question in your comment, I would answer yes but...how to know the exact number of such steps? How many steps should we run before safely declaring that $C$ is superpolynomial in $|V|$? $\endgroup$ – Giorgio Camerani Mar 9 '11 at 15:14
  • 2
    $\begingroup$ @Walter: For the 1st question, would you formalize more about "polynomial" and "superpolynomial"? I guess you're talking about asymptotics, so these terms only make sense if you consider a class (or a series) of graphs, and you cannot say for a single graph the number of vertex covers is polynomial or superpolynomial unless you fix your polynomial. It's hard to guess what kind of computational problem you have in mind for the 1st question. $\endgroup$ – Yoshio Okamoto Mar 9 '11 at 16:16
  • 2
    $\begingroup$ There is a sharp bound on the number of independent sets (and hence vertex covers) of a regular graph in terms of the degree: journals.cambridge.org/action/… $\endgroup$ – Colin McQuillan Mar 9 '11 at 16:28
  • $\begingroup$ @Yoshio: I meant a class of graphs with the same $frac{|E|}{|V|}$ (or, in general, with the same value of some other graph parameter). $\endgroup$ – Giorgio Camerani Mar 9 '11 at 16:29
7
$\begingroup$

There's a close relation between the independence number of a graph and the number of its vertex covers, not close enough to completely answer your question but close: if the independence number is superlogarithmic then the number of covers is superpolynomial, and otherwise it's quasipolynomial.

More specifically if the independence number is $\alpha$, and the maximum independent set $I$ is the complement of a vertex cover $C$, then each of the $2^\alpha$ supersets of $C$ is also a vertex cover. So in this case if $\alpha \ge c\,\log_2 n$ then the number of covers is lower bounded by $n^c$. But each cover is complementary to an independent set and there can be only $O(n^\alpha)$ sets of at most $\alpha$ vertices, so if $\alpha \le c\,\log_2 n$ then this upper bound is $O(2^{c\, \log^2 n})$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.