PROBLEM LINK:
DIFFICULTY
EASY
PREREQUISITES
Graph Theory, Bipartite Graph, Two colouring, DFS
(Alternate Solution) Gauss Elimination, Minimum Spanning Tree, Finite Field Arithmetic - especially GF(2)
PROBLEM
Given a graph, houses as nodes and roads as edges, you can warp some edges out of a restricted set of edges. Warping an edge means the two vertices it joins are merged and all the existing edges are extended to this new vertex.
This may result in some edges becoming self loops. Unless these self loops can be warped, they should not be formed.
Your aim is to make the graph bipartite.
EXPLANATION
The setter and the tester use two very different approaches to solve the problem.
TESTERS APPROACH
Let us look at this approach first, because of its simplicity!
Ignore the warp-able edges. Don’t warp them yet, but consider the graph without any of edges that can be warped. Let this graph be called A.
Try to find a two colouring of A. Now, some of the warp-able edges can be warped to get a bipartite graph if and only if it was possible to find a two colouring of A. This result is because
-
If A is not bipartite, since no edges of A can be warped and self loops are not ignored, A cannot be bipartite finally after warping any of the remaining edges.
-
If A is bipartite, then we warp those edges that are connecting the vertices of the same colour. This way, we will never introduce self loops, the the final graph will also be bipartite - since we preserved only those edges that connected vertices of different colour.
The only remaining trick is to find whether A has a two colouring.
This can be done by doing a DFS on the graph and trying to two colour it arbitrarily. If ever an edge is encountered which connects to a vertex previously coloured, and whose colour is same as the colour you are about to assign to the current vertex; then you have found a necessary and sufficient witness to the non bipartite-ness of the graph.
SETTERS APPROACH
The setter used a very complicated technique, which relies upon the following axiom:
For a graph to be bipartite, all the cycles must be of even length.
We can construct a system of linear equations in GF(2). Consider the set of binary variables EW representing all the warp-able edges. If a variable is 1, it means the edge is not warped, and vice versa.
We can construct equations over these variables, where each equation refers to a cycle in the graph. Each equation should evaluate to {0, 1} based on whether after warping a set of edges, there should remain even or odd number of edges from the set of warp-able edges.
Since the number of cycles can be exponential in a graph, we must consider a polynomial number of cycles which can be linearly combined (that is symmetric difference of their edge sets taken) to get all the other cycles. One such set of cycles can be achieved as follows
- Consider a minimum spanning tree of the graph
- Add an edge and consider the unique cycle hence created
- Repeat the other step by deleting the previously added edge and adding a new one each time
This gives O(E) cycles to consider, whose linear combination (addition in GF(2)) produces all the other cycles.
What remains is to verify whether the system of equations hence built has a valid solution or not. This can be done via Gaussian Elimination.
Gaussian Elimination can be applied to ensure whether it is possible to have even number of edges un-warped for cycles that have even number of un-warpable edges otherwise, and vice-versa.
SETTERS SOLUTION
Can be found here
TESTERS SOLUTION
Can be found here