Schaefer's theorem for graphs

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

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 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 universalalgebraic 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.

Details

OriginalspracheEnglisch
Aufsatznummer19
FachzeitschriftJournal of the ACM
Jahrgang62
Ausgabenummer3
PublikationsstatusVeröffentlicht - 1 Juni 2015
Peer-Review-StatusJa

Externe IDs

ORCID /0000-0001-8228-3611/work/142241108

Schlagworte

Schlagwörter

  • Algorithms, Computational logic, Constraint satisfaction, F.2.2 [analysis of algorithms and problem complexity]: Nonnumerical algorithms and problems - Computations on discrete structures, Homogeneous structures, Model theory, Ramsey theory, The countable random graph, Theory, Universal algebra