Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
| Autoři | |
|---|---|
| Rok publikování | 2011 |
| Druh | Článek ve sborníku |
| Konference | Parameterized and Exact Computation |
| Fakulta / Pracoviště MU | |
| Citace | |
| Obor | Teorie informace |
| Klíčová slova | vertex cover |
| Popis | 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. |
| Související projekty: |