Forbidden Tournaments and the Orientation Completion Problem
Manuel Bodirsky, Santiago Guzmán‐Pro · SIAM Journal on Discrete Mathematics · 2025
Abstract. For a fixed finite set of finite tournaments [Formula: see text], the [Formula: see text] -free orientation problem asks whether a given finite undirected graph [Formula: see text] has an [Formula: see text] -free orientation, i.e., whether the edges of [Formula: see text] can be oriented so that the resulting digraph does not embed any of the tournaments from [Formula: see text]. We prove that for every [Formula: see text] this problem is in P or NP-complete. Our proof reduces the classification task to a complete complexity classification of the orientation completion problem for [Formula: see text], which is the variant of the problem above where the input is a directed graph instead of an undirected graph, introduced by Bang-Jensen, Huang, and Zhu [ J. Graph Theory, 87 (2018), pp. 285–304]. Our proof uses results from the theory of constraint satisfaction and a result of Agarwal and Kompatscher [ J. Symb. Log., 83 (2018), pp. 395–415] about infinite permutation groups and transformation monoids.