{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,12]],"date-time":"2026-11-12T04:20:26Z","timestamp":1794457226822,"version":"4.9.1"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"MTA-ELTE Egervary Research Group"},{"name":"Hungarian National Research, Development and Innovation Office-NKFIH","award":["K109240"],"award-info":[{"award-number":["K109240"]}]},{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"publisher","award":["JPMJCR14D2"],"award-info":[{"award-number":["JPMJCR14D2"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP16H06931"],"award-info":[{"award-number":["JP16H06931"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JPMJPR16UR"],"award-info":[{"award-number":["JPMJPR16UR"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>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\u00e1n [ 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.<\/jats:p>","DOI":"10.1137\/16m1106717","type":"journal-article","created":{"date-parts":[[2018,2,22]],"date-time":"2018-02-22T13:09:36Z","timestamp":1519304976000},"page":"560-590","source":"Crossref","is-referenced-by-count":5,"title":["Making Bipartite Graphs DM-Irreducible"],"prefix":"10.1137","volume":"32","author":[{"given":"Krist\u00f3f","family":"B\u00e9rczi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Satoru","family":"Iwata","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jun","family":"Kato","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yutaro","family":"Yamaguchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,2,22]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01589417"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0531(03)00110-8"},{"key":"atypb3","unstructured":"I. S. Duff, A. M. Erisman and J. K. Reid,\n                      Direct Methods for Sparse Matrices\n                      , Clarendon Press, Oxford, UK, 1986."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1958-052-0"},{"key":"atypb5","unstructured":"A. L. Dulmage and N. S. Mendelsohn,\n                      A structure theory of bipartite graphs of finite exterior dimension\n                      , Trans. Roy. Soc. Canada Ser. \\Rn3, 53 (1959), pp. 1-13."},{"key":"atypb6","first-page":"11","author":"Edmonds J.","year":"2003","journal-title":"New York"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/0205044"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"atypb9","unstructured":"A. Frank,\n                      Connections in Combinatorial Optimization\n                      , Oxford University Press, Oxford, UK, 2011."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1044"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2008.03.002"},{"key":"atypb12","unstructured":"S. Fujishige,\n                      Submodular Functions and Optimization\n                      , 2nd ed., Elsevier, New York, 2005."},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"H. N. Gabow and Y. Xu,\n                      Efficient algorithms for independent assignments on graphic and linear matroids\n                      , in Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 106-111.","DOI":"10.1109\/SFCS.1989.63463"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0054"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"C.C. Huang, N. Kakimura and N. Kamiyama,\n                      Exact and approximation algorithms for weighted matroid intersection\n                      , in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, 2016, pp. 430-444.","DOI":"10.1137\/1.9781611974331.ch32"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1145\/990518.990521"},{"key":"atypb17","unstructured":"L. Lova\u0301sz and M. D. Plummer,\n                      Matching Theory\n                      , Akade\u0301miai Kiado\u0301, Budapset, 1986."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.4064\/fm-10-1-96-115"},{"key":"atypb19","unstructured":"K. Murota,\n                      Matrices and Matroids for Systems Analysis\n                      , Springer-Verlag, New York, 2000."},{"key":"atypb20","unstructured":"A. Schrijver,\n                      Combinatorial Optimization-Polyhedra and Efficiency\n                      , Springer-Verlag, New York, 2003."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"atypb22","first-page":"20","volume":"4","author":"Ve\u0301gh L.","year":"2008","journal-title":"ACM Trans. Algorithms"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1106717","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:54:11Z","timestamp":1787316851000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1106717"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1106717"],"URL":"https:\/\/doi.org\/10.1137\/16m1106717","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}