Bitter, ZenoZenoBitterMottet, AntoineAntoineMottet2024-09-172024-09-172024-08-2349th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)9783959773355https://hdl.handle.net/11420/49110A 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.enhttps://creativecommons.org/licenses/by/4.0/completion problemsconstraint satisfaction problemshomogeneous structurespolymorphismsTournamentsNatural Sciences and Mathematics::510: MathematicsComputer Science, Information and General Works::003: Systems TheoryConference Paper10.15480/882.1330310.4230/LIPIcs.MFCS.2024.2810.15480/882.13303Conference Paper