On the power of simple reductions for the maximum independent set problem
From MaRDI portal
Publication:2817877
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Abstract: Reductions---rules that reduce input size while maintaining the ability to compute an optimal solution---are critical for developing efficient maximum independent set algorithms in both theory and practice. While several simple reductions have previously been shown to make small domain-specific instances tractable in practice, it was only recently shown that advanced reductions (in a measure-and-conquer approach) can be used to solve real-world networks on millions of vertices [Akiba and Iwata, TCS 2016]. In this paper we compare these state-of-the-art reductions against a small suite of simple reductions, and come to two conclusions: just two simple reductions---vertex folding and isolated vertex removal---are sufficient for many real-world instances, and further, the power of the advanced rules comes largely from their initial application (i.e., kernelization), and not their repeated application during branch-and-bound. As a part of our comparison, we give the first experimental evaluation of a reduction based on maximum critical independent sets, and show it is highly effective in practice for medium-sized networks.
Recommendations
- Exactly solving the maximum weight independent set problem on large real-world graphs
- Scalable kernelization for maximum independent sets
- Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
- On reducing maximum independent set to minimum satisfiability
Cites work
- scientific article; zbMATH DE number 2084315 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
- A note on critical independence reductions
- A simple and faster branch-and-bound algorithm for finding a maximum clique
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- An exact bit-parallel algorithm for the maximum clique problem
- An improved bit parallel exact maximum clique algorithm
- Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
- Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
- Crown structures for vertex cover kernelization
- Estimating the size of correcting codes using extremal graph problems
- Exact exponential algorithms.
- Fast algorithms for max independent set
- Fast local search for the maximum independent set problem
- Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
- Improvements to MCS algorithm for the maximum clique problem
- Kernelization using structural parameters on sparse graph classes
- On Finding Critical Independent and Vertex Sets
- Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem
- Using critical sets to solve the maximum independent set problem
- Vertex cover: Further observations and further improvements
- Vertex packings: Structural properties and algorithms
Cited in
(6)- New properties of maximum independent set problem solution truncation rules or redundant branches
- On reducing maximum independent set to minimum satisfiability
- Scale reduction techniques for computing maximum induced bicliques
- Scalable kernelization for maximum independent sets
- Critical and maximum independent sets of a graph
- Exactly solving the maximum weight independent set problem on large real-world graphs
This page was built for publication: On the power of simple reductions for the maximum independent set problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817877)
