{"id":"arxiv/2608.28654","url":"https://arxiv.org/abs/2608.28654","tags":["cs.CC","cs.DM","math.CO","q-bio.PE"],"score":0,"title":"Orientations without transitive arcs for cubic graphs and phylogenetic networks","domain":"cs.CC","source":"arxiv","authors":["Janosch Döcker","Simone Linz"],"reviews":0,"subject":"cs.CC","summary":"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.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-20","reactions":{}}