On percolation and NP-hardness

DOI10.4230/LIPICS.ICALP.2016.80MaRDI QIDQ4598220zbMATH OpenFDO

Authors Huck Bennett, Daniel Reichman, Igor Shinkar

Publication date 19 December 2017

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2016.80

zbMATH Keywords

chromatic numberNP-hardnesspercolationrandom subgraphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On percolation and \(\mathcal{NP}\)-hardness
• An Average Case NP-complete Graph Colouring Problem
• A hard problem that is almost always easy
• The resolution complexity of independent sets and vertex covers in random graphs
• Random instances of problems in NP -- algorithms and statistical physics

Cited in

(2)

• On percolation and \(\mathcal{NP}\)-hardness
• Complexity of Two-dimensional Bootstrap Percolation Difficulty: Algorithm and NP-Hardness

This page was built for publication: On percolation and NP-hardness

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