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.