Talk:Dulmage–Mendelsohn decomposition

Applicable to any graph?

"the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph"

-- This definition may give the impression that every bipartite graph has a perfect matching, which is not true. Does this mean that the Dulmage–Mendelsohn decomposition is defined only on such graphs that have a perfect matching? If so, then this should be stated clearly in order to prevent confusion. --Erel Segal (talk) 16:42, 28 December 2013 (UTC)

The DM decomposition indeed applies to any bipartite graph; even better, in practice, the coarse decomposition is only useful when no perfect matching exists (including, but not limited to, non-square cases). It is stated that one input of the algorithm is D, 'the set of vertices in G that are not matched in at least one maximum matching of G'. If perfect matchings exist, then D is an empty set and the coarse DM decomposition is trivial; then any finer decomposition roughly consists in finding Strongly Connected Components, i.e., calling Tarjan to the rescue. 92.167.218.166 (talk) 08:36, 19 March 2020 (UTC)

Factual error: alternate definition

I am currently working, as a post-doctoral student, on the modeling and simulation of physical systems, and as such, I had to come back to the gool old DM decomposition.

I realized, to my horror, that Bunus and Fritzson (see additional link 1 in the article) were terribly wrong in their 2002 paper, as they were in the one before that ("A Debugging Scheme for Declarative Equation-Based Modeling Languages"). In both of these articles, they use the algorithm with sets E, U and O that has been, since, published by Irving et al. ("Rank-Maximal Matchings", 2006), and talk about this algorithm as "the Dulmage-Mendelsohn decomposition algorithm". It is not. Not only the article by Irving does not mention Dulmage nor Mendelsohn at any point, but the results yielded by this algorithm differ from the canonical DM decomposition, even on the very exemple provided by Bunus and Fritzson in their 2002 paper.

(For those who would like to check: the DM decomposition of this example is {e4,eq5,eq6,eq7} as the underdetermined part, {eq1,eq2,eq3} as the overdetermined part, no square/enabled part in between. I also checked these results with Matlab 2018a.)

To my knowledge, the works by Bunus and Fritzson are the only reason why this 'alternative DM decomposition' is mentioned in the Wikipedia article, and it is actually wrong. As such, this whole section should be removed from the article.

Of course, I highly encourage you to check the veracity of what I just wrote before taking any decision, and as a non-registered user, I will not edit the page myself.

Thanks for reading. 92.167.218.166 (talk) 08:31, 19 March 2020 (UTC)