Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2011-001 (January 06, 2011)

Further Improvement on Maximum Independent Set in 4-Degree Graphs
by Mingyu Xiao and Hiroshi Nagamochi

pdf File


We present a simple algorithm for the maximum independent set problem in an $n$-vertex graph with degree bounded by $4$, which runs in $O^*(1.1527^n)$ time and improves all previous algorithms for this problem. In this paper, we use the ``Measure and Conquer method'' to analyze the running time bound, and use some good reduction and branching rules to avoid tedious checking on a large number of local structures.