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

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.