Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2013-006 (November 1, 2013)

Exact Algorithms for Maximum Independent Set
by Mingyu Xiao and Hiroshi Nagamochi

pdf File

We show that the maximum independent set problem (MIS) on an $n$-vertex graph can be solved in $1.1996^nn^{O(1)}$ time and polynomial space, which even is faster than Robson's $1.2109^{n}n^{O(1)}$-time exponential -space algorithm published in 1986. We also obtain improved algorithms for MIS in graphs with maximum degree 6 and 7, which run in time of $1.1893^nn^{O(1)}$ and $1.1970^nn^{O(1)}$, respectively. Our algorithms are obtained by using fast algorithms for MIS in low- degree graphs in a hierarchical way and making a careful analyses on the structure of bounded-degree graphs.