TY - JOUR

T1 - Making bipartite graphs DM-irreducible

AU - Bérczi, Kristóf

AU - Iwata, Satoru

AU - Kato, Jun

AU - Yamaguchi, Yutaro

N1 - Funding Information:
∗Received by the editors December 6, 2016; accepted for publication (in revised form) January 8, 2018; published electronically February 22, 2018. http://www.siam.org/journals/sidma/32-1/M110671.html Funding: This work was supported by the MTA-ELTE Egerváry Research Group, by Hungarian National Research, Development and Innovation Office (NKFIH) grant K109240, by JST CREST grant JPMJCR14D2, by JSPS KAKENHI grant JP16H06931, and by JST ACT-I grant JPMJPR16UR. †Eötvös Loránd University, 1117 Budapest, Hungary (berkri@cs.elte.hu). ‡University of Tokyo, Tokyo 113-8656, Japan (iwata@mist.i.u-tokyo.ac.jp). §Toyota Motor Corporation, Toyota 471-8571, Japan (jun kato aa@mail.toyota.co.jp). ¶Osaka University, Osaka 565-0871, Japan (yutaro yamaguchi@ist.osaka-u.ac.jp).
Publisher Copyright:
© 2018 Society for Industrial and Applied Mathematics.

PY - 2018

Y1 - 2018

N2 - The Dulmage–Mendelsohn decomposition (or the DM-decomposition) gives a unique partition of the vertex set of a bipartite graph reflecting the structure of all the maximum matchings therein. A bipartite graph is said to be DM-irreducible if its DM-decomposition consists of a single component. In this paper, we focus on the problem of making a given bipartite graph DM-irreducible by adding edges. When the input bipartite graph is balanced (i.e., both sides have the same number of vertices) and has a perfect matching, this problem is equivalent to making a directed graph strongly connected by adding edges, for which the minimum number of additional edges was characterized by Eswaran and Tarjan [SIAM J. Comput., 5 (1976), pp. 653–665]. We give a general solution to this problem, which is divided into three parts. We first show that our problem can be formulated as a special case of a general framework of covering supermodular functions, which was introduced by Frank and Jordán [J. Combin. Theory Ser. B, 65 (1995), pp. 73–110] to investigate the directed connectivity augmentation problem. Second, when the input graph is not balanced, the problem is solved via matroid intersection. This result can be extended to the minimum cost version in which the addition of an edge gives rise to an individual cost. Third, for balanced input graphs, we devise a combinatorial algorithm that finds a minimum number of additional edges to attain the DM-irreducibility, while the minimum cost version of this problem is NP-hard. These results also lead to min-max characterizations of the minimum number, which generalize the result of Eswaran and Tarjan.

AB - The Dulmage–Mendelsohn decomposition (or the DM-decomposition) gives a unique partition of the vertex set of a bipartite graph reflecting the structure of all the maximum matchings therein. A bipartite graph is said to be DM-irreducible if its DM-decomposition consists of a single component. In this paper, we focus on the problem of making a given bipartite graph DM-irreducible by adding edges. When the input bipartite graph is balanced (i.e., both sides have the same number of vertices) and has a perfect matching, this problem is equivalent to making a directed graph strongly connected by adding edges, for which the minimum number of additional edges was characterized by Eswaran and Tarjan [SIAM J. Comput., 5 (1976), pp. 653–665]. We give a general solution to this problem, which is divided into three parts. We first show that our problem can be formulated as a special case of a general framework of covering supermodular functions, which was introduced by Frank and Jordán [J. Combin. Theory Ser. B, 65 (1995), pp. 73–110] to investigate the directed connectivity augmentation problem. Second, when the input graph is not balanced, the problem is solved via matroid intersection. This result can be extended to the minimum cost version in which the addition of an edge gives rise to an individual cost. Third, for balanced input graphs, we devise a combinatorial algorithm that finds a minimum number of additional edges to attain the DM-irreducibility, while the minimum cost version of this problem is NP-hard. These results also lead to min-max characterizations of the minimum number, which generalize the result of Eswaran and Tarjan.

UR - http://www.scopus.com/inward/record.url?scp=85045645488&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85045645488&partnerID=8YFLogxK

U2 - 10.1137/16M1106717

DO - 10.1137/16M1106717

M3 - Article

AN - SCOPUS:85045645488

SN - 0895-4801

VL - 32

SP - 560

EP - 590

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -