Indian Computing Olympiad

Training Material


Network Flows→Evil Intentions (IOITC 2005)

Tanmoy is searching for some special directed graphs so that he can force 90% of the submissions to time out. For each graph, his test data generator requires the vertices v1,v2,…,vN to have indegrees i1,i2,…,iN and outdegrees o1,o2,…,oN.

For instance, suppose the sequence of indegrees required is 0,1,2,2 and the sequence of outdegrees required is 2,1,1,1. Here is a graph with the required properties.

              v1------> v3
                 \   /  ^
                   X    |
                  / \   |
                <-   -> |
              v2 -----> v4
      

Your task is to help him construct a graph that meets his requirements or report that no such graph exists, so Tanmoy has to find another way to achieve his evil goal.

Solution

Take two copies of vertices {v1,v2,...,vn} and {v'1,v'2,...,v'n} and construct a bipartite graph where you connect vi to v'j for all j not equal to i. as a complete bipartite graph, add a source and sink and put capacities as follows:

  • source → vi : capacity is outdegree(i)
  • vi → sink : capacity is indegree(i)
  • vi → vj' : capacity is 1
            --- v1--      v'1 ---
 outdeg(1) /      \ \\ 1         \  indeg(1)
          / --- v2 \ \ -- v'2 --- \
         / /        \ \ 1        \ \
   source ----- v3   \ -- v'3 ------ sink
         \           1\            /
          \     ...    \  ...     /
 outdeg(n) \            \       /  indeg(n)
            --- vn        v'n --
      

Want a solution to maxflow = i1+i2+...in = o1+o2+...+on. (If these sums are not the same, there is no solution.)

If we find such a flow, the edges with flow 1 between vi and v'j define the graph you want.

Conversely, if there is a graph of the type you want, there will be a max flow as described.