On the complexity of unfrozen problems

DOI10.1016/J.DAM.2005.05.003MaRDI QIDQ2581544zbMATH OpenOpenAlexFDO

Authors Adam Beacham, J. Culberson

Publication date 10 January 2006

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2005.05.003

zbMATH Keywords

Hamiltonian cycleNP-completenessSatisfiabilityGraph coloringSubgraph isomorphismFrozen complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Recognizing frozen variables in constraint satisfaction problems
• scientific article; zbMATH DE number 67483
• Frozen variables in random Boolean constraint satisfaction problems
• Recognizing maximal unfrozen graphs with respect to independent sets is CO-NP-complete
• DP-Complete Problems Derived from Extremal NP-Complete Properties

Cites work

• scientific article; zbMATH DE number 67483 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1249657 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 956851 (Why is no real title available?)
• Determining computational complexity from characteristic ``phase transitions
• Frozen development in graph coloring
• Generating hard satisfiability problems
• Graph Theory and Probability
• The phase transition in 1-in-\(k\) SAT and NAE 3-SAT

Cited in

(6)

• Complexity of Stability.
• Recognizing frozen variables in constraint satisfaction problems
• Complexity of stability
• DP-Complete Problems Derived from Extremal NP-Complete Properties
• Recognizing maximal unfrozen graphs with respect to independent sets is CO-NP-complete
• Gap theorems for robust satisfiability: Boolean CSPs and beyond

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: On the complexity of unfrozen problems

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