Orientations without transitive arcs for cubic graphs and phylogenetic networks
Abstract
An st-orientation of an undirected graph G is an acyclic digraph with a single source s and a single sink t that can be obtained from G by assigning a direction to each edge. The classical problem of deciding if an undirected graph G has an st-orientation can be solved efficiently. On the other hand, deciding if an st-orientation of G exists that does not have any transitive arc is NP-complete, even if each vertex of G has degree at most four. Here we show that this last decision problem remains NP-complete if G is cubic, which settles an open question by Binucci et al. (2025). We obtain NP-completeness for two variants of the problem: (i) s and t are fixed and given as part of the input and (ii) s and t can be chosen freely. We then use these results to investigate the computational complexity of a problem that arises in computational evolution. Specifically, we show that the problem of deciding if an unrooted binary phylogenetic network has an orientation as a rooted binary phylogenetic network without any shortcuts (the analog of a transitive arcs in phylogenetics) is NP-complete. Our results connect the two (mostly) distinct research areas of orienting undirected graphs and orienting unrooted phylogenetic networks.
Related
- Best Matches in Phylogenetic Networks
- Exact Counts of Binary Phylogenetic Networks with Four Reticulations
- The nearest neighbor interchange proximity measure for the tree-basedness of rooted binary phylogenetic networks
- The parental parsimony problem on binary, tree-child phylogenetic networks
- An explicit birth-death-reticulation model for studying the diversification of phylogenetic networks
BibTeX
@misc{docker2026orientations,
title = {{Orientations without transitive arcs for cubic graphs and phylogenetic networks}},
author = {Janosch Döcker and Simone Linz},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.28654},
eprint = {2608.28654},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.28654},
}
RIS
TY - UNPB
TI - Orientations without transitive arcs for cubic graphs and phylogenetic networks
AU - Janosch Döcker
AU - Simone Linz
PY - 2026
DA - 2026/08/20
PB - arXiv
DO - 10.48550/arxiv.2608.28654
UR - https://arxiv.org/abs/2608.28654
AB - An st-orientation of an undirected graph G is an acyclic digraph with a single source s and a single sink t that can be obtained from G by assigning a direction to each edge. The classical problem of deciding if an undirected graph G has an st-orientation can be solved efficiently. On the other hand, deciding if an st-orientation of G exists that does not have any transitive arc is NP-complete, even if each vertex of G has degree at most four. Here we show that this last decision problem remains NP-complete if G is cubic, which settles an open question by Binucci et al. (2025). We obtain NP-completeness for two variants of the problem: (i) s and t are fixed and given as part of the input and (ii) s and t can be chosen freely. We then use these results to investigate the computational complexity of a problem that arises in computational evolution. Specifically, we show that the problem of deciding if an unrooted binary phylogenetic network has an orientation as a rooted binary phylogenetic network without any shortcuts (the analog of a transitive arcs in phylogenetics) is NP-complete. Our results connect the two (mostly) distinct research areas of orienting undirected graphs and orienting unrooted phylogenetic networks.
ER -