Acyclic orientations of mixed graphs

Abstract

A mixed graph M=(V,E∪ 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 has both an out-branching and an in-branching (a bipolar orientation). We show that it is NP-complete to decide whether M can be oriented so that it contains a directed path between two prescribed vertices. Finally we describe a polynomial algorithm for deciding whether an acyclic digraph D has an out-branching B⁺_s such that the digraph D−A(B⁺_s) is connected (in the underlying sense). Based on this we pose as an open problem the complexity of deciding whether the edges of an acyclic mixed graph can be oriented so that the result is an acyclic digraph with a non-separating out-branching.

Hamiltonicity of graphs of acyclic orientations and acyclic polynomials
Leonie Mühlherr, Germain Poullot
arXiv17 Sep 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs
Hanzhi Bai, Jørgen Bang-Jensen, Jin Yan
arXiv21 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
An improved randomized algorithm for finding sinks of Acyclic Unique Sink Orientations of the binary hypercube
Thomas Dueholm Hansen, Uri Zwick
arXiv15 Oct 2026PreprintarXiv licenceFull textOptimisation & controlarXiv
Modulo k-orientations of highly edge-connected signed graphs
You Lu, Zhengke Miao, Zhenyu Tian +1
arXiv30 Oct 2026PreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
Chains and unique transitive orientations of prime graphs
Robert Brignall, Sean Mandrick, Vincent Vatter
arXiv7 Sep 2026PreprintCC0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{bangjensen2026acyclic,
  title = {{Acyclic orientations of mixed graphs}},
  author = {Jørgen Bang-Jensen and Anders Yeo},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.32403},
  eprint = {2609.32403},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.32403},
  note = {CC BY-NC-ND 4.0},
}

RIS

TY  - UNPB
TI  - Acyclic orientations of mixed graphs
AU  - Jørgen Bang-Jensen
AU  - Anders Yeo
PY  - 2026
DA  - 2026/09/26
PB  - arXiv
DO  - 10.48550/arxiv.2609.32403
UR  - https://arxiv.org/abs/2609.32403
AB  - A mixed graph M=(V,E∪ 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 has both an out-branching and an in-branching (a bipolar orientation). We show that it is NP-complete to decide whether M can be oriented so that it contains a directed path between two prescribed vertices. Finally we describe a polynomial algorithm for deciding whether an acyclic digraph D has an out-branching B^+_s such that the digraph D−A(B^+_s) is connected (in the underlying sense). Based on this we pose as an open problem the complexity of deciding whether the edges of an acyclic mixed graph can be oriented so that the result is an acyclic digraph with a non-separating out-branching.
ER  -

Abstract

Related

Cite