PROBLEM LINKSDIFFICULTYHARD EXPLANATIONApproach Taken: This can be solved via network flow. First, say we have already verified the trivial condition that the total fraction is V1. 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. 1) 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 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 V1. 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: 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) > S1, we have the cut capacity being strictly less than V1. Therefore, by the maxflow/mincut theorem the maximum flow between u and v is less than V1. On the other hand, if the maximum flow between u and v is less than V1 then consider a cut S containing u with capacity less than V1. The arguments made above can be easily reversed to yield a nontrivial set S with f(S) > V1. 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 flowbased algorithm mentioned above. Fix a node u and try all V1 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 viceversa. So, we just need to run the above algorithm at most 2V2 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 EdmondsKarp or Dinic's flow algorithm would not result in overflow if 64 bit integers were used.
This question is marked "community wiki".
asked 28 Nov '12, 16:56
