Schaefer's Theorem for Graphs
Schaefer's Theorem for Graphs
Schaefer's theorem is a complexity classification result for so-called Boolean constraint satisfaction problems : it states that every Boolean constraint satisfaction problem is either contained in one out of six classes and can be solved in polynomial time, or is NP-complete. We present an analog of this dichotomy result for …