An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs

Vijay V. Vazirani

Papers from arXiv.org

Abstract: We prove that a fractional perfect matching in a non-bipartite graph can be written, in polynomial time, as a convex combination of perfect matchings. This extends the Birkhoff-von Neumann Theorem from bipartite to non-bipartite graphs. The algorithm of Birkhoff and von Neumann is greedy; it starts with the given fractional perfect matching and successively "removes" from it perfect matchings, with appropriate coefficients. This fails in non-bipartite graphs -- removing perfect matchings arbitrarily can lead to a graph that is non-empty but has no perfect matchings. Using odd cuts appropriately saves the day.

Date: 2020-10, Revised 2020-10
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://arxiv.org/pdf/2010.05984 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2010.05984

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().