Generalizing vertex cover as a graph parameter

VCLA will be hosting a talk by Robert Ganian from the Goethe University Frankfurt on October 2nd, 2012.

ABSTRACT

Parameterized algorithms allow the design of exact and efficient algorithms for NP-hard problems by exploiting the structure of the input, and graph parameters such as tree-width and clique-width have been successfully used to solve many classical problems on well-structured graphs. However, some problems are known not to admit efficient algorithms even on graphs of bounded tree-width, and vertex cover is often used as a powerful parameter capable of dealing with these problems.

The drawback of vertex cover as a parameter is that it severely restricts the structure of admissible graph classes. After introducing the area, the talk focuses on a generalization of vertex cover called twin-cover and shows that it can often be used instead of vertex cover as the parameter of parameterized algorithms. The advantage of twin-cover over vertex cover is that it restricts the input of our algorithms much less and attains low values even on dense graphs.