Forbidden Tournaments and the Orientation Completion Problem

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Abstract

For a fixed finite set of finite tournaments F, the F-free orientation problem asks whether a given finite undirected graph G has an F-free orientation, i.e., whether the edges of G can be oriented so that the resulting digraph does not embed any of the tournaments from F. We prove that for every F 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 F, 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.

Details

OriginalspracheEnglisch
Seiten (von - bis)170-205
Seitenumfang36
FachzeitschriftSIAM journal on discrete mathematics : a publ. of the Society for Industrial and Applied Mathematics
Jahrgang39
Ausgabenummer1
PublikationsstatusVeröffentlicht - März 2025
Peer-Review-StatusJa

Externe IDs

Scopus 105001291688
ORCID /0000-0001-8228-3611/work/187993422

Schlagworte

ASJC Scopus Sachgebiete

Schlagwörter

  • homomorphisms, orientations with forbidden patterns, infinite graphs, computational complexity