Question

The Gallai-Edmonds decomposition partitions a graph into three sets based on the structure of these things. The size of these things is given by the Tutte-Berge formula. The first known algorithm for finding these things in polynomial time works by recursively contracting odd length cycles, which are called “blossoms”. (15[1])It’s not flow, but most algorithms that find these things work by repeatedly finding alternating paths that begin and end at free vertices and augmenting those paths until there are none left. The Hopcroft-Karp algorithm (-5[1])finds these things, which are equivalent to minimum vertex covers by (*) Kőnig's theorem. (-5[1])If all edges in a bipartite graph have capacity 1, then finding a max flow is trivially equivalent to finding one of these things. For 10 points, give this term for the largest set of edges in a graph that shares no common vertex, (-5[1])which therefore pairs up the most possible vertices. ■END■ (0[2])

Back to tossups