Perfectly matchable subgraph problem on a bipartite graph. (English) Zbl 1218.05149
Summary: We consider the maximum weight perfectly matchable subgraph problem on a bipartite graph \(G=(UV,E)\) with respect to given nonnegative weights of its edges. We show that \(G\) has a perfect matching if and only if some vector indexed by the nodes in \(UV\) is a base of an extended polymatroid associated with a submodular function defined on the subsets of \(UV\). The dual problem of the separation problem for the extended polymatroid is transformed to the special maximum flow problem on \(G\). In this paper, we give a linear programming formulation for the maximum weight perfectly matchable subgraph problem and propose an \(O(n^3)\) algorithm to solve it.
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | R. Ahuja, T.K. Magnanti and J.B. Orlin, Network Flows, Theory, Algorithms and Applications. Prentice-Hall (1993). · Zbl 1201.90001 |
| [2] | H. Alt, N. Blum, K. Mehlhorn and M. Paul, Computing maximum cardinality matching in time O ( n 1 . 5 m / log | V | ) . Infor. Process. Lett.37 (1991) 237-240. · Zbl 0714.68036 |
| [3] | E. Balas and W. Pulleyblank, The perfectly matchable subgraph polytope of a bipartite graph. Networks13 (1983) 495-516. · Zbl 0525.90069 · doi:10.1002/net.3230130405 |
| [4] | E. Balas and W. Pulleyblank, The perfectly matchable subgraph polytope of an arbitrary graph. Combinatorica9 (1989) 321-337. · Zbl 0723.05087 · doi:10.1007/BF02125345 |
| [5] | M. L. Balinski, Signature methods for the assignment problem. Oper. Res.33 (1985) 527-536. Zbl0583.90064 · Zbl 0583.90064 · doi:10.1287/opre.33.3.527 |
| [6] | D. Cornaz and A.R. Mahjoub, The Maximum Induced Bipartite Subgraph Problem with Edge Weight. SIAM J. Discrete Math.3 (2007) 662-675. · Zbl 1141.05076 · doi:10.1137/060650015 |
| [7] | W.H. Cunningham and J. Green-Krotki, A separation algorithm for matchable set polytope. Math. Program.65 (1994) 139-150. Zbl0819.90120 · Zbl 0819.90120 · doi:10.1007/BF01581694 |
| [8] | M. Grotschel, L. Lovasz and A. Schrijver, Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin (1988). |
| [9] | F.A. Sharifov, Determination of the minimum cut using the base of an extended polymatroid. Cybern. Syst. Anal.6 (1997) 856-867 (translated from Kibernetika i Systemnyi Analis6 (1996) 138-152, in Russian). · Zbl 0892.90066 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
