Paper Info
Title
The Parameterized Complexity of Some Minimum Label Problems
Abstract
We study the parameterized complexity of several minimum label graph problems, in which we are given an undirected graph whose edges are labeled, and a property 驴, and we are asked to find a subset of edges satisfying property 驴 that uses the minimum number of labels. These problems have a lot of applications in networking. We show that all the problems under consideration are W[2]-hard when parameterized by the number of used labels, and that they remain W[2]-hard even on graphs whose pathwidth is bounded above by a small constant. On the positive side, we prove that most of these problems are FPT when parameterized by the solution size, that is, the size of the sought edge set. For example, we show that computing a maximum matching or an edge dominating set that uses the minimum number of labels, is FPT when parameterized by the solution size. Proving that some of these problems are FPT is nontrivial, and requires interesting and elegant algorithmic methods that we develop in this paper.
Year
DOI
Venue
2009
10.1007/978-3-642-11409-0_8
Journal of Computer and System Sciences
Keywords
DocType
Volume
minimum label graph problem,edges satisfying property,parameterized complexity,undirected graph,maximum matching,minimum number,fixed-parameter tractability,minimum label problems,edge set,positive side,edge labeled graphs,elegant algorithmic method,minimum label problem,interesting algorithmic method,solution size,w-hardness
Conference
76
Issue
ISSN
Citations 
8
Journal of Computer and System Sciences
11
PageRank 
References 
Authors
0.65
18
3
Name
Order
Citations
PageRank
Michael R. Fellows14138319.37
Jiong Guo2149388.91
Iyad A. Kanj3111074.93