In a bipartite graph I want to partition edges into the following three sets:
- $E_1$, edges that are in all maximum matchings
- $E_2$, edges that are in some but not all maximum matchings
- $E_3$, edges that never appear in a maximum matching
I have read that the Dulmage-Mendelsohn decomposition (DMD) can be used to partition the edges this way. However, the only tool for computing the DMD I can find (in matlab) does not directly give this partitioning. Rather it gives a block diagonal form of the biadjacency matrix representing the graph.
My question is, how does this matrix form of the decomposition relate to the above partitioning of edges. And is there a way to read off $E_1$, $E_2$ and $E_3$ from this block matrix? And if so how?