4
$\begingroup$

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:

enter image description here

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?

$\endgroup$
  • $\begingroup$ Do you know en.wikipedia.org/wiki/Dulmage%E2%80%93Mendelsohn_decomposition ? It seems closely related to your decomposition. It is something like the strongly connected components of the directed graph, generated from the matching which is used for orienting the edges of the bipartite graph. $\endgroup$ – Thomas Klimpel Jul 5 at 0:12
  • $\begingroup$ Here is a working link: Dulmage–Mendelsohn decomposition $\endgroup$ – Thomas Klimpel Jul 5 at 5:23
  • $\begingroup$ @ThomasKlimpel I read this link but did not understand the construction. The construction is based on "D - the set of vertices in G that are not matched in at least one maximum matching of G". Apparently, to find this D (or even to verify whether a given set is D) one has to find all maximum matchings in G, which is quite hard. In contrast, my construction requires only a single maximum matching. $\endgroup$ – Erel Segal-Halevi Jul 5 at 5:49
  • $\begingroup$ @ThomasKlimpel I also read the original paper: cambridge.org/core/services/aop-cambridge-core/content/view/… but I did not understand the connection - they talk about exterior covering and other concepts that I cannot see their connection to my construction. $\endgroup$ – Erel Segal-Halevi Jul 5 at 10:02
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think I get the first part. In the second part, I do not understand this sentence: "I guess the neighbors of D∩X belong to any minimal vertex cover, and the neighbors of D∩Y also belong to any minimal vertex cover. So YS is also part of (or at least easily defined) for the Dulmage-Mendelsohn decomposition." Why is it true? $\endgroup$ – Erel Segal-Halevi Jul 5 at 14:25
  • $\begingroup$ @ErelSegal-Halevi The vertices in $D$ belong to maximal alternating paths with an odd number of vertices (and an even number of edges). If you want to cover every edge of such an alternating path, you can do so with 'number of edges'/2 vertices, if you don't put vertices on the endpoints of the path. This is not a full explanation, but it is the reason why I guess that the neighbors of $D$ belong to any minimal vertex cover. $\endgroup$ – Thomas Klimpel Jul 5 at 16:37
  • $\begingroup$ @ErelSegal-Halevi This short writeup treats the (coarse) Dulmage-Mendelsohn decomposition in terms of alternating paths: cse.iitm.ac.in/~meghana/matchings/bip-decomp.pdf Should be easy to understand, or at least easier than my attempts at an explanation (or the original publication). $\endgroup$ – Thomas Klimpel Jul 7 at 16:11
  • $\begingroup$ Indeed this looks closely related, thanks! The only difference is that my construction starts with unmatched vertices in one side only ($X_0\subseteq X$), while their construction starts considers the unmatched vertices in both sides. $\endgroup$ – Erel Segal-Halevi Jul 9 at 15:02
  • $\begingroup$ But now there is a different question: why are these two definitions equivalent? The first definition in Wikipedia and the definition in the linked page look quite different.. $\endgroup$ – Erel Segal-Halevi Jul 29 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.