Exact Algorithms for Maximum Independent Set

Mingyu Xiao, Hiroshi Nagamochi

We show that the maximum independent set problem (MIS) on an $n$-vertex graph can be solved in $1.1996^n{n}^{O(1)}$ time and polynomial space, which even is faster than Robson's $1.2…