A real polynomial for bipartite graph minimum weight perfect matchings. (English) Zbl 1531.05124
Summary: In a recent paper, G. Beniamini and N. Nisan [Isr. J. Math. 256, No. 1, 91–131 (2023; Zbl 1536.05365)] gave a closed-form formula for the unique multilinear polynomial for the Boolean function determining whether a given bipartite graph \(G\subseteq K_{n,n}\) has a perfect matching, together with an efficient algorithm for computing the coefficients of the monomials of this polynomial. We give the following generalization: Given an arbitrary weight function \(w\) on the edges of \(K_{n,n}\), consider its set of minimum weight perfect matchings. We give the real multilinear polynomial for the Boolean function which determines if a graph \(G\subseteq K_{n,n}\) contains one of these minimum weight perfect matchings. Finally, we discuss a number of open problems which follow from [Beniamini and Nisan, loc. cit.] and our work; in particular, extending the main theorem of [Beniamini and Nisan, loc. cit.] to non-bipartite graphs.
MSC:
| 05C31 | Graph polynomials |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C35 | Extremal problems in graph theory |
| 05C22 | Signed and weighted graphs |
| 06E30 | Boolean functions |
Citations:
Zbl 1536.05365Software:
OEISReferences:
| [1] | Anari, Nima; Vazirani, Vijay V., Matching is as easy as the decision problem, in the NC model, (11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (2020), Schloss Dagstuhl-Leibniz-Zentrum für Informatik) · Zbl 07650402 |
| [2] | Beniamini, Gal, The dual polynomial of bipartite perfect matching (2020), arXiv preprint |
| [3] | Birkhoff, Garrett, Rings of sets, Duke Math. J., 3, 3, 443-454 (1937) · Zbl 0017.19403 |
| [4] | Beniamini, Gal; Nisan, Noam, Bipartite perfect matching as a real polynomial, (Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021)), 1118-1131 · Zbl 1536.05366 |
| [5] | Billera, Louis J.; Sarangarajan, Aravamuthan, The combinatorics of permutation polytopes, (Formal Power Series and Algebraic Combinatorics, vol. 24 (1994)), 1-23 · Zbl 0839.52007 |
| [6] | Fenner, Stephen; Gurjar, Rohit; Thierauf, Thomas, Bipartite perfect matching is in quasi-NC, (Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (2016), Association for Computing Machinery: Association for Computing Machinery New York, NY, USA), 754-763 · Zbl 1373.68267 |
| [7] | Gusfield, Dan; Irving, Robert W., The Stable Marriage Problem: Structure and Algorithms (1989), MIT Press · Zbl 0703.68046 |
| [8] | Lovász, L.; Plummer, M. D., Matching Theory (1986), North-Holland: North-Holland Amsterdam-New York · Zbl 0618.05001 |
| [9] | O’Donnell, Ryan, Analysis of Boolean Functions (2014), Cambridge University Press · Zbl 1336.94096 |
| [10] | Sloane, Neil J. A.; The OEIS Foundation Inc., The on-Line Encyclopedia of Integer Sequences (2021) · Zbl 1494.68308 |
| [11] | Stanley, Richard, Enumerative Combinatorics, vol. 1 (1996), Wadsworth and Brooks/Cole: Wadsworth and Brooks/Cole Pacific Grove, CA |
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.
