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

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ⁿ</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>