Breaking the 2n-barrier for Irredundance: Two lines of attack

Author(s)
Binkele-Raible, Daniel
Brankovic, Ljiljana
Cygan, Marek
Fernau, Henning
Kneis, Joachim
Kratsch, Dieter
Langer, Alexander
Liedloff, Mathieu
Pilipczuk, Marcin
Rossmanith, Peter
Wojtaszczyk, Jakub Onufry
Publication Date
2011-09
Abstract
<p>The lower and the upper irredundance numbers of a graph <i>G</i>, denoted ir(<i>G</i>) and IR(<i>G</i>), respectively, are conceptually linked to the domination and independence numbers and have numerous relations to other graph parameters. It has been an open question whether determining these numbers for a graph <i>G</i> on <i>n</i> vertices admits exact algorithms running in time faster than the trivial Θ(<i>2<sup>n</sup></i> · poly(<i>n</i>)) enumeration, also called the <i>2<sup>n</sup></i>-barrier. The main contributions of this article are exact exponential-time algorithms breaking the <i>2<sup>n</sup></i>-barrier for irredundance. We establish algorithms with running times of <i>O<sup>*</sup></i>(1.99914<sup><i>n</i></sup>) for computing ir(<i>G</i>) and <i>O<sup>*</sup></i>(1.9369<sup><i>n</i></sup>) for computing IR(<i>G</i>). Both algorithms use polynomial space. The first algorithm uses a parameterized approach to obtain (faster) exact algorithms. The second one is based, in addition, on a reduction to the Maximum Induced Matching problem providing a branch-and-reduce algorithm to solve it.</p>
Citation
Journal of Discrete Algorithms, 9(3), p. 214-230
ISSN
1570-8675
1570-8667
Link
Publisher
Elsevier BV
Title
Breaking the 2n-barrier for Irredundance: Two lines of attack
Type of document
Journal Article
Entity Type
Publication

Files:

NameSizeformatDescriptionLink