Term for a graph decomposition based on a maximum matching

Question

Let $M$ be a maximum cardinality matching in a bipartite graph $G(X+Y,E)$. Let $X_0$ be the subset of $X$ unmatched by $M$. Define the following sequence:

• $Y_1 = $ the neighbors of $X_0$ using edges in $E\setminus M$.
• $X_1 = $ the neighbors of $Y_1$ using edges in $M$.
• $Y_2 = $ the new neighbors of $X_1$ ("new" = not in $Y_1$) using edges in $E\setminus M$.
• etc...

Since the graph is finite, at some point we stop finding new vertices, so the process stops and we have a maximal sequence.

Let $X_S,Y_S$ be the vertices contained in the sequence, and $X_L,Y_L$ the leftover vertices:

We have a decomposition of $X$ and $Y$ into two subsets. This decompositionhas some nice properties (for example, $X_L$ and $X_S$ are the same regardless of what maximum matching $M$ we start from).

Such a nice decomposition must have a name... what is its name? And what is a standard reference for the decomposition and its properties?

Answer 1

Looking at the image in the question, I get the impression that $X_L\cup Y_S$ is a minimal vertex cover of the graph $G$. (This is not fully true: If $X$ contains isolated vertices, then those would be part of $X_L$, but not of a minimal vertex cover.) Good, but there can be many vertex covers of a graph, so this does not yet fully characterize that specific decomposition. So let us look at the construction in more detail: Any minimal vertex cover must contain at least one vertex from every matched edge. Since the vertices in $X_0$ don't belong to any matched edge, covering the edges incident to $X_0$ by vertices (from $Y$) belonging to matched edges is the best we can do. So $Y_S$ turns out to be the biggest subset of $Y$ belonging to every mimimal vertex cover of $G$. (So it is the intersection of the $Y$ part of all minimal vertex covers). And $X_L$ is the unique subset of $X$ covering the remaining edges (+ the isolated vertices of $X$).

OK, so how is this related to the Dulmage-Mendelsohn decomposition? (set $U=X$ and $V=Y$).

..., let $D$ be the set of vertices in $G$ that are not matched in at least one maximum matching

I guess the neighbors of $D\cap X$ belong to any minimal vertex cover, and the neighbors of $D\cap Y$ also belong to any minimal vertex cover. So $Y_S$ is also part of (or at least easily defined) for the Dulmage-Mendelsohn decomposition. Can we also define $X_L$ in terms of the Dulmage-Mendelsohn decomposition? Well, it is easier to define $X_S$, it should be just $D\cap X$.

This all sounds much more complicated than it actually is. If you look at the possible alternating paths for the given maximum matching, it should be easy to see the relation between the minimal vertex cover and the set $D$ used to define the Dulmage-Mendelsohn decomposition.