Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
| Authors | |
|---|---|
| Year of publication | 2011 |
| Type | Article in Proceedings |
| Conference | Parameterized and Exact Computation |
| MU Faculty or unit | |
| 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: |