Raising The Bar For Vertex Cover: Fixed-parameter Tractability Above A Higher Guarantee

Shivam Garg, Geevarghese Philip

We investigate the following above-guarantee parameterization of the classical Vertex Cover problem: Given a graph $G$ and $k\in \mathbb{N}$ as input, does $G$ have a vertex cover o…