<p>I describe a method for adding edges to a graph one at a time and computing the number of vertex covers. <a href="http://www.mathkb.com/Uwe/Forum.aspx/math/77614/3SAT-A-Better-2SAT-Approximation" rel="nofollow">http://www.mathkb.com/Uwe/Forum.aspx/math/77614/3SAT-A-Better-2SAT-Approximation</a> . Using my method, you can approximate the number of vertex covers in polynomial time, but computing the exact effect of adding even one edge can be exponential. You can efficiently compute the effect of adding an edge if you know something about the existing graph. For example, adding an edge that is disjoint from the existing graph is easily computable. Other examples woud include adding an edge to a chain or a complete graph.</p>

CC BY-SA 3.0
2011-04-28T20:47:57.233Z
2011-04-28T20:47:57.233Z
Russell Easterly
<p>Since counting vertex covers is #P-complete, your problem is unlikely to be in P; otherwise you could count the number of vertex covers starting from the empty graph on $|V|$ vertices, adding edges one by one.</p>

CC BY-SA 3.0
2011-04-14T14:45:23.607Z
2011-04-14T14:45:23.607Z
Marcus Ritt
<p>Suppose you are given both a graph $G(V,E)$ and the exact number $C$ of vertex covers of $G$. Now suppose that $G$ is subject to a very small perturbation $P$, leading to $G&#39;=P(G)$. More precisely, the perturbation $P$ is restricted to be one of the following:</p>

<ul>
<li>Addition of $1$ new edge.</li>
<li>Addition of $2$ new distinct edges.</li>
<li>Removal of $1$ existing edge.</li>
<li>Removal of $2$ distinct existing edges.</li>
</ul>

<blockquote>
  <p><strong>Question</strong><br><br>
  Given $G$, $C$, and $P$, how hard is to determine the number $C&#39;$ of vertex covers of $G&#39;=P(G)$? Is it possible to exploit the knowledge of $C$ and the fact that the perturbation is so tiny in order to efficiently determine $C&#39;$?</p>
</blockquote>

<cc.complexity-theory><graph-theory><graph-algorithms><counting-complexity>
How hard is counting the number of vertex covers after a small perturbation?
Giorgio Camerani
# How hard is counting the number of vertex covers after a small perturbation?

(Asked by: username_0 on 2011-04-14)

Suppose you are given both a graph $G(V,E)$ and the exact number $C$ of vertex covers of $G$. Now suppose that $G$ is subject to a very small perturbation $P$, leading to $G'=P(G)$. More precisely, the perturbation $P$ is restricted to be one of the following:

* Addition of $1$ new edge.
* Addition of $2$ new distinct edges.
* Removal of $1$ existing edge.
* Removal of $2$ distinct existing edges.

> **Question**  
>   
> Given $G$, $C$, and $P$, how hard is to determine the number $C'$ of vertex covers of $G'=P(G)$? Is it possible to exploit the knowledge of $C$ and the fact that the perturbation is so tiny in order to efficiently determine $C'$?

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


---

## 2 answers

### Answer by username_2 on 2011-04-14. Score: 17 | Accepted answer

Since counting vertex covers is #P-complete, your problem is unlikely to be in P; otherwise you could count the number of vertex covers starting from the empty graph on $|V|$ vertices, adding edges one by one.


---

### Answer by username_1 on 2011-04-28. Score: 2

I describe a method for adding edges to a graph one at a time and computing the number of vertex covers. <http://www.mathkb.com/Uwe/Forum.aspx/math/77614/3SAT-A-Better-2SAT-Approximation> . Using my method, you can approximate the number of vertex covers in polynomial time, but computing the exact effect of adding even one edge can be exponential. You can efficiently compute the effect of adding an edge if you know something about the existing graph. For example, adding an edge that is disjoint from the existing graph is easily computable. Other examples woud include adding an edge to a chain or a complete graph.


---

