PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
Approach Taken:
This can be solved via network flow. First, say we have already verified the trivial condition that the total fraction is |V|-1. For the moment, fix two nodes u and v. Construct the following directed graph H on node set V. Use the following notation. For a node a let f(a) denote the total fraction assigned to edges having a as an endpoint. For a set S let f(S) denote the total fraction assigned to edges having both endpoints in S. Finally, for a set S let f*(S) denote the total fraction assigned of edges having exactly one endpoint in S.
- For each edge (a,b) of the original graph with value f(a,b) add two opposing directed arcs each with capacity f(a,b)/2
- For each node a in V{u,v}, add a directed arc from a to v with capacity 1
- For each node a in V{u}, add a directed arc from u to a with capacity equal to f(a)/2
The claim is that there is a violated set S with u in S and v not in S if and only if the maximum flow from u to v in the graph H described above is strictly less than |V|-1. For one direction, say S is a violated set containing u but not v. Let’s examine the capacity of the corresponding cut S in H:
- |S|-1 total capacity is from edges created in step 2 (1 from each node except u)
- f * (S)/2 total capacity is from edges created in step 1
- (f(a _ 1) + f(a _ 2) + … + f(a _ k))/2 total capacity is from edges created in step 3 where a _ 1, …, a _ k are the nodes not in S
Now, f(a _ 1) + f(a _ 2) + … + f(a _ k) = 2f(V) - f(s _ 1) - f(s _ 2) - … - f(s _ |S|) where the s _ i are the nodes in S (each edge contributes to two vertices). Therefore, the total capacity of the cut is:
|S| - 1 + f * (S)/2 + f(V) - f(a _ 1)/2 - f(a _ 2)/2 - … - f(a _ k)/2
Now, each edge with exactly one endpoint in S has half its value counted among f*(S)/2 and half its value counted among the f(a _ i)/2. Each edge with both endpoints in S is counted twice among the f(a _ i)/2. Therefore, f * (S)/2 - f(a _ 1)/2 - f(a _ 2)/2 - … - f(a _ k)/2 = f(S). Thus, the capacity of the cut is:
|S| - 1 + f(V) - f(S) = |S| - 1 + |V| - 1 - f(S)
Under the assumption f(S) > |S|-1, we have the cut capacity being strictly less than |V|-1. Therefore, by the max-flow/min-cut theorem the maximum flow between u and v is less than |V|-1.
On the other hand, if the maximum flow between u and v is less than |V|-1 then consider a cut S containing u with capacity less than |V|-1. The arguments made above can be easily reversed to yield a non-trivial set S with f(S) > |V|-1.
So, if we know two nodes u and v such that u is in a violated set S and v is not, then we can recover such a set using the flow-based algorithm mentioned above. Fix a node u and try all |V|-1 other nodes v. We know that either u is in S or u is not in S so for some guess v we have u is in S and v is not, or vice-versa. So, we just need to run the above algorithm at most 2|V|-2 times: once from u to each node v and once from each node v to u.
While converting to doubles would probably not cause any rounding errors in any reasonable implementation, the bound on the denominators of the rational numbers was chosen such that a careful implementation of rational numbers and either the Edmonds-Karp or Dinic’s flow algorithm would not result in overflow if 64 bit integers were used.