Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2012-003 (May 8, 2012)

Further Improvement on Maximum Independent Set in Graphs with Maximum Degree 4
by Mingyu Xiao, 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.1446^n)$ time and improves all previous algorithms for this problem. The algorithm is analyzed by using the ``Measure and Conquer'' method. We use some good reduction and branching rules with a new idea on setting weights to obtain the improved time bound without increasing the number of branching rules in the algorithm.