2026-07-21T23:34:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23535 2025-10-02T12:58:03Z ddc:004 open_access

Restricted CSPs and F-Free Digraph Algorithmics Guzmán-Pro, Santiago Martin, Barnaby Digraph homomorphisms constraint satisfaction problems subgraph-free algorithmics 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Santiago Guzmán-Pro and Barnaby Martin 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.158 urn:nbn:de:0030-drops-235352 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.158 eng https://creativecommons.org/licenses/by/4.0/legalcode