Constructing concrete hard instances of the maximum independent set problem

DOI10.1088/1742-5468/AB409DMaRDI QIDQ5149679zbMATH OpenOpenAlexFDO

Authors Naoto Shiraishi, Junya Takahashi

Publication date 12 February 2021

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We provide a deterministic construction of hard instances for the maximum independent set problem (MIS). The constructed hard instances form an infinite graph sequence with increasing size, which possesses similar characteristics to sparse random graphs and in which MIS cannot be solved efficiently. We analytically and numerically show that all algorithms employing cycle-chain refutation, which is a general refutation method we introduce for capturing the ability of many known algorithms, cannot upper bound the size of the maximum independent set tightly.

Recommendations

• Finding Large Independent Sets in Polynomial Expected Time
• On the complexity of approximating the independent set problem
• scientific article; zbMATH DE number 1305487
• Exact Algorithms for Maximum Independent Set
• On the maximum independent set problem in graphs of bounded maximum degree

Cites work

• scientific article; zbMATH DE number 4191094 (Why is no real title available?)
• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 1256724 (Why is no real title available?)
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• Average-Case Complexity
• Computational Complexity
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Determining computational complexity from characteristic ``phase transitions
• Determining the Stability Number of a Graph
• Differential equations for random processes and random graphs
• Expander graphs and their applications
• From average case complexity to improper learning complexity
• Generating hard satisfiable formulas by hiding solutions deceptively
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Information, Physics, and Computation
• Limits of local algorithms over sparse random graphs
• More on average case vs approximation complexity
• Number Theory
• On lattices, learning with errors, random linear codes, and cryptography
• On the independence number of random cubic graphs
• On the solution-space geometry of random constraint satisfaction problems
• Phase Transitions in Combinatorial Optimization Problems
• Proof of the satisfiability conjecture for large \(k\)
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Relations between average case complexity and approximation complexity
• Sharp thresholds of graph properties, and the $k$-sat problem
• Spectra of graphs
• Sum of squares lower bounds for refuting any CSP
• The asymptotic distribution of short cycles in random regular graphs
• The large deviations of the whitening process in random constraint satisfaction problems
• The resolution complexity of independent sets and vertex covers in random graphs
• The threshold for SDP-refutation of random regular NAE-3SAT
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Typical performance of approximation algorithms for NP-hard problems

Cited in

(3)

• scientific article; zbMATH DE number 1305522 (Why is no real title available?)
• Constructive -- non-constructive approximation and maximum independent set problem
• New instances for maximum weight independent set from a vehicle routing application

This page was built for publication: Constructing concrete hard instances of the maximum independent set problem

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