HAMEL - Editorial

general
, , , , , ,
1

Problem Link:

Practice

Contest

Setter: Alei Reyes

Tester: Triveni Mahatha

Editorialist: Alei Reyes

Difficulty:

HARD

Prerequisites:

Matroid Partition, Augmenting Path

Problem:

Given a highly connected (min cut > 3) multi graph G(V, E), find an Eulerian Path from some subset of E.

Explanation:

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!).
  • Let's suppose that we are adding edge e, it will generate a cycle in both the red tree and the green forest.
  • In order to add e we'll have to change the color of some of the other edges.
  • The idea is that e creates a cycle in the red tree, so if we make e of color red, then we have to change the color of one of the edges of the cycle to color green, however this can again create a cycle in the green forest, so we'll have to find one edge of the green cycle and change its color to red, but this can create a cycle in ... (and so on) this process can finish if we end up in a connector
  • Let's build a graph where its vertices represents the edges of G, and there is a directed edge between two vertices x, y if it is possible to replace y by x in its respective tree without generating cycles. Now the previous step is equivalent to finding a path from e to a connector in this new graph. Note that this is similar to finding an augmenting path in flows algorithms.

    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.

    SOLUTION:

    Setter

    Tester

    Time Complexity:

    O(VE), per test case.

    Space Complexity:

    O(E + V)

    • 1 Like