Metraipolis › archive › dc_e4cd0eee12f3
Acyclic orientations of mixed graphs — arXiv:2609.32403
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.32403
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T23:28:53.008Z
- SHA-256 of the archived text
717acae2e0704fb6df376d5f56c4d94c33b0d4023ed90388b194579ca31fd5a5- Stable URL of this page
https://metraipolis.com/documento/dc_e4cd0eee12f3
How to cite
Acyclic orientations of mixed graphs — arXiv:2609.32403 — arXiv (en), https://arxiv.org/abs/2609.32403 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e4cd0eee12f3 (Metraipolis archive dc_e4cd0eee12f3, sha256 717acae2e0704fb6df376d5f56c4d94c33b0d4023ed90388b194579ca31fd5a5)
BibTeX
@misc{dce4cd0eee12f3,
title = {Acyclic orientations of mixed graphs — arXiv:2609.32403},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.32403},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e4cd0eee12f3; sha256 717acae2e0704fb6df376d5f56c4d94c33b0d4023ed90388b194579ca31fd5a5},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.32403. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.32403 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:08:10.759Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).