On the Power of Simple Reductions for the Maximum Independent Set Problem

DOI10.1007/978-3-319-42634-1_28zbMath1476.68217arXiv1608.00724OpenAlexW2496359038MaRDI QIDQ2817877

Darren Strash

Publication date: 2 September 2016

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

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

zbMATH Keywords

reductionsmaximum independent setexact algorithmskernelizationminimum vertex cover

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Scale reduction techniques for computing maximum induced bicliques, Critical and maximum independent sets of a graph

Uses Software

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast local search for the maximum independent set problem
• Exact exponential algorithms.
• An exact bit-parallel algorithm for the maximum clique problem
• 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
• An improved bit parallel exact maximum clique algorithm
• Fast algorithms for max independent set
• Improvements to MCS algorithm for the maximum clique problem
• Using critical sets to solve the maximum independent set problem
• Crown structures for vertex cover kernelization
• Vertex Cover: Further Observations and Further Improvements
• Kernelization Using Structural Parameters on Sparse Graph Classes
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Estimating the size of correcting codes using extremal graph problems
• Vertex packings: Structural properties and algorithms
• On Finding Critical Independent and Vertex Sets
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
• Some Experimental and Theoretical Results on Test Case Generators for the Maximum Clique Problem
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs