In this work we take a step towards characterising strongly flip-flat classes of graphs. Strong flip-flatness appears to be the analogue of uniform almost-wideness in the setting of dense classes of graphs. We prove that strongly flip-flat classes of graphs that are weakly sparse are indeed uniformly almost-wide.

Feder and Vardi showed that the class Monotone Monadic SNP without inequality (MMSNP) has a P vs NP-complete dichotomy if and only if such a dichotomy holds for finite-domain Constraint Satisfaction Problems (CSPs). Moreover, they showed that none of the three classes obtained by removing one of the defining properties of MMSNP (monotonicity, monadicity, no inequality) has a dichotomy. The overall objective of this paper is to study the gaps between MMSNP and each of these three superclasses, where the existence of a dichotomy remains unknown. For the gap between MMSNP and Monotone SNP without inequality, we study the class Guarded Monotone SNP without inequality (GMSNP) introduced by Bienvenu, ten Cate, Lutz, and Wolter, and prove that GMSNP has a dichotomy if and only if a dichotomy holds for GMSNP problems over signatures consisting of a unique relation symbol. For the gap between MMSNP and MMSNP with inequality, we introduce a new class MMSNP with guarded inequality, that lies between MMSNP and MMSNP with inequality and that is strictly more expressive than the former and still has a dichotomy. For the gap between MMSNP and Monadic SNP without inequality, we introduce a logic that extends the class of Matrix Partitions in a similar way how MMSNP extends finite-domain CSP, and pose an open question about the existence of a dichotomy for this class. Finally, we revisit the theorem of Feder and Vardi, which claims that the class NP embeds into MMSNP with inequality. We give a detailed proof of this theorem as it ensures no dichotomy for the right-hand side class of each of the three gaps.

Let 𝔸 be an idempotent algebra on a finite domain. By mediating between results of Chen [ 1 ] and Zhuk [ 2 ], we argue that if 𝔸 satisfies the polynomially generated powers property (PGP) and ℬ is a constraint language invariant under 𝔸 (i.e., in Inv(𝔸)), then QCSP ℬ is in NP. In doing this, we study the special forms of PGP, switchability, and collapsibility, in detail, both algebraically and logically, addressing various questions such as decidability on the way. We then prove a complexity-theoretic converse in the case of infinite constraint languages encoded in propositional logic, that if Inv}(𝔸) satisfies the exponentially generated powers property (EGP), then QCSP (Inv(𝔸)) is co-NP-hard. Since Zhuk proved that only PGP and EGP are possible, we derive a full dichotomy for the QCSP, justifying what we term the Revised Chen Conjecture . This result becomes more significant now that the original Chen Conjecture (see [ 3 ]) is known to be false [ 4 ]. Switchability was introduced by Chen [ 1 ] as a generalization of the already-known collapsibility [ 5 ]. There, an algebra 𝔸 :=({ 0,1,2}; r ) was given that is switchable and not collapsible. We prove that, for all finite subsets Δ of Inv (𝔸 A), Pol (Δ) is collapsible. The significance of this is that, for QCSP on finite structures, it is still possible all QCSP tractability (in NP) explained by switchability is already explained by collapsibility. At least, no counterexample is known to this.

The logic MMSNP is a restricted fragment of existential second-order logic which can express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi, who showed that every MMSNP sentence is computationally equivalent to a finite-domain constraint satisfaction problem (CSP); the involved probabilistic reductions were derandomized by Kun using explicit constructions of expander structures. We present a new proof of the reduction to finite-domain CSPs that does not rely on the results of Kun. The new universal-algebraic proof allows us to obtain a stronger statement and to verify the more general Bodirsky--Pinsker dichotomy conjecture for CSPs in MMSNP. Our approach uses the fact that every MMSNP sentence describes a finite union of CSPs for countably infinite $\omega$-categorical structures; moreover, by a recent result of Hubička and Nešetřil, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property.

