Forbidden Tournaments and the Orientation Completion Problem
Research output: Preprint/Documentation/Report › Preprint
Contributors
Abstract
For a fixed finite set of finite tournaments ${\mathcal F}$, the ${\mathcal F}$-free orientation problem asks whether a given finite undirected graph $G$ has an $\mathcal 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 ${\mathcal F}$. We prove that for every ${\mathcal 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 ${\mathcal 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 (2017). Our proof uses results from the theory of constraint satisfaction, and a result of Agarwal and Kompatscher (2018) about infinite permutation groups and transformation monoids.
Details
Original language | English |
---|---|
Publication status | Published - 15 Sept 2023 |
No renderer: customAssociatesEventsRenderPortal,dk.atira.pure.api.shared.model.researchoutput.WorkingPaper
External IDs
ORCID | /0000-0001-8228-3611/work/148606027 |
---|---|
dblp | journals/corr/abs-2309-08327 |
Keywords
Keywords
- math.CO, cs.CC, math.LO, 05C60 (Primary) 03C98 (Secondary)