Exact Algorithms for Maximum Independent Set

Abstract

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.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^n{n}^{O(1)}$ and $1.1970^n{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.

Cited by in corpus (22)

• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• Listing Maximal k-Plexes in Large Real-World Graphs
• On the External Validity of Average-Case Analyses of Graph Algorithms
• A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
• Four short stories on surprising algorithmic uses of treewidth
• Lorentz Quantum Computer
• Quantum Optimization Benchmarking Library - The Intractable Decathlon
• Escaping Local Minima with Quantum Coherent Cooling
• Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
• Exact algorithms for maximum weighted independent set on sparse graphs
• Graph Profiling for Vertex Cover: Targeted Reductions in a Branch and Reduce Solver
• Exact Algorithms With Worst-case Guarantee For Scheduling: From Theory to Practice
• Faster Vertex Cover Algorithms on GPUs with Component-Aware Parallel Branching
• Quantum Hamiltonian Algorithms for Maximum Independent Sets
• An Efficient Method to Transform SAT problems to Binary Integer Linear Programming Problem
• Properties of nowhere dense graph classes related to independent set problem
• The Generalized Independent and Dominating Set Problems on Unit Disk Graphs
• On the complexity of detecting hazards
• Maximum Independent Set when excluding an induced minor: $K_1+t{K}_2$ and $t{C}_3\uplus C_4$
• Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry
• On Fine-Grained Exact Computation in Regular Graphs
• On a reduction of the weighted induced bipartite subgraph problem to the weighted independent set problem