{"id":"arxiv/2609.32403","url":"https://arxiv.org/abs/2609.32403","tags":["math.CO","cs.DM"],"score":0,"title":"Acyclic orientations of mixed graphs","domain":"math.CO","source":"arxiv","authors":["Jørgen Bang-Jensen","Anders Yeo"],"reviews":0,"subject":"math.CO","summary":"A mixed graph $M=(V,E\\cup A)$ is acyclic if its directed part $(V,A)$ is an acyclic digraph. In this note we study the so-called orientation completion problem for the class of acyclic mixed graphs. That is, given an acyclic mixed graph $M$ and a property ${\\cal P}$; can we orient the edges of $M$ so that the resulting digraph is acyclic and has property ${\\cal P}$. We prove that one can decide in polynomial time whether $M$ can be completed to an acyclic digraph with an out-branching from a prescibed vertex $s$, while it is NP-complete to decide whether $M$ has an acyclic orientation which…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-26","reactions":{}}