The logic MMSNP is a restricted fragment of existential second-order logic which allows to express many interesting queries in graph theory and finite model theory. The logic was introduced by Feder and Vardi who showed that every MMSNP sentence is computationally equivalent to a finite-domain constraint satisfaction problem (CSP); the involved probabilistic reductions were derandomized by Kun using explicit constructions of expander structures. We present a new proof of the reduction to finite-domain CSPs that does not rely on the results of Kun. This new proof allows us to obtain a stronger statement and to verify the Bodirsky-Pinsker dichotomy conjecture for CSPs in MMSNP. Our approach uses the fact that every MMSNP sentence describes a finite union of CSPs for countably infinite ω-categorical structures; moreover, by a recent result of Hubička and Nešetřil, these structures can be expanded to homogeneous structures with finite relational signature and the Ramsey property. This allows us to use the universal-algebraic approach to study the computational complexity of MMSNP.

We apply the algebraic approach for Constraint Satisfaction Problems (CSPs) with counting quantifiers, developed by Bulatov and Hedayaty, for the first time to obtain classifications for computational complexity. We develop the consistency approach for expanding polymorphisms to deduce that, if H has an expanding majority polymorphism, then the corresponding CSP with counting quantifiers is tractable. We elaborate some applications of our result, in particular deriving a complexity classification for partially reflexive graphs endowed with all unary relations. For each such structure, either the corresponding CSP with counting quantifiers is in P, or it is NP-hard.

The complexity of the model checking problem for various fragments of first-order logic (FO) has attracted much attention over the last two decades, in particular for the fragment induced by $\exists$ and $\wedge$ and that induced by $\forall, \exists$, and $\wedge$, which are better known as the constraint satisfaction problem and the quantified constraint satisfaction problem, respectively. The former was conjectured to follow a dichotomy between P and NP-complete by Feder and Vardi [ SIAM J. Comput., 28 (1998), pp. 57--104]. For the latter, there are several partial trichotomy results between P, NP-complete, and Pspace-complete, and Chen [ Meditations on quantified constraint satisfaction, in Logic and Program Semantics, Springer, Heidelberg, 2012, pp. 35--49] ventured a conjecture regarding Pspace-completeness vs. membership in NP in the presence of constants. We give a comprehensive account of the whole field of the complexity of model checking similar syntactic fragments of FO. The above two fragments are in fact the only ones for which there is currently no known complexity classification. Indeed, we consider all other similar syntactic fragments of FO, induced by the presence or absence of quantifiers and connectives, and fully classify the complexities of the parameterization of the model-checking problem by a finite model $\mathcal{D}$, that is, the expression complexities for certain finite $\mathcal{D}$. Perhaps surprisingly, we show that for most of these fragments, “tractability” is witnessed by a generic solving algorithm which uses quantifier relativization. Our classification methodology relies on tailoring suitably the algebraic approach pioneered by Jeavons, Cohen, and Gyssens [ J. ACM, 44 (1997), pp. 527--548] for the constraint satisfaction problem and by Börner et al. [ Inform. and Comput., 207 (2009), pp. 923--944] for the quantified constraint satisfaction problem. Most fragments under consideration can be relatively easily classified, either directly or using Schaefer's dichotomy theorems for SAT and QSAT, with the notable exception of the positive equality-free fragment induced by $\exists,\forall, \wedge$, and $\vee$. This outstanding fragment can also be classified and enjoys a tetrachotomy: according to the model, the corresponding model checking problem is either tractable, NP-complete, co-NP-complete, or Pspace-complete.

Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idem potent polymorphisms of certain digraph classes. Our first results are two algebraic dichotomy, even "gap", theorems. Building on and extending [Martin CP'11], we prove that partially reflexive paths bequeath a set of idem potent polymorphisms whose associated clone algebra has: either the polynomially generated powers property (PGP), or the exponentially generated powers property (EGP). Similarly, we build on [DaMM ICALP'14] to prove that semi complete digraphs have the same property. These gap theorems are further motivated by new evidence that PGP could be the algebraic explanation that a QCSP is in NP even for unbounded alternation. Along the way we also effect a study of a concrete form of PGP known as collapsibility, tying together the algebraic and structural threads from [Chen Sicomp'08], and show that collapsibility is equivalent to its Pi2-restriction. We also give a decision procedure for k-collapsibility from a singleton source of a finite structure (a form of collapsibility which covers all known examples of PGP for finite structures). Finally, we present a new QCSP trichotomy result, for partially reflexive paths with constants. Without constants it is known these QCSPs are either in NL or Pspace-complete [Martin CP'11], but we prove that with constants they attain the three complexities NL, NP-complete and Pspace-complete.

