2025/02/24 by Guzmán-Pro, Santiago, Martin, Barnaby
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2502.17596
In recent years, much attention has been placed on the complexity of graph homomorphism problems when the input is restricted to \mathbb Pk-free and \mathbb Pk-subgraph-free graphs. We consider the directed version of this research line, by addressing the questions, is it true that digraph homomorphism problems CSP(\mathbb H) have a P versus NP-complete dichotomy when the input is restricted to \mathbb Pk-free (resp. \mathbb Pk-subgraph-free) digraphs? Our main contribution in this direction shows that if CSP(\mathbb H) is NP-complete, then there is a positive integer N such that CSP(\mathbb H) remains NP-hard even for \mathbb PN-subgraph-free digraphs. Moreover, it remains NP-hard for acyclic \mathbb PN-subgraph-free digraphs, and becomes polynomial-time solvable for \mathbb PN-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 \mathbb F-(subgraph)-free algorithmics and constraint satisfaction theory. On the way, we introduce restricted CSPs, i.e., problems of the form CSP(\mathbb H) restricted to yes-instances of CSP(\mathbb 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.