Robert Ganian - Improving Vertex Cover as a Graph Parameter

dmtcs:2136 - Discrete Mathematics & Theoretical Computer Science, September 14, 2015, Vol. 17 no.2 - https://doi.org/10.46298/dmtcs.2136
Improving Vertex Cover as a Graph ParameterArticle

Authors: Robert Ganian ORCID1,2

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.


Volume: Vol. 17 no.2
Section: Discrete Algorithms
Published on: September 14, 2015
Submitted on: July 1, 2013
Keywords: Parameterized Complexity,Twin-cover,Vertex cover,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Exploiting New Types of Structure for Fixed Parameter Tractability (X-TRACT); Code: P 26696

8 Documents citing this article

Consultation statistics

This page has been seen 872 times.
This article's PDF has been downloaded 1513 times.