Exact algorithms for maximum independent set

DOI10.1016/J.IC.2017.06.001MaRDI QIDQ2013558zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Mingyu Xiao, Hiroshi Nagamochi

Publication date 8 August 2017

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.6260

zbMATH Keywords

amortized analysisbranch-and-reduceexact algorithmgraphindependent setmeasure-and-conquerpolynomial-space

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• Exact Algorithms for Maximum Independent Set
• scientific article; zbMATH DE number 1305487
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
• Fast algorithms for max independent set
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs

Cites work

• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
• A fine-grained analysis of a simple independent set algorithm
• A measure \& conquer approach for the analysis of exact algorithms
• A refined algorithm for maximum independent set in degree-4 graphs
• A simple and fast algorithm for Maximum Independent Set in 3-degree graphs (extended abstract)
• A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
• Algorithms for maximum independent sets
• An exact algorithm for maximum independent set in degree-5 graphs
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• Exact Algorithms for Maximum Independent Set
• Exact exponential algorithms.
• Fast algorithms for max independent set
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• Finding a Maximum Independent Set
• scientific article; zbMATH DE number 1305487 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• Vertex cover: Further observations and further improvements

Cited in

(63)

• Moderately exponential time algorithms for the maximum bounded-degree-1 set problem
• On comparing algorithms for the maximum clique problem
• A refined algorithm for maximum independent set in degree-4 graphs
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• \textit{Branch} \& \textit{memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees
• A note on the fine-grained complexity of MIS on regular graphs
• Exact algorithms for counting 3-colorings of graphs
• Moderate exponential-time algorithms for scheduling problems
• Domination chain: characterisation, classical complexity, parameterised complexity and approximability
• On the complexity of detecting hazards
• A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
• Faster exponential-time algorithms for approximately counting independent sets
• Exact algorithms for maximum induced matching
• Fast algorithms for max independent set
• Reinforcement learning for combinatorial optimization: a survey
• Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract)
• Solving vertex cover in polynomial time on hyperbolic random graphs
• Exact Algorithms for Maximum Independent Set
• A fine-grained analysis of a simple independent set algorithm
• An O *(1.0977 n ) Exact Algorithm for max independent set in Sparse Graphs
• A bottom-up method and fast algorithms for Max Independent Set
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Algorithms for maximum independent sets
• scientific article; zbMATH DE number 1305487 (Why is no real title available?)
• scientific article; zbMATH DE number 1305522 (Why is no real title available?)
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Faster FPT algorithm for 5-path vertex cover
• Exact Solution Algorithms for the Chordless Cycle Problem
• Listing Maximal Independent Sets with Minimal Space and Bounded Delay
• Fast local search for the maximum independent set problem
• Approximation algorithms for maximum independent set of pseudo-disks
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• Conflict free version of covering problems on graphs: classical and parameterized
• An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem†
• Further improvements for SAT in terms of formula length
• Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs
• Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
• Average-case complexity of a branch-and-bound algorithm for \textsc{Min Dominating Set}
• On the maximal independence polynomial of the covering graph of the hypercube up to \(n=6\)
• A polytime preprocess algorithm for the maximum independent set problem
• Targeted Branching for the Maximum Independent Set Problem
• Minimum number of maximal dissociation sets in trees
• Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
• Generating Faster Algorithms for d-Path Vertex Cover
• Turán’s Theorem Through Algorithmic Lens
• On kernels for \(d\)-path vertex cover
• A bisection approach to subcubic maximum induced matching
• Semidefinite programming bounds and a branch-and-bound algorithm for the chordless cycle problem
• Maximum independent set when excluding an induced minor: K₁ + tK₂ and tC₃ C₄
• Exact algorithms for the maximum k-balanced weighted biclique problem
• Machine learning predicts graph properties: clique, girth, and independent numbers
• A faster algorithm for vertex cover parameterized by solution size
• Exponential-time approximation schemes via compression
• The minimum number of maximal dissociation sets in unicyclic graphs
• Sidestepping barriers for dominating set in parameterized complexity
• The number of maximal dissociation sets in unicyclic graphs
• Bounds on isolated scattering number
• Kernels for storage capacity and dual index coding
• On the external validity of average-case analyses of graph algorithms
• On the external validity of average-case analyses of graph algorithms
• Moderate exponential-time algorithms for scheduling problems
• Parameterized complexity of modular dominating structures in bounded-treewidth graphs
• An exact algorithm for maximum independent set in degree-5 graphs

This page was built for publication: Exact algorithms for maximum independent set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2013558)