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.


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


2 Answers 2


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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.