Constructing concrete hard instances of the maximum independent set problem

DOI10.1088/1742-5468/AB409DzbMATH Open1456.68134arXiv1807.03739OpenAlexW3098383736MaRDI QIDQ5149679FDOQ5149679

Authors: Naoto Shiraishi, Junya Takahashi 

Publication date: 12 February 2021

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

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.

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

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

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)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• 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)