Dichotomy for orderings?

Fagin defined the class N P by the means of Existential Second-Order logic. Feder and Vardi expressed it (up to polynomial equivalence) by special fragments of Existential Second-Order logic (SNP), while the authors used forbidden expanded substructures (cf. lifts and shadows). Consequently, for such problems there is no dichotomy, unlike for CSPs.

We prove that ordering problems for graphs defined by finitely many forbidden ordered subgraphs capture the full power of the class N P , that is, any language in the class N P is polynomially equivalent to an ordering problem. In particular, we refute a conjecture of Hell, Mohar and Rafiey that dichotomy holds for this class. On the positive side, we confirm the conjecture of Duffus, Ginn and Rödl that ordering problems defined by a single obstruction which is a biconnected ordered graph are N P -complete if the graph is not complete.

We initiate the study of meta-theorems for classes which have the full power of the class N P . For example, homomorphism problems (or CSPs) do not have full power (similarly to coloring problems). On the other hand, we show that problems defined by the existence of an ordering, which avoids certain ordered patterns, have full power. We find it surprising that such simple structures can express the full power of N P .

It is essential that we treat these problems in a more general context. An interesting feature appeared: while the full power is reached by disconnected structures, and one can even guarantee the connectivity of all patterns, this is no longer the case for biconnected patterns. We prove that we have here a general phenomenon: For finite sets of biconnected patterns (which may be colored structures or ordered structures) dichotomy holds, while for general patterns we have full power. A principal tool for obtaining these results is the Sparse Incomparability Lemma in many of its variants, which are classical results in the theory of homomorphisms of graphs and structures. We prove it here in the setting of ordered stuctures as a Temporal Sparse Incomparability Lemma. This is a non-trivial result, even in the random setting, and a deterministic algorithm requires more effort. Interestingly, our proof involves the Lovász Local Lemma.

Dichotomy results for forbidden biconnected patterns encourage to prove that the ordering problem for any non-trivial biconnected graph is N P -complete (as conjectured by Duffus, Ginn and Rödl). We confirm this by bringing together most of the techniques developed in the paper, and we also use the results of Bodirsky and Kára on the complexity of temporal CSPs.