1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.