Constructing Concrete Hard Instances of the Maximum Independent Set Problem

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.

arXiv comment9 pages, 5 figures

References in corpus (23)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Phase Transitions in the Coloring of Random Graphs
• Clustering of solutions in the random satisfiability problem
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Statistical mechanics of the random K-SAT model
• Probing for quantum speedup in spin glass problems with planted solutions
• Algorithmic barriers from phase transitions
• Simplest random K-satisfiability problem
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• The backtracking survey propagation algorithm for solving random K-SAT problems
• On independent sets in random graphs
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Statistical Mechanics of maximal independent sets
• Practical engineering of hard spin-glass instances
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Phase transition for cutting-plane approach to vertex-cover problem
• Typical behavior of the linear programming method for combinatorial optimization problems: From a statistical-mechanical perspective
• Typical Performance of Approximation Algorithms for NP-hard Problems
• An exact algorithm exhibiting RS-RSB/easy-hard correspondence for the maximum independent set problem