Improving Vertex Cover as a Graph Parameter

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.77-100
Liste complète des métadonnées

Littérature citée [42 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01349051
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 26 juillet 2016 - 17:26:51
Dernière modification le : jeudi 7 septembre 2017 - 01:03:44

Fichier

2378-9773-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01349051, version 1

Collections

Citation

Robert Ganian. Improving Vertex Cover as a Graph Parameter. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no.2 (2), pp.77-100. 〈hal-01349051〉

Partager

Métriques

Consultations de la notice

49

Téléchargements de fichiers

437