We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem \( \mathrm{QCSP}(\mathrm{H}) \) when \( \mathrm{H} \) is a reflexive tournament. It is well known that reflexive tournaments can be split into a sequence of strongly connected components \( \mathrm{H}_1,\ldots ,\mathrm{H}_n \) so that there exists an edge from every vertex of \( \mathrm{H}_i \) to every vertex of \( \mathrm{H}_j \) if and only if \( i\lt j \) . We prove that if \( \mathrm{H} \) has both its initial and final strongly connected component (possibly equal) of size 1, then \( \mathrm{QCSP}(\mathrm{H}) \) is in \( \mathsf {NL} \) and otherwise \( \mathrm{QCSP}(\mathrm{H}) \) is \( \mathsf {NP} \) -hard.

We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split into a sequence of strongly connected components H₁,…,H_n so that there exists an edge from every vertex of H_i to every vertex of H_j if and only if i < j. We prove that if H has both its initial and final strongly connected component (possibly equal) of size 1, then QCSP(H) is in NL and otherwise QCSP(H) is NP-hard.

The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have demonstrated to play a crucial role in many of those applications. For instance, in the decision CSPs, structural properties of the relational structures involved---like, for example, dismantlability---and their logical characterizations have been instrumental for determining the complexity and other properties of the problem. Topological properties of the solution set such as connectedness are related to the hardness of CSPs over random structures. Additionally, in approximate counting and statistical physics, where CSPs emerge in the form of spin systems, mixing properties and the uniqueness of Gibbs measures have been heavily exploited for approximating partition functions and free energy. In spite of the great diversity of those features, there are some eerie similarities between them. These were observed and made more precise in the case of graph homomorphisms by Brightwell and Winkler, who showed that dismantlability of the target graph, connectedness of the set of homomorphisms, and good mixing properties of the corresponding spin system are all equivalent. In this paper we go a step further and demonstrate similar connections for arbitrary CSPs. This requires much deeper understanding of dismantling and the structure of the solution space in the case of relational structures, and new refined concepts of mixing introduced by Brice\~no. In addition, we develop properties related to the study of valid extensions of a given partially defined homomorphism, an approach that turns out to be novel even in the graph case. We also add to the mix the combinatorial property of finite duality and its logic counterpart, FO-definability, studied by Larose, Loten, and Tardif.

We find a set of generators of the variety of reflexive digraphs admitting $k-{NU}$ polymorphisms. We do this, in spite of the fact that such digraphs do not have finite tree duality, by defining finite duals of infinite trees. As a result of this, we answer a question of Quackenbush, Rival, and Rosenberg, giving a finite family of generators of the variety of finite bounded posets admitting $k-{NU}$ polymorphisms.

The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993). It has been verified for conservative problems (also known as list homomorphism problems) by A. Bulatov (2003). Egri et al. (SODA 2014) augmented this result by showing that for digraph templates H, every conservative CSP, denoted LHOM(H), is solvable in log space or is hard for NL. A conjecture of Larose and Tesson from 2007 forecasts that when LHOM(H) is in log space, then in fact, it falls in a small subclass of log space, the set of problems expressible in symmetric Data log. The present work verifies the conjecture for LHOM(H) (and, indeed, for the wider class of conservative CSPs with binary constraints), and by so doing sharpens the aforementioned dichotomy. A combinatorial characterization of symmetric Data log provides the language in which the algorithmic ideas of the paper, quite different from the ones in Egri et al., are formalized.

The Dichotomy Conjecture for constraint satisfaction problems (CSPs) states that every CSP is in P or is NP-complete (Feder-Vardi, 1993). It has been verified for conservative problems (also known as list homomorphism problems) by Bulatov (2003). We augment this result by showing that for digraph templates H, every conservative CSP, denoted LHOM(H), is solvable in logspace or is hard for NL. More precisely, we introduce a digraph structure we call a circular N, and prove the following dichotomy: if H contains no circular N then LHOM(H) admits a logspace algorithm, and otherwise LHOM(H) is hard for NL. Our algorithm operates by reducing the lists in a complex manner based on a novel decomposition of an auxiliary digraph, combined with repeated applications of Reingold's algorithm for undirected reachability (2005). We also prove an algebraic version of this dichotomy: the digraphs without a circular N are precisely those that admit a finite chain of conservative polymorphisms satisfying the Hagemann-Mitschke identities. This confirms a conjecture of Larose and Tesson (2007) for LHOM(H). Moreover, we show that the presence of a circular N can be decided in time polynomial in the size of H.

We describe a generating set for the variety of simple graphs that admit a $k$-ary near-unanimity (NU) polymorphism. The result follows from an analysis of NU polymorphisms of strongly bipartite digraphs, i.e., whose vertices are either a source or a sink. We show that the retraction problem for a strongly bipartite digraph ${\mathbb H}$ has finite duality if and only if ${\mathbb H}$ admits an NU polymorphism. This result allows the use of tree duals to generate the variety of digraphs admitting a $k$-NU polymorphism.

