How hard is counting the number of vertex covers after a small perturbation? 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:


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&#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;$?
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.