We initiate the study of constraint satisfaction problems (CSPs) in the presence of counting quantifiers $\exists^{\geq j}$ which assert the existence of at least $j$ elements such that the ensuing property holds. These are natural variants of CSPs in the mould of quantified CSPs (QCSPs). Namely, $\exists^{\geq 1}:=\exists$ and $\exists^{\geq n}:=\forall$ (for the domain of size $n$). We observe that a single counting quantifier $\exists^{\geq j}$ strictly between $\exists$ and $\forall$ already affords the maximal possible complexity of QCSPs (which have both $\exists$ and $\forall$), namely, being Pspace-complete for a suitably chosen template. Therefore, to better understand the complexity of this problem, we focus on restricted cases for which we derive the following results. First, for all subsets of counting quantifiers on clique and cycle templates, we give a full trichotomy---all such problems are in P, NP-complete, or Pspace-complete. Second, we consider the problem with exactly two quantifiers: $\exists^{\geq 1}:=\exists$ and $\exists^{\geq j}$ ($j \neq 1$). Such a CSP is already NP-hard on nonbipartite graph templates. We explore the situation of this generalized CSP on graph templates, giving various conditions for both tractability and hardness. For quantifiers $\exists^{\geq 1}$ and $\exists^{\geq 2}$, we give a dichotomy for all graphs, namely, the problem is NP-hard if the graph contains a triangle or has girth at least 5, and is in P otherwise. We strengthen this result in the following two ways. For bipartite graphs, the problem is in P for forests and graphs of girth 4, and is Pspace-hard otherwise. For complete multipartite graphs, the problem is in L, NP-complete, or Pspace-complete. Finally, using counting quantifiers we solve the complexity of a concrete QCSP whose complexity was previously open.

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 nonuniform quantified constraint satisfaction problem QCSP( B ). We introduce surjective hyper-endomorphisms and use them in proving a Galois connection that characterizes 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 either is in L, is NP-complete, is co-NP-complete, or is Pspace-complete.

Let u and v be any two given nodes in a k-ary n-cube Qnkwith at most 2n-2 faulty edges. Suppose that the number of healthy links incident with u is no more than that of v, and denote this number by m. In this paper, we show that there are m mutually node-disjoint paths between u and v.

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 structures: each problem is either in L, is NP-complete, is co-NP-complete or is P space-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.

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 subjective 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 Logspace, is NP-complete, is coNP-complete or is Pspace-complete.

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 1990s, Feder and Vardi attempted to find a large subclass of NP which exhibits a dichotomy, that is, where every problem in the subclass is either solvable in polynomial‐time or NP‐complete. Their studies resulted in a candidate class of problems, namely, those definable in the logic MMSNP. While it remains open as to whether MMSNP exhibits a dichotomy, for various reasons it remains a strong candidate. Feder and Vardi added to the significance of MMSNP by proving that, although MMSNP strictly contains CSP, the class of constraint satisfaction problems, MMSNP and CSP are computationally equivalent. We introduce here a new class of combinatorial problems, the class of forbidden patterns problems FPP, and characterize MMSNP as the finite unions of problems from FPP. We use our characterization to detail exactly those problems that are in MMSNP but not in CSP. Furthermore, given a problem in MMSNP, we are able to 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 counterexample (again, this process is effective).