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

OpenURL Link
Title
A parameterized route to exact puzzles: breaking the 2n-barrier for irredundance
Author/Creator
Binkele-Raible, Daniel;  Brankovic, Ljiljana;  Fernau, Henning;  Kneis, Joachim;  Kratsch, Dieter;  Langer, Alexander;  Liedloff, Mathieu;  Rossmanith, Peter
Institution
The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
Description
The lower and the upper irredundance numbers of a graph G, denoted ir(G) and IR(G) respectively, are conceptually linked to domination and independence numbers and have numerous relations to other graph parameters. It is a long-standing open question whether determining these numbers for a graph G on n vertices admits exact algorithms running in time less than the trivial Ω(2n) enumeration barrier. We solve this open problem by devising parameterized algorithms for the duals of the natural parameterizations of the problems with running times faster than O*(4ᵏ). For example, we present an algorithm running in time O*(3.069ᵏ) for determining whether IR(G) is at least n − k. Although the corresponding problem has been shown to be in FPT by kernelization techniques, this paper offers the first parameterized algorithms with an exponential dependency on the parameter in the running time. Furthermore, these seem to be the first examples of a parameterized approach leading to a solution to a problem in exponential time algorithmics where the natural interpretation as exact exponential-time algorithms fails.
Relation
CIAC 7th International Conference (CIAC 2010). Algorithms and Complexity: 7th International Conference, CIAC 2010: Proceedings (Rome, Italy 26-28 May 2010) p. 311-322
Publisher Link
http://dx.doi.org/10.1007/978-3-642-13073-1_28
Date
2010
Publisher
Springer Verlag
Keyword(s)
graph parameters;  parameterized algorithms;  2n enumeration barrier;  irredundance numbers
Resource Type
conference paper
Identifier
http://hdl.handle.net/1959.13/927106
Identifier
ISBN:9783642130724
Identifier
ISSN:0302-9743
Reviewed
Reviewed
13 Visitors 16 Hits 0 Downloads
Save/E-mail Citation
Citation Format
E-mail Address
Subject
"A parameterized route to exact puzzles: breaking the 2n-barrier for irredundance"
 
OR