We describe a generating set for the variety of reflexive graphs that admit a compatible $k$-ary near-unanimity (NU) operation. We further delineate a very simple subset that generates the variety of $j$-absolute retracts; in particular we show that the class of reflexive graphs with a 4-NU operation coincides with the class of 3-absolute retracts. Our results generalize and encompass several results on NU-graphs and absolute retracts.

We completely classify the computational complexity of the list $\bH$-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph $\bH$ the problem is either NP-complete, NL-complete, L-complete or is first-order definable; descriptive complexity equivalents are given as well via Datalog and its fragments. Our algebraic characterisations match important conjectures in the study of constraint satisfaction problems.

Let B be a finite, core relational structure and let A be the algebra associated to B, i.e. whose terms are the operations on the universe of B that preserve the relations of B. We show that if A generates a so-called arithmetical variety then CSP(B), the constraint satisfaction problem associated to B, is solvable in Logspace; in fact notCSP(B) is expressible in symmetric Datalog. In particular, we obtain that notCSP(B) is expressible in Datalog and the relations of B are invariant under a Maltsev operation then notCSP(B) is in symmetric Datalog.

Recently, a strong link has been discovered between supermodularity on lattices and tractability of optimization problems known as maximum constraint satisfaction problems. This paper strengthens this link. We study the problem of maximizing a supermodular function which is defined on a product of n copies of a fixed finite lattice and given by an oracle. We exhibit a large class of finite lattices for which this problem can be solved in oracle-polynomial time in n. We also obtain new large classes of tractable maximum constraint satisfaction problems.

We introduce symmetric Datalog, a syntactic restriction of linear Datalog and show that its expressive power is exactly that of restricted symmetric Krom monotone SNP. The deep result of Reingold [17] on the complexity of undirected connectivity suffices to show that symmetric Datalog queries can be evaluated in logarithmic space. We show that for a number of constraint languages Gamma, the complement of the constraint satisfaction problem CSP(Gamma) can be expressed in symmetric Datalog. In particular, we show that if CSP(Gamma) is first-order definable and Lambda is a finite subset of the relational clone generated by Gamma then notCSP(Lambda) is definable in symmetric Datalog. Over the two-element domain and under standard complexity-theoretic assumptions, expressibility of notCSP(Gamma) in symmetric Datalog corresponds exactly to the class of CSPs computable in logarithmic space. Finally, we describe a fairly general subclass of implicational (or 0/1/all) constraints for which the complement of the corresponding CSP is also definable in symmetric Datalog. Our results provide preliminary evidence that symmetric Datalog may be a unifying explanation for families of CSPs lying in L.

We describe simple algebraic and combinatorial characterisations of finite relational core structures admitting finitely many obstructions. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores. A slight modification of this algorithm provides, for first-order definable CSP's, a simple poly-time algorithm to produce a solution when one exists. As an application of our algebraic characterisation of first order CSP's, we describe a large family of L-complete CSP's.

A retraction from a structure P to its substructure Q is a homomorphism from P onto Q that is the identity on Q. We present an algebraic condition which completely characterzies all posets and all reflexive graphs Q such that the class of all posets or reflexive graphs, respectively, that admit a retraction onto Q is first-order definable.

We characterise finite relational core structures admitting finitely many obstructions, in terms of special nearunanimity functions, and in terms of dismantling properties of their square. As a consequence, we show that it is decidable to determine whether a constraint satisfaction problem is first-order definable: we show the general problem to be NP-complete, and give a polynomial-time algorithm in the case of cores.

A retraction from a structure P to its substructure Q is a homomorphism from P onto Q that is the identity on Q. We present an algebraic condition which completely characterises all posets and all reflexive graphs Q with the following property: the class of all posets or reflexive graphs, respectively, that admit a retraction onto Q is first-order definable.

For a finite poset P let EXT(P) denote the following decision problem. Given a finite poset Q and a partial map f from Q to P, decide whether f extends to a monotone total map from Q to P. It is easy to see that EXT(P) is in the complexity class NP. In [SIAM J. Comput., 28 (1998), pp. 57-104], Feder and Vardi define the classes of width 1 and of bounded strict width constraint satisfaction problems for finite relational structures. Both classes belong to the broader class of bounded width problems in P. We prove that for any finite poset P, if EXT(P) has bounded strict width, then it has width 1. In other words, if a poset admits a near unanimity operation, it also admits a totally symmetric idempotent operation of any arity. In [Fund. Inform., 28 (1996), pp. 165-182], Pratt and Tiuryn proved that SAT(P), a polynomial-time equivalent of EXT(P) is NP-complete if P is a crown. We generalize Pratt and Tiuryn's result on crowns by proving that EXT(P), is NP-complete for any finite poset P which admits no nontrivial idempotent Malcev condition.