PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
Given an assignment of 0/1 values to edges of the graph, let w(C) be the number of edges on a cycle C that are assigned a 1 and let f(C) be the number of faces contained in C. Say that a cycle C is harmonious if w(C) = f(C) mod 2. If C is a cycle that bounds a single face, then f(C) = 1 so a necessary condition for all cycles being harmonious is that w(C) is odd for every cycle C that bounds a single face.
One of the main observations in this question is that this is also sufficient. Consider a cycle C and say it contains k = f(C) faces F_1, …, F_k. Let C_1, …, C_k denote the cycles that bound the respective faces. Then w(C) = W(C_1) + … + W(C_k) (mod 2) because every edge on C is counted only once and every edge contained in the region bounded by C is counted twice in the sum (once for each of the faces F_i, F_j that include the edge on C_i, C_j). Because the graph is has no bridges, then there is no edge that has the same face touching both sides. We have W(C_1) = … = W(C_k) = 1 (mod 2) since each C_i is the cycle bounding a single face so then w(C) = k = f(C) (mod 2), which is what we wanted to show.
If n was smaller, then we could simply set up a system of linear equations mod 2 where we have variables for the edges an one equation for each interior face and solve this using Gaussian elimination. However, n can be much larger so a better algorithm is needed. First, find any spanning tree T of the graph. Consider the “dual complement” of T. This is a graph T’ whose nodes correspond to faces in the drawing of G (including the unbounded face) and two nodes in T’ are adjacent if their corresponding faces in the drawing of G share a common edge that is not in the tree T. Let r be the node in T’ that corresponds to the unbounded face of the drawing of G.
Now, T’ is also connected and acyclic. The intuitive idea behind this is that if T’ is not connected then faces in the drawing of G that are not in the same component as r in T’ are separated from the other faces by a cycle whose edges are in T, which contradicts the fact that T is acyclic. Also, if T’ has a cycle then we can draw a closed curve in the plane that stays entirely contained in the faces corresponding to such a cycle and passes only through edges that are not in T. But then these edges form a cut of G which contradicts the fact that any cut of a connected graph must contain at least one edge of any particular spanning tree.
To exploit this, assign arbitrary values to the edges in T (e.g. 0 for each such edge) and root T’ at r. A leaf node x (excluding r if r has degree 1 in T’) corresponds to a face in the drawing of G for which exactly one edge on the boundary has not been assigned a value. So, pick any such leaf x and assign whatever value is needed to have the corresponding face f(C) odd where C is the bounding cycle of this face. Then remove x from T’ and recurse until T’ consists of only the root r, in which case we are done. With care, this can be implemented to run in O(n log n) time.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.