New Branching Rules: Improvements on Independent Set and Vertex Cover in Sparse Graphs
Abstract
Description
We present an $O^*(1.0919^n)$-time algorithm for finding a maximum independent set in an $n$-vertex graph with degree bounded by 3, which improves the previously known algorithm of running time $O^*(1.0977^n)$ by Bourgeois, Escoffier and Paschos [IWPEC 2008]. We also present an $O^*(1.1923^k)$-time algorithm to decide if a graph with degree bounded by 3 has a vertex cover of size $k$, which improves the previously known algorithm of running time $O^*(1.1939^k)$ by Chen, Kanj and Xia [ISAAC 2003].
Two new branching techniques, \emph{branching on a bottle} and \emph{branching on a 4-cycle}, are introduced, which help us to design simple and fast algorithms for the maximum independent set and minimum vertex cover problems and avoid tedious branching rules.
The paper was presented at the 2nd annual meeting of asian association for algorithms and computation (AAAC 2009), April 11-12, 2009, Hangzhou, China
The paper was presented at the 2nd annual meeting of asian association for algorithms and computation (AAAC 2009), April 11-12, 2009, Hangzhou, China