Breaking the n2 2 n -barrier for Irredundance: Two lines of attack ?
The lower and the upper irredundance numbers of a graph G , denoted ir(G) ir ( G ) and IR(G) 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 ?(n2?poly(n)) ? ( 2 n ? poly ( n ) ) enumeration, also called the n2 2 n -barrier. The main contributions of this article are exact exponential-time algorithms breaking the n2 2 n -barrier for irredundance. We establish algorithms with running times of O?(n1.99914) O ? ( 1.99914 n ) for computing ir(G) ir ( G ) and O?(n1.9369) O ? ( 1.9369 n ) for computing IR(G) 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.
irredundance number graph algorithms