Skew-symmetric Graph - Matching

Matching

In constructing matchings in undirected graphs, it is important to find alternating paths, paths of vertices that start and end at unmatched vertices, in which the edges at odd positions in the path are not part of a given partial matching and in which the edges at even positions in the path are part of the matching. By removing the matched edges of such a path from a matching, and adding the unmatched edges, one can increase the size of the matching. Similarly, cycles that alternate between matched and unmatched edges are of importance in weighted matching problems. As Goldberg & Karzanov (1996) showed, an alternating path or cycle in an undirected graph may be modeled as a regular path or cycle in a skew-symmetric directed graph. To create a skew-symmetric graph from an undirected graph G with a specified matching M, view G as a switch graph in which the edges at each vertex are partitioned into matched and unmatched edges; an alternating path in G is then a regular path in this switch graph and an alternating cycle in G is a regular cycle in the switch graph.

Goldberg & Karzanov (1996) generalized alternating path algorithms to show that the existence of a regular path between any two vertices of a skew-symmetric graph may be tested in linear time. Given additionally a non-negative length function on the edges of the graph that assigns the same length to any edge e and to σ(e), the shortest regular path connecting a given pair of nodes in a skew-symmetric graph with m edges and n vertices may be tested in time O(m log n). If the length function is allowed to have negative lengths, the existence of a negative regular cycle may be tested in polynomial time.

Along with the path problems arising in matchings, skew-symmetric generalizations of the max-flow min-cut theorem have also been studied (Goldberg & Karzanov 2004; Tutte 1967).