Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/923287

OpenURL Link
Title
The parameterized complexity of some minimum label problems
Author/Creator
Fellows, Michael R.;  Guo, Jiong;  Kanj, Iyad
Institution
The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)
Description
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 Π with respect to G 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 requires interesting algorithmic methods that we develop in this paper.
Relation
Journal of Computer and System Sciences Vol. 76, Issue 8, p. 727-740
Publisher Link
http://dx.doi.org/10.1016/j.jcss.2010.02.012
Date
2010
Publisher
Elsevier
Keyword(s)
edge labeled graphs;  W-hardness;  fixed-parameter tractability
Resource Type
journal article
Identifier
http://hdl.handle.net/1959.13/923287
Identifier
ISSN:0022-0000
Reviewed
Reviewed
8 Visitors 10 Hits 0 Downloads
Save/E-mail Citation
Citation Format
E-mail Address
Subject
"Journal of Computer and System Sciences"
 
OR