<p>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.</p>

<p>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})$.</p>

CC BY-SA 2.5
2011-03-10T01:54:29.547Z
2011-03-10T01:54:29.547Z
David Eppstein
<p>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).</p>

<blockquote>
  <p><strong>Questions</strong>  </p>
  
  <ol>
  <li>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|} &lt; 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|$".</li>
  <li>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?</li>
  </ol>
</blockquote>

CC BY-SA 2.5
2011-03-09T15:00:49.977Z
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"?
Holger
CC BY-SA 2.5
2011-03-09T15:14:36.040Z
@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|$?
Giorgio Camerani
CC BY-SA 2.5
2011-03-09T16:16:06.573Z
@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.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-09T16:28:07.567Z
There is a sharp bound on the number of independent sets (and hence vertex covers) of a regular graph in terms of the degree:

http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=7183052
Colin McQuillan
CC BY-SA 2.5
2011-03-09T16:29:18.733Z
@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).
Giorgio Camerani
CC BY-SA 2.5
2011-03-09T16:42:29.733Z
@Walter: Thank you, but I don't still get it. Suppose in your class of graphs you know every graph has at most $1.5^n$ vertex covers where $n$ is the number of vertices.  Then, in your problem from the 1st question, do you want to solve the following problem? Given a graph from this class, determine whether there exists a number $c$ s.t. the number of vertex covers of the graph is at most $n^c$.  Or: Given a graph from this class and a number $c$, determine whether the number of vertex covers of the graph is at most $n^c$?  Or something else?
Yoshio Okamoto
CC BY-SA 2.5
2011-03-09T16:59:04.750Z
@Yoshio: You're welcome. It's much more simple: if I know that every graph of my class has at most $1.5^n$ vertex covers, then my 1st question is answered (knowing that is exactly the answer to the 1st question, it's exactly what I liked to know). Of course I'd like a class as general as possible (a good example would be: every graph with $\frac{|E|}{|V|} < 5$ has no less than $1.3^{|V|}$ vertex covers). If I know that my class has at most $1.5^n$ vertex covers, I can just conclude that I can't use brute force and that I must invent something more clever.
Giorgio Camerani
CC BY-SA 2.5
2011-03-09T19:53:47.233Z
Note also that the number of vertex covers is precisely the number of integer points of the related polytope, so maybe there's some polyhedral theory that kicks in here.
Suresh Venkat
CC BY-SA 2.5
2011-03-09T20:25:38.067Z
@Suresh: Thanks for your comment. Do you think that the question, as currently phrased, is clear and understandable and not trivial?
Giorgio Camerani
CC BY-SA 2.5
2011-03-09T20:51:06.050Z
If the graph isn't too dense, you can find an independent set with $\omega(\log n)$ nodes, and hence the number of independent sets (= number of vertex covers) is superpolynomial in $n$.
Jukka Suomela
CC BY-SA 2.5
2011-03-09T21:43:58.243Z
@Jukka: Isn't the number of independent sets equal to $2^n$ minus the number of vertex covers?
Giorgio Camerani
CC BY-SA 2.5
2011-03-09T21:49:12.690Z
@Walter: No. Take any vertex cover; its complement is an independent set. And vice versa. There is a 1:1 mapping between them.
Jukka Suomela
CC BY-SA 2.5
2011-03-09T22:14:16.473Z
@Jukka: Sorry, of course you're right. I was misleaded by the word "complement".
Giorgio Camerani
CC BY-SA 2.5
2011-03-10T07:32:11.197Z
@Suresh: I'm now parsing your comment: how is "the related polytope" defined?
Giorgio Camerani
CC BY-SA 2.5
2011-03-10T07:46:39.140Z
@Jukka: I'm parsing your before-last comment: if I understand correctly, in that case yes the number of vertex covers is superpolynomial in $n$, but it seems also easy to represent (i.e. compactly representable). I mean, those $\omega(\log n)$ nodes would be, in terms of the set of all vertex covers, just free variables...do you agree?
Giorgio Camerani
CC BY-SA 2.5
2011-03-10T13:24:35.600Z
@Downvoters: Could you please motivate why did you downvote? Is the question trivial for you? Or badly stated?
Giorgio Camerani
CC BY-SA 2.5
2011-03-10T17:00:51.313Z
@walter it's the polytope defined by the linear relaxation of the VC ILP. Which is to say, the polytope consisting of constraints $x_i + x_j \ge 1$ for all edges $(i,j)$, coupled with the usual $x_i \ge 0$ constraints.
Suresh Venkat
<cc.complexity-theory><graph-theory><graph-algorithms><counting-complexity>
Number of Vertex Covers: when it is polynomial and when it is superpolynomial
Giorgio Camerani
# Number of Vertex Covers: when it is polynomial and when it is superpolynomial

(Asked by: username_0 on 2011-03-09)

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?

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, counting-complexity

> **Comments:**
> **username_1**: 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"?  
> **username_0**: @username_1: 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|$?  
> **username_2**: @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.  
> **username_3**: There is a sharp bound on the number of independent sets (and hence vertex covers) of a regular graph in terms of the degree:  http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=7183052  
> **username_0**: @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).  
> **username_2**: @Walter: Thank you, but I don't still get it. Suppose in your class of graphs you know every graph has at most $1.5^n$ vertex covers where $n$ is the number of vertices.  Then, in your problem from the 1st question, do you want to solve the following problem? Given a graph from this class, determine whether there exists a number $c$ s.t. the number of vertex covers of the graph is at most $n^c$.  Or: Given a graph from this class and a number $c$, determine whether the number of vertex covers of the graph is at most $n^c$?  Or something else?  
> **username_0**: @Yoshio: You're welcome. It's much more simple: if I know that every graph of my class has at most $1.5^n$ vertex covers, then my 1st question is answered (knowing that is exactly the answer to the 1st question, it's exactly what I liked to know). Of course I'd like a class as general as possible (a good example would be: every graph with $\frac{|E|}{|V|} < 5$ has no less than $1.3^{|V|}$ vertex covers). If I know that my class has at most $1.5^n$ vertex covers, I can just conclude that I can't use brute force and that I must invent something more clever.  
> **username_4**: Note also that the number of vertex covers is precisely the number of integer points of the related polytope, so maybe there's some polyhedral theory that kicks in here.  
> **username_0**: @Suresh: Thanks for your comment. Do you think that the question, as currently phrased, is clear and understandable and not trivial?  
> **username_5**: If the graph isn't too dense, you can find an independent set with $\omega(\log n)$ nodes, and hence the number of independent sets (= number of vertex covers) is superpolynomial in $n$.  
> **username_0**: @Jukka: Isn't the number of independent sets equal to $2^n$ minus the number of vertex covers?  
> **username_5**: @Walter: No. Take any vertex cover; its complement is an independent set. And vice versa. There is a 1:1 mapping between them.  
> **username_0**: @Jukka: Sorry, of course you're right. I was misleaded by the word "complement".  
> **username_0**: @Suresh: I'm now parsing your comment: how is "the related polytope" defined?  
> **username_0**: @Jukka: I'm parsing your before-last comment: if I understand correctly, in that case yes the number of vertex covers is superpolynomial in $n$, but it seems also easy to represent (i.e. compactly representable). I mean, those $\omega(\log n)$ nodes would be, in terms of the set of all vertex covers, just free variables...do you agree?  
> **username_0**: @Downvoters: Could you please motivate why did you downvote? Is the question trivial for you? Or badly stated?  
> **username_4**: @walter it's the polytope defined by the linear relaxation of the VC ILP. Which is to say, the polytope consisting of constraints $x_i + x_j \ge 1$ for all edges $(i,j)$, coupled with the usual $x_i \ge 0$ constraints.  

---

## 1 answers

### Answer by username_6 on 2011-03-10. Score: 7

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})$.


---

