Binkele-Raible, Daniel

Brankovic, Ljiljana

Cygan, Marek

Fernau, Henning

Kneis, Joachim

Kratsch, Dieter

Langer, Alexander

Liedloff, Mathieu

Pilipczuk, Marcin

Rossmanith, Peter

Wojtaszczyk, Jakub Onufry

2011-09

<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ⁿ</i> · poly(<i>n</i>)) enumeration, also called the <i>2ⁿ</i>-barrier. The main contributions of this article are exact exponential-time algorithms breaking the <i>2ⁿ</i>-barrier for irredundance. We establish algorithms with running times of <i>O^*</i>(1.99914^<i>n</i>) for computing ir(<i>G</i>) and <i>O^*</i>(1.9369^<i>n</i>) 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>

Journal of Discrete Algorithms, 9(3), p. 214-230

1570-8675

1570-8667

https://hdl.handle.net/1959.11/62013

en

Elsevier BV

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

Journal Article

Publication