Research on Matching and Vertex Cover Problems in Bipartite Graphs using Simplex Method
DOI:
https://doi.org/10.54097/hset.v38i.5737Keywords:
Bipartite graphs; linear programming; matchings; vertex covers; duality.Abstract
This paper considers a bipartite graph where a perfect matching does not necessarily exist. Linear programming is used in this paper as a special case of the linear program is the assignment problem, which is another name for the weighted maximum matching problem. The objective is to show that linear programming, in particular the simplex algorithm, can be used to calculate maximum weight matchings and minimum weighted vertex covers. This study also calculates and shows the equivalence of the maximum matching and minimum vertex cover cardinalities, and uses linear programming duality to present its relevance to König's theorem. Finally, Hall’s marriage theorem is used to explicitly prove the absence of a perfect matching in particular graphs. There exist many algorithms developed over the years that are designed to solve maximum matching problems in polynomial time, but the simplex method is one of the oldest and simplest algorithms to understand in solving these problems.
Downloads
References
Kench R. Bipartite Graphs. [online] Study.com. Available at: https://study.com/learn/lesson/bipartite-graph-applications-examples.html, [Accessed 18 August 2022]. 2022.
Matousek J. and GärtnerB. Understanding and using linear programming. Springer Science & Business Media. 2006.
Turner J. Applications of Matchings. [online] Available at: https://www.arl.wustl.edu/~jon.turner/cse/542/text/sec13.pdf, [Accessed 18 August 2022]. 2013.
Dharwadker A. and Pirzada S. Applications of Graph Theory. [online] Available at: https://www.dharwadker.org/pirzada/applications/, [Accessed 18 August 2022]. 2007.
Dinur I. and Safra S. On the hardness of approximating minimum vertex cover. Annals of mathematics, 2005, pp.439-485.
M, P. and user53923. Is maximum matching problem equivalent to maximum independent set problem in its dual graph? [online] Computer Science Stack Exchange. Available at: <https://cs.stackexchange.com/questions/69846/is-maximum-matching-problem-equivalent-to-maximum-independent-set-problem-in-its> [Accessed 18 August 2022]. 2017.
Hung M.S. A polynomial simplex method for the assignment problem. Operations Research, 1983, 31(3), pp.595-600.
Tanaka Y. Using the simplex method for a type of allocation problems. American Journal of Computational Mathematics, 2019, 9(2), pp.25-31.
Kuhn H. W. The Hungarian method for the assignment problem. Naval research logistics quarterly, 1955, 2, pp.83-97.
Cattrysse D. G. and Van Wassenhove L. N. A survey of algorithms for the generalized assignment problem. European journal of operational research, 1992, 60(3), pp.260-272.
Bipartite Graph. [online] Available at: <https://mathworld.wolfram.com/BipartiteGraph.html> [Accessed 18 August 2022]. 2022.
Ahmadi A. Bipartite matching and vertex covers. [online] Available at: <https://www.princeton.edu/~aaa/Public/Teaching/ORF523/ORF523_Lec6.pdf.> [Accessed 18 August 2022].
König D. Theorie der endlichen und unendlichen Graphen, Akad. Verlagsgeselschaft, Leipzig. 1936.
Hall P. On representatives of subsets. Classic Papers in Combinatorics, 1987, pp.58-62.
Metatrix et al. Python recursive function to display all subsets of given set. [online] Stack Overflow. Available at: <https://stackoverflow.com/questions/26332412/python-recursive-function-to-display-all-subsets-of-given-set.> [Accessed 18 August 2022]. 2014.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
How to Cite
