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.
Categories: cs.DS