A Generalization of Nemhauser and Trotter's Local Optimization Theorem

Abstract : The Nemhauser-Trotter local optimization theorem applies to the NP-hard Vertex Cover problem and has applications in approximation as well as parameterized algorithmics. We present a framework that generalizes Nemhauser and Trotter's result to vertex deletion and graph packing problems, introducing novel algorithmic strategies based on purely combinatorial arguments (not referring to linear programming as the Nemhauser-Trotter result originally did). We exhibit our framework using a generalization of Vertex Cover, called Bounded- Degree Deletion, that has promise to become an important tool in the analysis of gene and other biological networks. For some fixed d ≥ 0, Bounded-Degree Deletion asks to delete as few vertices as possible from a graph in order to transform it into a graph with maximum vertex degree at most d. Vertex Cover is the special case of d = 0. Our generalization of the Nemhauser-Trotter theorem implies that Bounded-Degree Deletion has a problem kernel with a linear number of vertices for every constant d. We also outline an application of our extremal combinatorial approach to the problem of packing stars with a bounded number of leaves. Finally, charting the border between (parameterized) tractability and intractability for Bounded-Degree Deletion, we provide a W[2]-hardness result for Bounded-Degree Deletion in case of unbounded d-values.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.409-420, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00360058
Contributeur : Publications Loria <>
Soumis le : mardi 10 février 2009 - 10:55:37
Dernière modification le : vendredi 9 février 2018 - 19:00:03
Document(s) archivé(s) le : mardi 8 juin 2010 - 20:35:39

Fichiers

fellows_new.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00360058, version 1
  • ARXIV : 0902.2149

Collections

Citation

Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier. A Generalization of Nemhauser and Trotter's Local Optimization Theorem. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.409-420, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00360058〉

Partager

Métriques

Consultations de la notice

44

Téléchargements de fichiers

688