Constructing concrete hard instances of the maximum independent set problem

DOI10.1088/1742-5468/AB409DzbMath1456.68134arXiv1807.03739OpenAlexW3098383736MaRDI QIDQ5149679

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)

Cites Work

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

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