Computer Science – Computational Complexity
Scientific paper
2010-11-12
Computer Science
Computational Complexity
49 pages
Scientific paper
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 {\Phi} of statements ("constraints") about these variables in the language of graphs, where each statement is taken from a fixed finite set {\Psi} of allowed quantifier-free first-order formulas; the question is whether {\Phi} is satisfiable in a graph. We prove that either {\Psi} 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 to classify 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.
Bodirsky Manuel
Pinsker Michael
No associations
LandOfFree
Schaefer's theorem for graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Schaefer's theorem for graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Schaefer's theorem for graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-204137