Setter: Alei Reyes
Tester: Triveni Mahatha
Editorialist: Alei Reyes
Matroid Partition, Augmenting Path
Given a highly connected (min cut > 3) multi graph G(V, E), find an Eulerian Path from some subset of E.
Every 4-edge connected graph has 2 edge disjoint spanning trees. Given two edge disjoint spanning trees, is possible to choose some of the edges and create an Eulerian subgraph H as follows:
- Paint the edges of the two spanning trees, the first one in red, and the second in green.
- Add all the edges of the green tree to H.
- Root the red tree in an arbitrary node, this will create a parent-child relationship.
- Let’s go through the red tree from leafs to root. Suppose that we are at node u. If the degree of u in H is odd, then add the red edge that joins u with its parent to H.
At the end of the algorithm, all the vertices in H will have even degree. In particular note that the root can not have odd degree because every graph has an even number of odd degree vertices.
To find two disjoint spanning trees in a given graph G, we can use the following algorithm:
- Let’s find an spanning tree T, and paint its edges with color red.
- Now let’s find a spanning forest F that doesn’t use edges of T and paint its edges with color green.
- The green forest is composed of many disconnected trees. Let’s call the red edges that joins two disconnected components of the green forest as “connectors”
- If F consists of exactly one tree, then we are done.
- Otherwise we’ll try add one by one the edges that are not painted keeping always a red tree and a green forest (at the end the green forest will become a green tree!).
The algorithm described above is actually the matroid partition algorithm. For a formal proof in the more general setting of matroids, you can see Lecture 13 of Goemans.
O(VE), per test case.
O(E + V)