### Schaefer's Theorem for GraphsSchaefer's Theorem for Graphs

Access Restriction
Subscribed

 Author Bodirsky, Manuel ♦ Pinsker, Michael Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Constraint satisfaction ♦ Ramsey theory ♦ Computational logic ♦ Homogeneous structures ♦ Model theory ♦ The countable random graph ♦ Universal algebra Abstract 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 the propositional logic of graphs instead of Boolean logic. In this generalization of Schaefer's result, the input consists of a set $\textit{W}$ of variables and a conjunction Φ of statements (“constraints”) about these variables in the language of graphs, where each statement is taken from a fixed finite set Ψ of allowed quantifier-free first-order formulas; the question is whether Φ is satisfiable in a graph. We prove that either Ψ is contained in one out of 17 classes of graph formulas and the corresponding problem can be solved in polynomial time, or the problem is NP-complete. This is achieved by a universal-algebraic approach, which in turn allows us to use structural Ramsey theory. To apply the universal-algebraic approach, we formulate the computational problems under consideration as constraint satisfaction problems (CSPs) whose templates are first-order definable in the countably infinite random graph. Our method for classifying the computational complexity of those CSPs is based on a Ramsey-theoretic analysis of functions acting on the random graph, and we develop general tools suitable for such an analysis which are of independent mathematical interest. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-06-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 3 Page Count 52 Starting Page 1 Ending Page 52

#### Open content in new tab

Source: ACM Digital Library