In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the two. Equivalently, each edge in the graph has at most one ...
Exact algorithms for maximum independent set
- Citation data:
Information and Computation, ISSN: 0890-5401, Vol: 255, Page: 126-146
- Publication Year:
- Mathematics; Computer Science
We show that the maximum independent set problem on an n -vertex graph can be solved in 1.1996nnO(1) time and polynomial space, which even is faster than Robson's 1.2109nnO(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.1893nnO(1) and 1.1970nnO(1), respectively. Our algorithms are obtained by using fast algorithms for MIS in low-degree graphs in a hierarchical way and making a careful analysis on the structure of bounded-degree graphs.