On the power of simple reductions for the maximum independent set problem

DOI10.1007/978-3-319-42634-1_28zbMATH Open1476.68217arXiv1608.00724OpenAlexW2496359038MaRDI QIDQ2817877FDOQ2817877

Authors: Darren Strash 

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

exact algorithmsreductionskernelizationmaximum independent setminimum vertex cover

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Exact exponential algorithms.
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Vertex packings: Structural properties and algorithms
• Fast algorithms for max independent set
• Improvements to MCS algorithm for the maximum clique problem
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• An exact bit-parallel algorithm for the maximum clique problem
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• Kernelization using structural parameters on sparse graph classes
• Crown structures for vertex cover kernelization
• Vertex cover: Further observations and further improvements
• An improved bit parallel exact maximum clique algorithm
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• Fast local search for the maximum independent set problem
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• Using critical sets to solve the maximum independent set problem
• On Finding Critical Independent and Vertex Sets
• A note on critical independence reductions
• Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Estimating the size of correcting codes using extremal graph problems

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

Uses Software

• Pajek
• Pajek datasets
• SNAP
• BioGRID
• KONECT
• WebGraph

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)