Improving Vertex Cover as a Graph Parameter
Robert Ganian
Abstract
Parameterized algorithms are often used to efficiently solve NP-hard problems on graphs.
In this context, vertex cover is used as a powerful parameter for dealing with graph problems which are hard to solve even when parameterized by tree-width;
however, the drawback of vertex cover is that bounding it severely restricts admissible graph classes.
We introduce a generalization of vertex cover called twin-cover and show that FPT algorithms exist for a wide range of difficult problems when parameterized by twin-cover. The advantage of twin-cover over vertex cover is that it imposes a lesser restriction on the graph structure and attains low values even on dense graphs.
Apart from introducing the parameter itself, this article provides a number of new FPT algorithms parameterized by twin-cover with a special emphasis on solving problems which are not in FPT even when parameterized by tree-width.
It also shows that MS1 model checking can be done in elementary FPT time parameterized by twin-cover and discusses the field of kernelization.
Full Text: PDF