Forbidden Tournaments and the Orientation Completion Problem
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
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
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 170-205 |
| Seitenumfang | 36 |
| Fachzeitschrift | SIAM journal on discrete mathematics : a publ. of the Society for Industrial and Applied Mathematics |
| Jahrgang | 39 |
| Ausgabenummer | 1 |
| Publikationsstatus | Veröffentlicht - März 2025 |
| Peer-Review-Status | Ja |
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