PROBLEM LINK:Author: Sai Sandeep Tester: Aditya Shah DIFFICULTY:HARD PREREQUISITES:PROBLEM:Given sum of degrees of each vertex of graph, check if such a weighted graph can exist, if the upper bound on weight of edge between vertices i and j is i^j ( Bitwise xor ) QUICK EXPLANATION:Check if the sum of degrees is even. Construct a flow network with N vertices on left and right, edge with capacity i ^ j from i th vertex on left to jth vertex on right. Add a source and sink, with capacities equal to sum of degrees of vertices on left and right. Check if the flow equals the sum of degrees. EXPLANATION:First of all, the sum of degrees of the graph is even. See this From here onwards, we use $c_{ij}$ to denote i^j, $d_i$ to denote sum of degrees of i. Lets construct a flow network, with N vertices on left and N vertices on right, edge of capacity $c_{ij}$ from i on left to j on right. Add a source on left and edges of capacity $d_i$ from source to i on left. Add a sink on right and edges of capacity $d_i$ from i on right to sink. Suppose that there is such a graph satisfying the conditions in the problem, then the maximum flow in this graph is equal to sum of $d_i$, since we can send $w_{ij}$ on the edge between i on left and j on right. Is the converse true ? Why can't it possibly not hold ? It's because in our flow network, $e_{ij}$ and $e_{ji}$ need not be same. But we can still consider $w_{ij} = (e_{ij} + e_{ji} )/2$ and it will satisfy the sum of degrees criterion. But the problem with this is that we no longer have integral weights on the edges. It can be a fraction, but still integral multiple of 1/2. It turns out that if the sum of degrees is even, this flow can be modified to get a flow in which we don't have these nonintegral weights. For example, if there is an even cycle with nonintegral weights, we can add 1/2 to alternate edges and subtract 1/2 from rest to get rid of these nonintegral weights. If we have two odd cycles with nonintegral flows, we can adjust the flow from one cycle to other to get rid of all the nonintegral ones. See this writeup for more formal proof. Of course, we need not code all that, we just need to check that sum of degrees is even. But to arrive at that, we need above observations. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here
This question is marked "community wiki".
asked 30 Sep '16, 12:12
