We classify completely the complexity of evaluating positive equality-free sentences of first-order logic over a fixed, finite structure D. This problem may be seen as a natural generalisation of the quantified constraint satisfaction problem QCSP(D). We obtain a tetrachotomy for arbitrary finite domains: each problem is either in L, is NP-complete, is co-NP-complete or is Pspace-complete. Moreover, its complexity is characterised algebraically in terms of the presence or absence of specific surjective hyper-endomorphisms; and, logically, in terms of relativisation properties with respect to positive equality-free sentences. We prove that the meta-problem, to establish for a specific D into which of the four classes the related problem lies, is NP-hard.

La conjecture de la dichotomie postule qu'un problème de satisfaction de contraintes est soit facile (dans P), soit difficile (NP-complet). Cette conjecture, motivée par Feder et Vardi il y a 20 ans, reste ouverte malgré les efforts importants d'une communauté internationale regroupant des chercheurs issus d'horizons très variés.

Nous présentons ici un bref aperçu des résultats obtenus et des techniques utilisées pour étudier cette question centrale en informatique théorique afin d'illustrer cette interdisciplinarité qui mêle algèbre, combinatoire, complexité et logique.

In a k-ary n-cube with at most 2n − 2 faulty edges, and two given nodes u and v. Assuming that m the number of healthy links of u is no more than that of v, we show that there are m disjoint paths between u and v.

Forbidden patterns problems are a generalisation of (finite) constraint satisfaction problems which are definable in Feder and Vardi’s logic MMSNP. In fact, they are examples of infinite constraint satisfaction problems with nice model theoretic properties introduced by Bodirsky. In previous work with Iain Stewart, we introduced a normal form for these forbidden patterns problems which allowed us to provide an effective characterisation of when a problem is a finite or infinite constraint satisfaction problem. One of the central concepts of this normal form is that of a recolouring. In the presence of a recolouring from a forbidden patterns problem Ω₁ to another forbidden patterns problem Ω₂ , containment of Ω₁ in Ω₂ follows. The converse does not hold in general and it remained open whether it did in the case of problems being given in our normal form. In this paper, we prove that this is indeed the case. We also show that the recolouring problem is Π₂-hard and in Σ₃.

We study the complexity of evaluating positive equality-free sentences of first-order (FO) logic over a fixed, finite structure B. This may be seen as a natural generalisation of the non-uniform quantified constraint satisfaction problem QCSP(B). We introduce surjective hyper-endomorphisms and use them in proving a Galois connection that characterises definability in positive equality-free FO. Through an algebraic method, we derive a complete complexity classification for our problems as B ranges over structures of size at most three. Specifically, each problem is either in L, is NP-complete, is coNP-complete or is Pspace-complete.

Forbidden Patterns Problems (FPPs) are a proper generalisation of Constraint Satisfaction Problems (CSPs). However, we show that when the input is connected and belongs to a class which has low tree-depth decomposition (e.g. structure of bounded degree, proper minor closed class and more generally class of bounded expansion) any FPP becomes a CSP. This result can also be rephrased in terms of expressiveness of the logic MMSNP, introduced by Feder and Vardi in relation with CSPs. Our proof generalises that of a recent paper by Nesetril and Ossona de Mendez. Note that our result holds in the general setting of problems over arbitrary relational structures (not just for graphs).

We study the complexity of evaluating positive equality-free sentences of first-order (FO) logic over a fixed, finite structure B. This may be seen as a natural generalisation of the non-uniform quantified constraint satisfaction problem QCSP(B). We introduce surjective hyper-endomorphisms and use them in proving a Galois connection that characterises definability in positive equality-free FO. Through an algebraic method, we derive a complete complexity classification for our problems as B ranges over structures of size at most three. Specifically, each problem is either in L, is NP-complete, is coNP-complete or is Pspace-complete.

We improve upon the best known upper and lower bounds on the sizes of minimal feedback vertex sets in butterflies. Also, we construct new feedback vertex sets in grids so that for a large number of grids, the size of our feedback vertex set in the grid matches the best known lower bound, and for all other grids it differs from this lower bound by at most 2.

We study two containment problems related to the quantified constraint satisfaction problem (QCSP). Firstly, we give a combinatorial condition on finite structures A and B that is necessary and sufficient to render QCSP(A) a subset of QCSP(B). The required condition is the existence of a positive integer r such that there is a surjective homomorphism from the power structure A^r to B. We note that this condition is already necessary to guarantee containment of the Pi_2 restriction of QCSP, that is Pi_2-CSP(A) a subset of Pi_2-CSP(B). Since we are able to give an effective bound on such an r, we provide a decision procedure for the model containment problem with non-deterministic double-exponential time complexity.

Secondly, we prove that the entailment problem for quantified conjunctive-positive first-order logic is decidable. That is, given two sentences phi and psi of first-order logic with no instances of negation or disjunction, we give an algorithm that determines whether "phi implies psi" is true in all structures (models). Our result is in some sense tight, since we show that the entailment problem for positive first-order logic (i.e. quantified conjunctive-positive logic plus disjunction) is undecidable.

