License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2009.1820
URN: urn:nbn:de:0030-drops-18200
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/1820/
Go to the corresponding LIPIcs Volume Portal

Fellows, Michael R. ; Guo, Jiong ; Moser, Hannes ; Niedermeier, Rolf

A Generalization of Nemhauser and Trotter's Local Optimization Theorem

pdf-format:
09001.FellowsMichael.1820.pdf (0.2 MB)

Abstract

The Nemhauser-Trotter local optimization theorem applies to the NP-hard \textsc{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 \textsc{Vertex Cover}, called \textrm{\sc Bounded-Degree Deletion}, that has promise to become an important tool in the analysis of gene and other biological networks. For some fixed~$d\geq 0$, \textrm{\sc 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$. \textsc{Vertex Cover} is the special case of $d=0$. Our generalization of the Nemhauser-Trotter theorem implies that \textrm{\sc 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 \textrm{\sc Bounded-Degree Deletion}, we provide a W[2]-hardness result for \textrm{\sc Bounded-Degree Deletion} in case of unbounded $d$-values.

BibTeX - Entry

@InProceedings{fellows_et_al:LIPIcs:2009:1820,
  author =	{Michael R. Fellows and Jiong Guo and Hannes Moser and Rolf Niedermeier},
  title =	{{A Generalization of Nemhauser and Trotter's Local Optimization Theorem}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{409--420},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Susanne Albers and Jean-Yves Marion},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/1820},
  URN =		{urn:nbn:de:0030-drops-18200},
  doi =		{10.4230/LIPIcs.STACS.2009.1820},
  annote =	{Keywords: Algorithms, Computational complexity, NP-hard problems, W[2]-completeness, Graph problems, Combinatorial optimization, Fixed-parameter tractability, K}
}

Keywords: Algorithms, Computational complexity, NP-hard problems, W[2]-completeness, Graph problems, Combinatorial optimization, Fixed-parameter tractability, K
Collection: 26th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2009
Date of publication: 19.02.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI