Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2013-002 (Apil 8, 2013)

A Refined Algorithm for Maximum Independent Set in Degree-4 Graphs
by Mingyu Xiao and Hiroshi Nagamochi

pdf File

The maximum independent set problem is one of the most important problems in worst-case analysis for exact algorithms. Improvement on this problem in low-degree graphs can be used to get improvement on the problem in general graphs. In this paper, we show that the maximum independent set problem in an $n$-vertex graph with degree bounded by $4$ can be solved in $O^*(1.1376 ^n)$ time and polynomial space, improving all previous exact algorithms for this problem. As most fast exact algorithms, this algorithm is a branch-and-search algorithm and analyzed by using the measure and conquer method. To effectively analyze the running time bound, we use the idea of `shift' to save some decreasing on the measure from some good branches to some bad branches. After treating cycles of length 3 and 4 in the graph, we check carefully what will happen after branching on a degree-4 vertex (without any local structure), and then we can get the claimed improvement.