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

The lower and the upper irredundance numbers of a graph G, denoted ir(G) and IR(G), 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 G on n vertices admits exact algorithms running in time faster than the trivial Theta(2(n) center dot poly(n)) enumeration, also called the 2(n)-barrier. The main contributions of this article are exact exponential-time algorithms breaking the 2(n)-barrier for irredundance. We establish algorithms with running times of O*(1.99914(n)) for computing ir(G) and O*(1.9369(n)) for computing IR(G). 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. (C) 2011 Elsevier B.V. All rights reserved.