Algorithms for finding a Tutte-Berge maximizer

Question

Let $G=(V,E)$ be a graph. The Tutte-Berge formula states that a maximum matching on $G$ has size $$\nu(G)=\frac12\left(|V|-\max_{U\subset V}(o(V-U)-|U|)\right)$$ with $o(V-U)$ the number of connected components of $V-U$ of odd size.

Question: How much is known about algorithms for finding $U\subset V$ maximizing $o(V-U)-|U|$? I am having trouble finding any resources about this question.

I did come up with a polynomial time algorithm by myself. I determined that you can construct such $U$ by iteratively finding a vertex $v\in V$ such that $\nu(V-\{v\})=\nu(V)-1$. This requires solving $O(|V|^2)$ maximum matching problems, and thus runs in polynomial time. However, I would like to know if there is any faster algorithm.

Answer 1

It is not necessary to do $O(|V|^2)$ passes of a maximum matching algorithm; a single pass is enough if we're careful about it, use the right algorithm, and look at the additional data that algorithm generates.

Suppose you go looking for a maximum matching in $G$ using the blossom algorithm. This takes us through some number of steps of finding augmenting paths and contracting odd cycles (blossoms). At the end of the algorithm, we find a maximum matching $M'$ in some smaller graph $G'$, and by expanding the blossoms again we can obtain a maximum matching $M$ in $G$. At this stage:

1. Right before expanding the blossoms, we can find a Tutte–Berge maximizer in $G'$;
2. After we expand the blossoms, it remains a Tutte–Berge maximizer in $G$.

Finding a Tutte–Berge maximizer in $G'$

Here, the blossom algorithm has built a forest $F$ in $G'$ (called an $M'$-alternating forest) in which each tree component has a root in $S$: the set of vertices not covered by the matching. We say that a vertex is an inner vertex if its distance in $F$ from a root is odd, and an outer vertex if the distance is even. By the algorithm, all inner vertices have degree $2$ in $F$: they have one parent and one child, and the edge from each inner vertex to its child is an edge of $M'$.

This much should hold at every step of the blossom algorithm. When we've reached the end, we also know the following:

• No outer vertex has neighbors outside $F$; otherwise, we could use those neighbors to expand the forest.
• Two outer vertices cannot be adjacent. If there were an edge between two outer vertices in different components of $F$, we would find an $M'$-augmenting path; if there were an edge between two outer vertices in the same component of $F$, we would find a blossom.

In this case, let $U$ be the set of inner vertices: this set $U$ is a Tutte–Berge maximizer in $G'$! Why? Well, by the observations above, the outer vertices can only have neighbors in $U$, so in particular, they are odd components of $G' - U$. The number of outer vertices is exactly $|U| + |S|$, because each outer vertex in the forest $F$ is either a root or the unique child of an inner vertex. Therefore $o(G' - U) - |U|$ is exactly $|S|$, the number of vertices uncovered by a maximum matching in $G'$.

Returning to $G$

We wanted to find a Tutte–Berge maximizer in $G$, not $G'$. To do this, we expand the blossoms, one at a time, and see what happens to $U$.

Each blossom is an odd cycle containing $k$ inner vertices and $k+1$ outer vertices of an alternating forest; after the blossom is contracted, it becomes a single outer vertex of an alternating forest in the smaller graph. Therefore, as we expand the blossoms, the set $U$ is left untouched: it started out consisting of inner vertices only, and as we expand, it continues to consist of inner vertices only (though it will no longer contain all the inner vertices).

Meanwhile, the odd components in the complement of $U$ will remain odd components. As we expand the blossoms, they might get bigger. However, they'll remain isolated from each other, and replacing a vertex by an odd cycle will not change their parity.

Therefore $o(G-U) - |U|$ in the original graph $G$ will have the same value as $o(G'-U) - |U|$ did in $G'$. The number of vertices uncovered by the maximum matching also remains the same: expanding a blossom of length $2k+1$ adds $2k$ vertices, but also adds $k$ edges to the matching. We conclude that $U$ is still a Tutte–Berge maximizer in $G$.

A worse but lazier solution

If we stick to treating the blossom algorithm (or any alternative) as a black box, we can still do better and identify a Tutte–Berge maximizer after only solving $O(|V|)$ maximum matching problems.

Let $D$ be the set of all inessential vertices of $G$: the vertices that are left uncovered by some maximum matching in $G$. A vertex $v \in D$ can be identified by the property that $G-v$ and $G$ have maximum matchings of the same size. Next, split $V(G)-D$ into sets $A$ and $C$, defined to be the essential vertices adjacent to some vertex in $D$, and the other essential vertices.

The partition $A \cup C \cup D$ is the Gallai–Edmonds decomposition of $G$. In particular, the set $A$ is a Tutte–Berge maximizer.