Reducing the Vertex Cover Number via Edge Contractions

Paloma T. Lima, Vinicius F. dos Santos, Ignasi Sau +2

The CONTRACTION(vc) problem takes as input a graph $G$ on $n$ vertices and two integers $k$ and $d$, and asks whether one can contract at most $k$ edges to reduce the size of a min…