# 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.