Exact algorithms for maximum independent set

2013/12/21 by Mingyu Xiao, Hiroshi Nagamochi · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithm #Bounded function #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computational complexity theory #Computer science #Degree (music) #Discrete mathematics #Exponential function #Graph #Independent set #Mathematics #Maximal independent set #PSPACE #Set (abstract data type) #Time complexity #Vertex (graph theory) #cs.DS

paper · pdf · doi:10.1016/j.ic.2017.06.001

published as Information and Computation 255(1) (2017):126-146

arxiv created 2013/12/21 · openalex publication_date 2017/06/07 · crossref created 2017/06/07 · crossref issued 2017/08/01 · crossref published 2017/08/01 · crossref published-print 2017/08/01 · arxiv updated 2017/08/08 · crossref deposited 2021/07/31 · openalex created_date 2025/10/10 · crossref indexed 2026/07/21 · openalex updated_date 2026/08/05

Abstract

We show that the maximum independent set problem (MIS) on an n-vertex graph can be solved in 1.1996ⁿn^O(1) time and polynomial space, which even is faster than Robson's 1.2109ⁿ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ⁿn^O(1) and 1.1970ⁿn^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.

Citations

• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• A measure & conquer approach for the analysis of exact algorithms
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
• Algorithms for maximum independent sets
• Finding a Maximum Independent Set
• Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs

Cited by

• Branch-and-Bound Tensor Networks for Exact Ground-State Characterization
• Independent set (graph theory) [wikipedia]

Related

• An O^*(1.0821ⁿ)-Time Algorithm for Computing Maximum Independent Set in Graphs with Bounded Degree 3
• Fast Algorithms for Max Independent Set in Graphs of Small Average Degree
• Exact algorithms for maximum weighted independent set on sparse graphs
• Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws
• Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs