# Acyclic orientation with connectivity prescriptions

Problem 1. Given an undirected graph $\displaystyle G=(V,E)$ and $\displaystyle s,t\in V,\;\; k\in N$, decide whether the graph has an acyclic orientation, so that for every vertex $\displaystyle v\in V\setminus\{s,t\}$,   there are $\displaystyle k$ pairwise edge-disjoint directed paths from $\displaystyle s$ to $\displaystyle v$, and also $\displaystyle k$ pairwise edge-disjoint directed paths from $\displaystyle v$ to $\displaystyle t$.

Problem 2. Given an undirected graph $\displaystyle G=(V,E)$ and $\displaystyle s, t_1, t_2\in V,\;\; k\in N$, decide whether the graph has an acyclic orientation, so that there are $\displaystyle k$ pairwise edge-disjoint directed paths from $\displaystyle s$ to $\displaystyle t_1$, and also $\displaystyle k$ pairwise edge-disjoint directed paths from $\displaystyle s$ to $\displaystyle t_2$.

## Remarks

The following related problems are solved. Given an undirected graph $\displaystyle G=(V,E)$ and indegree-prescription at each vertex, decide whether the graph has an acyclic orientation, so that every vertex has the prescribed indegree (this is in P). If instead of exact indegree-prescription we have lower bounds on the indegrees, the problem is also polynomial, as well as deciding whether the graph has rooted $\displaystyle k$ edge-connected acyclic orientation. But for both upper and lower bounds on the indegrees, it is NP-complete (reduction from Vertex Cover by Z. Király).

Problem 1 is equivalent to saying that we are looking for an acyclic orientation where every $\displaystyle v\in V\setminus\{s,t\}$ has indegree at least $\displaystyle k$ and at most $\displaystyle d(v)-k.$ Problem 2 is related to Network Coding, where usually the underlying graph is undirected, but simple Network Codes work on acyclic directed graphs (of course the more general problem for $\displaystyle k$ terminals should be settled).