Restricted CSPs and F-free Digraph Algorithmics

In recent years, much attention has been placed on the complexity of graph homomorphism problems when the input is restricted to Pₖ-free and Pₖ-subgraph-free graphs. We consider the directed version of this research line, by addressing the questions, is it true that digraph homomorphism problems CSP (H) have a P versus NP-complete dichotomy when the input is restricted to Pₖ-free (resp. \ Pₖ-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 PN-subgraph-free digraphs. Moreover, it remains NP-hard for acyclic PN-subgraph-free digraphs, and becomes polynomial-time solvable for P₍-₁-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 Nesetril. 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.