Complexity results for orienting acyclic mixed graphs with branching paths
Acyclic orientations of mixed graphs
Discrete Mathematics
Summary
The authors studied how to give directions to undirected edges in mixed graphs that already have some directions, without creating loops. They found ways to tell quickly if a graph can be directed to have a certain kind of tree with paths starting from a specific point. But they also showed that figuring out if the graph can have more complex structures like trees branching in both directions or paths between two chosen points is much harder. Lastly, they gave a method for checking a certain connectivity property related to those branchings and posed a question about its complexity.
What this means in practice
- •For network designers: Decide efficiently if a network diagram can be oriented to have a single root node with outward flow without cycles.
- •For routing protocol developers: Understand limits on automatically orienting network edges to enable guaranteed paths between nodes, informing protocol design.
A theory result. No direct application yet.
Authors
Jørgen Bang-Jensen, Anders Yeo
Abstract
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.