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

Frozen complexityGraph coloringHamiltonian cycleNP-completenessSatisfiabilitySubgraph isomorphism

Mathematics Subject Classification ID

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

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

• Determining computational complexity from characteristic ``phase transitions
• Frozen development in graph coloring
• Generating hard satisfiability problems
• Graph Theory and Probability
• 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?)
• The phase transition in 1-in-k SAT and NAE 3-SAT

Cited in

(7)

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

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)