Making bipartite graphs DM-irreducible

DOI10.1137/16M1106717MaRDI QIDQ4604647zbMATH OpenOpenAlexFDO

Authors Kristóf Bérczi, Satoru Iwata, Jun Kato, Yutaro Yamaguchi

Publication date 5 March 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.08828

zbMATH Keywords

matroid intersectionbipartite graphsconnectivity augmentationDM-decomposition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial aspects of matroids and geometric lattices (05B35) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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 (1976). 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'an (1995) to investigate the directed connectivity augmentation problem. Secondly, 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. Thirdly, 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.

Recommendations

• Nonbipartite Dulmage-Mendelsohn decomposition for Berge duality
• Incrementing bipartite digraph edge-connectivity
• Solving matching problems efficiently in bipartite graphs
• A perfect matching algorithm for sparse bipartite graphs
• Minimal edge-coverings of pairs of sets

Cites work

• scientific article; zbMATH DE number 3149610 (Why is no real title available?)
• scientific article; zbMATH DE number 3976197 (Why is no real title available?)
• scientific article; zbMATH DE number 1953186 (Why is no real title available?)
• A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
• An algorithm to increase the node-connectivity of a digraph by one
• Augmentation Problems
• Bargaining in a network of buyers and sellers.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Connections in combinatorial optimization
• Coverings of Bipartite Graphs
• Depth-First Search and Linear Graph Algorithms
• Efficient theoretic and practical algorithms for linear matroid intersection problems
• Exact and approximation algorithms for weighted matroid intersection
• Matrices and matroids for systems analysis
• Maximal Flow Through a Network
• Minimal edge-coverings of pairs of sets
• Primal-dual approach for directed vertex connectivity augmentation and generalizations
• Submodular functions and optimization.

Cited in

(3)

• How to Secure Matchings Against Edge Failures
• How to Secure Matchings against Edge Failures
• Making bidirected graphs strongly connected

This page was built for publication: Making bipartite graphs DM-irreducible

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604647)