Making bipartite graphs DM-irreducible

DOI10.1137/16M1106717zbMATH Open1381.05052arXiv1612.08828OpenAlexW2963249783MaRDI QIDQ4604647FDOQ4604647

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)

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.

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

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

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)

Cites Work

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

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)