Given n pair of integer (di, dj), e.g. (0, 2), (1, 1), (1, 0), (1, 0)... Construct a directed graph G = ({1...n}, E) such that in-degree of vertex 1 is di and out-degree is dj. Is it possible to reduce this problem to max flow problem?
In other words, using idea to Ford–Fulkerson to solve this problem.
Thank you!
On
If I'm not mistaken, it is indeed possible to reduce it to a max flow problem, try this:
Make two sets of vertices $N_1$ and $N_2$. Each of these sets will contain all of the vertices you are given (they will have all $n$ vertices). Set a source $s$ and connect it to each vertex in $N_1$ with capacity $d_{in}(v)$ and a sink $t$ connected to each vertex $v$ with capacity $d_{out}(v)$.
Now connect every vertex $v_i \in N_1$ to every other vertex $v_j \in N_2$, where $i \neq j$ with capacity $d_{out}(v_i)$, since you want to find a way to distribute $d_{out}(v_i)$ accross all other nodes in the graph.
Now run any algorithm to compute the max flow in this digraph. If the result $F = \sum_{i=1}^{n}d_{in}(v_i) = \sum_{i=1}^{n}d_{out}(v_i)$ then it is possible to construct the directed graph you are looking for, otherwise there is no solution to your problem.
Notice that the property $\sum_{i=1}^{n}d_{in}(v_i) = \sum_{i=1}^{n}d_{out}(v_i)$ is a necessary condition stated in https://en.wikipedia.org/wiki/Fulkerson%E2%80%93Chen%E2%80%93Anstee_theorem.
This is known as the digraph realization problem.
As far as I know, there is two solutions, none of which involve max flow.
To figure out whether the given set $(a_i, b_i)$ is valid, you can use the sufficiency/necessary conditions from the Fulkerson–Chen–Anstee theorem
For an actual constructive algorithm, you can use the Kleitman–Wang algorithms (There are two variants of the algorithm, but essentially both use a similar idea. I also believe you can show that a set is invalid with the algorithm. )