In the early nineties, Feder and Vardi attempted to logically characterize the class of constraint satisfaction problems, CSP, by introducing a syntactic fragment of existential monadic second-order logic, namely the logic MMSNP. They proved that MMSNP is computationally equivalent to CSP but that CSP is strictly included in MMSNP (as classes of problems). We introduce here a new class of combinatorial problems, the class of forbidden patterns problems, FPP, and show that they correspond (modulo technical restrictions) to the class of problems MMSNP. We introduce some novel algebraic tools that allow us to characterize exactly those problems that are in FPP (and so in MMSNP) but not in CSP. Furthermore, given a representation for a problem in FPP, we are able to construct a normal form and, according to a very simple criterion, so decide whether the problem is in CSP or not (this whole process is effective). If the problem is in CSP then we can construct a template for this problem, otherwise for any given candidate for the role of template, we can build a counter-example (again, this process is effective).

We study the quantified H-colouring problem for directed graphs. We prove that the quantified H-colouring problem is tractable when H is a directed cycle or a semicomplete digraph with at most one cycle. We give sufficient criteria for the quantified H-colouring problem to be in NP, and thus infer NP-completeness of the quantified H-colouring problem when H is semicomplete with more than one cycle and both a source and a sink.

We expose a strict hierarchy within monotone monadic strict NP without inequalities (MMSNP), based on the number of second-order monadic quantifiers. We do this by studying a finer strict hierarchy within a class of forbidden patterns problems (FPP), based on the number of permitted colours. Through an adaptation of a preservation theorem of Feder and Vardi, we are able to prove that this strict hierarchy also exists in monadic strict NP (MSNP). Our hierarchy results apply over a uniform signature involving a single binary relation, that is over digraphs.

Hell and Nesetril proved that the H-coloring problem is NP-complete if, and only if, H is bipartite. In this paper, we investigate the complexity of the quantified H-coloring problem (a restriction of the quantified constraint satisfaction problem to undirected graphs). We introduce this problem using a new two player coloring game. We prove that the quantified H-coloring problem is: tractable, if H is bipartite; NP-complete, if H is not bipartite and not connected; and, Pspace complete, if H is connected and has a unique cycle, which is of odd length. We conjecture that the last case extends to all non-bipartite connected graphs.

Forbidden Pattern problem (FPP) is a proper generalisation of Constraint Satisfaction Problem (CSP) [?]. FPP is related to MMSNP, a logic introduced in relation with CSP by Feder and Vardi. We prove that Forbidden Pattern Problems are Constraint Satisfaction Problems when restricted to graphs of bounded degree. This result is generalisation of a result by Häggkvist and Hell who showed that F-moteness of bounded-degree graphs is a CSP (that is, for a given graph F there exists a graph H so that the class of bounded-degree graphs that do not admit a homomorphism from F is exactly the same as the class of bounded-degree graphs that are homomorphic to H). Forbidden pattern property is a strict generalisation of F-moteness (in fact of F-moteness combined with a CSP) involving both vertex- and edge-colorings of the graph F, and thus allowing to express NP-complete problems (while F-moteness is always in P). We finally extend our result to arbitrary structures (not only graphs) and prove that every problem in MMSNP, restricted to connected input of bounded degree, is in fact in CSP.

Forbidden Patterns Problems (FPPs) are a proper generalisation of Constraint Satisfaction Problems (CSPs). However, we show that when the input belongs to a proper minor closed class, a FPP becomes a CSP. This result can also be rephrased in terms of expressiveness of the logic MMSNP, introduced by Feder and Vardi in relation with CSPs. Our proof generalises that of a recent paper by Nesetril and Ossona de Mendez. Note that our result holds in the general setting of problems over arbitrary relational structures (not just for graphs).

We study non-uniform constraint satisfaction problems where the underlying signature contains constant and function symbols as well as relation symbols. Amongst our results are the following. We establish a dichotomy result for the class of non-uniform constraint satisfaction problems over the signature consisting of one unary function symbol by showing that every such problem is either complete for L, via very restricted logical reductions, or trivial (depending upon whether the template function has a fixed point or not). We show that the class of non-uniform constraint satisfaction problems whose templates are structures over the signature λ2 consisting of two unary function symbols reflects the full computational significance of the class of non-uniform constraint satisfaction problems over relational structures. We prove a dichotomy result for the class of non-uniform constraint satisfaction problems where the template is a λ2-structure with the property that the two unary functions involved are the reverse of one another, in that every such problem is either solvable in polynomial-time or NP-complete. Finally, we extend some of our results to the situation where instances of non-uniform constraint satisfaction problems come equipped with lists of elements of the template structure which restrict the set of allowable homomorphisms.

We exhibit some problems defined in Feder and Vardi's logic MMSNP that are not in the class CSP of constraint satisfaction problems. Whilst some of these problems have previously been shown to be in MMSNP (that is, definable in MMSNP) but not in CSP, existing proof are probabilistic in nature. We provide explicit combinatorial constructions to prove that these problems are not in CSP and we use these constructions to exhibit yet more problems in MMSNP that are not in CSP.