Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics

Investor logo

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

GANIAN Robert

Year of publication 2011
Type Article in Proceedings
Conference Parameterized and Exact Computation
MU Faculty or unit

Faculty of Informatics

Citation
Field Information theory
Keywords vertex cover
Description Parameterized algorithms are a very useful tool for dealing with NP-hard problems on graphs. In this context, vertex cover is used as a powerful parameter for dealing with problems which are hard to solve even on graphs of bounded tree-width. The drawback of vertex cover is that bounding it severely restricts admissible graph classes. We introduce a new parameter called twin-cover and show that it is capable of solving a wide range of hard problems while also being much less restrictive than vertex cover and attaining low values even on dense graphs. The article begins by introducing a new FPT algorithm for Graph Motif on graphs of bounded vertex cover. This is the first algorithm of this kind for Graph Motif. We continue by defining twin-cover and providing some related results and notions. The next section contains a number of new FPT algorithms on graphs of bounded twin-cover, with a special emphasis on solving problems which are hard even on graphs of bounded tree-width. Finally, section five generalizes the recent results of Michael Lampis for $M\!S_1$ model checking from vertex cover to twin-cover.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.