Acyclic orientation with connectivity prescriptions

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

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

Remarks

The following related problems are solved. Given an undirected graph [math]\displaystyle G=(V,E)[/math] 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 [math]\displaystyle k[/math] 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 [math]\displaystyle v\in V\setminus\{s,t\}[/math] has indegree at least [math]\displaystyle k[/math] and at most [math]\displaystyle d(v)-k.[/math] 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 [math]\displaystyle k[/math] terminals should be settled).

See also

Acyclic orientation with parity constraints.