Fellows, Michael R. ;
Guo, Jiong ;
Moser, Hannes ;
Niedermeier, Rolf
A Generalization of Nemhauser and Trotter's Local Optimization Theorem
Abstract
The NemhauserTrotter local optimization theorem applies to the NPhard \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 NemhauserTrotter result originally did).
We exhibit our framework using a generalization of \textsc{Vertex Cover}, called \textrm{\sc BoundedDegree 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 BoundedDegree 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 NemhauserTrotter theorem implies that \textrm{\sc BoundedDegree 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 BoundedDegree Deletion}, we provide a W[2]hardness result for \textrm{\sc BoundedDegree 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 = {409420},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897095},
ISSN = {18688969},
year = {2009},
volume = {3},
editor = {Susanne Albers and JeanYves Marion},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/1820},
URN = {urn:nbn:de:0030drops18200},
doi = {10.4230/LIPIcs.STACS.2009.1820},
annote = {Keywords: Algorithms, Computational complexity, NPhard problems, W[2]completeness, Graph problems, Combinatorial optimization, Fixedparameter tractability, K}
}
2009
Keywords: 

Algorithms, Computational complexity, NPhard problems, W[2]completeness, Graph problems, Combinatorial optimization, Fixedparameter tractability, K 
Seminar: 

26th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2009 
Date of publication: 

2009 