An exact algorithm exhibiting RS-RSB/easy-hard correspondence for the maximum independent set problem
arXiv:1704.06899 · doi:10.7566/JPSJ.86.073001
Abstract
A recently proposed exact algorithm for the maximum independent set problem is analyzed. The typical running time is improved exponentially in some parameter regions compared to simple binary search. The algorithm also overcomes the core transition point, where the conventional leaf removal algorithm fails, and works up to the replica symmetry breaking (RSB) transition point. This suggests that a leaf removal core itself is not enough for typical hardness in the random maximum independent set problem, providing further evidence for RSB being the obstacle for algorithms in general.
arXiv comment4 pages, 6 figures
References in corpus (12)
- Emergence of scaling in random networks
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Coloring random graphs
- Algorithmic barriers from phase transitions
- Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
- Core percolation in random graphs: a critical phenomena analysis
- Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms
- Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
- Vertex cover problem studied by cavity method: Analytics and population dynamics
- 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
- A Fidelity Susceptibility Approach to Quantum Annealing of NP-hard problems