2026-07-26T03:03:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20584 2024-08-23T05:50:28Z ddc:004 open_access

Generalized Completion Problems with Forbidden Tournaments Bitter, Zeno Mottet, Antoine Tournaments completion problems constraint satisfaction problems homogeneous structures polymorphisms A recent result by Bodirsky and Guzmán-Pro gives a complexity dichotomy for the following class of computational problems, parametrized by a finite family F of finite tournaments: given an undirected graph, does there exist an orientation of the graph that avoids every tournament in F? One can see the edges of the input graphs as constraints imposing to find an orientation. In this paper, we consider a more general version of this problem where the constraints in the input are not necessarily about pairs of variables and impose local constraints on the global oriented graph to be found. Our main result is a complexity dichotomy for such problems, as well as a classification of such problems where the yes-instances have bounded treewidth duality. As a consequence, we obtain a streamlined proof of the result by Bodirsky and Guzmán-Pro using the theory of smooth approximations due to Mottet and Pinsker. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zeno Bitter and Antoine Mottet 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.28 urn:nbn:de:0030-drops-205844 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.28 eng https://creativecommons.org/licenses/by/4.0/legalcode