Generalized completion problems with forbidden tournaments

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.

Subjects

completion problems

constraint satisfaction problems

homogeneous structures

polymorphisms

Tournaments

DDC Class

510: Mathematics

003: Systems Theory

Publication version

publishedVersion

Lizenz

https://creativecommons.org/licenses/by/4.0/

Name

LIPIcs.MFCS.2024.28.pdf

Type

Main Article

Size

745.53 KB

Format

Adobe PDF

Options

Generalized completion problems with forbidden tournaments