How hard is counting the number of vertex covers after a small perturbation?

Question

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'$?

Answer 1

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