Many computational problems can be modelled as the class of all finite structures A that satisfy a fixed first-order sentence ϕ hereditarily, i.e., we require that every (induced) substructure of A satisfies ϕ. We call the corresponding computational problem the hereditary model checking problem for ϕ, and denote it by Her(ϕ). We present a complete description of the quantifier prefixes for ϕ such that Her(ϕ) is in P; we show that for every other quantifier prefix there exists a formula ϕ with this prefix such that Her(ϕ) is coNP-complete. Specifically, we show that if Q is of the form ∀*∃∀* or of the form ∀*∃*, then Her(ϕ) can be solved in polynomial time whenever the quantifier prefix of ϕ is Q. Otherwise, Q contains ∃∃∀ or ∃∀∃ as a subword, and in this case, there is a first-order formula ϕ whose quantifier prefix is Q and Her(ϕ) is coNP-complete. Moreover, we show that there is no algorithm that decides for a given first-order formula ϕ whether Her(ϕ) is in P (unless P=NP).

Extensional ESO is a fragment of existential second-order logic (ESO) that captures the following family of problems. Given a fixed ESO sentence Ψ and an input structure A the task is to decide whether there is an extension B of A that satisfies the first-order part of Ψ, i.e., a structure B such that R^A ⊆ R^B for every existentially quantified predicate R of Ψ, and R^A = R^B for every non-quantified predicate R of Ψ. In particular, extensional ESO describes all pre-coloured finite-domain constraint satisfaction problems (CSPs). In this paper we study the computational power of extensional ESO; we ask, for which problems in NP is there a polynomial-time equivalent problem in extensional ESO? One of our main results states that extensional ESO has the same computational power as hereditary first-order logic. We also characterize the computational power of the fragment of extensional ESO with monotone universal first-order part in terms of finitely bounded CSPs. These results suggest a rich computational power of this logic, and we conjecture that extensional ESO captures NP-intermediate problems. We further support this conjecture by showing that extensional ESO can express current candidate NP-intermediate problems such as Graph Isomorphism, and Monotone Dualization (up to polynomial-time equivalence). On the other hand, another main result proves that extensional ESO does not have the full computational power of NP: there are problems in NP that are not polynomial-time equivalent to a problem in extensional ESP (unless E=NE).

In 2008, Bodirsky and Grohe showed that for every Π_n^P-level of the Polynomial Hierarchy (PH) there are ω-categorical Constraint Satisfaction Problems (CSPs) complete for this level. We show that, in fact, there are ω-categorical CSPs complete for any level of the PH. To this end, we use a recent result of Bodirsky, Knäuer, and Rudolph for constructing ω-categorical CSPs from sentences of Monadic Second-Order logic (MSO) with certain preservation properties. As a secondary contribution, we develop a new tool for producing MSO sentences satisfying said preservation properties.

The Sandwich Problem (SP) for a graph class \(\mathcal{C}\) is the following computational problem. The input is a pair of graphs \((V,E_1)\) and \((V,E_2)\) where \(E_1 \subseteq E_2\), and the task is to decide whether there is an edge set \(E\) where \(E_1 \subseteq E \subseteq E_2\) such that the graph \((V,E)\) belongs to \(\mathcal{C}\). In this paper we show that many SPs correspond to the constraint satisfaction problem (CSP) of an infinite 2-edge-coloured graph \(H\). We then notice that several known complexity results for SPs also follow from general complexity classifications of infinite-domain CSPs, suggesting a fruitful application of the theory of CSPs to complexity classifications of SPs. We strengthen this evidence by using basic tools from constraint satisfaction theory to propose new complexity results of the SP for several graph classes including line graphs of multigraphs, line graphs of bipartite multigraphs, \(K_k\)-free perfect graphs, and classes described by forbidding finitely many induced subgraphs, such as \(\{I_4,P_4\}\)-free graphs, settling an open problem of Alvarado, Dantas, and Rautenbach (2019). We also construct a graph sandwich problem which is in \(\mathrm{coNP}\), but neither in \(\mathrm{P}\) nor \(\mathrm{coNP}\)-complete (unless \(\mathrm{P}=\mathrm{coNP}\)).

In recent years, much attention has been placed on the complexity of graph homomorphism problems when the input is restricted to ℙ_k-free and ℙ_k-subgraph-free graphs. We consider the directed version of this research line, by addressing the question is it true that digraph homomorphism problems CSP(H) have a P versus NP-complete dichotomy when the input is restricted to ℙ→_k-free (resp. ℙ→_k-subgraph-free) digraphs? Our main contribution in this direction shows that if CSP(H) is NP-complete, then there is a positive integer N such that CSP(H) remains NP-hard even for ℙ→_N-subgraph-free digraphs. Moreover, CSP(H) becomes polynomial-time solvable for ℙ→_{N-1}-subgraph-free acyclic digraphs. We then verify the questions above for digraphs on three vertices and a family of smooth tournaments. We prove these results by establishing a connection between F-(subgraph)-free algorithmics and constraint satisfaction theory. On the way, we introduce restricted CSPs, i.e., problems of the form CSP(H) restricted to yes-instances of CSP(H') - these were called restricted homomorphism problems by Hell and Nešetřil. Another main result of this paper presents a P versus NP-complete dichotomy for these problems. Moreover, this complexity dichotomy is accompanied by an algebraic dichotomy in the spirit of the finite domain CSP dichotomy.

Abstract. For a fixed finite set of finite tournaments [Formula: see text], the [Formula: see text] -free orientation problem asks whether a given finite undirected graph [Formula: see text] has an [Formula: see text] -free orientation, i.e., whether the edges of [Formula: see text] can be oriented so that the resulting digraph does not embed any of the tournaments from [Formula: see text]. We prove that for every [Formula: see text] this problem is in P or NP-complete. Our proof reduces the classification task to a complete complexity classification of the orientation completion problem for [Formula: see text], which is the variant of the problem above where the input is a directed graph instead of an undirected graph, introduced by Bang-Jensen, Huang, and Zhu [ J. Graph Theory, 87 (2018), pp. 285–304]. Our proof uses results from the theory of constraint satisfaction and a result of Agarwal and Kompatscher [ J. Symb. Log., 83 (2018), pp. 395–415] about infinite permutation groups and transformation monoids.