Abstract
Matchings and perfect matchings have received considerable attention in graph theory as well as in other related domains (such as, but not limited to, algorithms and optimization). There still remain many open problems — such as Barnette’s conjecture, Berge-Fulkerson conjecture, and so on — due to which it continues to remain an active area of research. For problems pertaining to perfect matchings, it is well-known that it suffices to solve them for matching covered graphs (that is, those connected graphs wherein each edge belongs to some perfect matching). The theory of matching covered graphs, despite its relatively recent emergence, presents an exciting landscape filled with captivating discoveries, elegant proofs, and unexpected applications. In the following paragraph, we briefly summarize some of the key developments in this field without going into the mathematical details.
Kotzig [3], in 1959, introduced the notion of canonical partition of a matching covered graph that uniquely partitions its vertex set into its maximal barriers. In 1987, László Lovász [5] established the uniqueness of the tight cut decomposition procedure; as per this, every matching covered graph may be uniquely decomposed into a list of special matching covered graphs called bricks (nonbipartite) and braces (bipartite). The key contribution of this landmark paper was to solve the Matching Lattice Problem. Lovász and Plummer, in 1975, introduced the well-known ear decomposition of matching covered graphs; see Matching Theory [4]. This notion of ear decomposition was further refined to that of an optimal ear decomposition by Carvalho, Lucchesi and Murty [2]. Furthermore, in their seminal paper, the same authors [1] introduced the dependency relationship in matching covered graphs that is closely tied with the ear decomposition theory. In 2001, McCuaig [7] established a generation method for all braces; analogously, Norine and Thomas [9], in 2007, established a generation method for all bricks. Both of these generation procedures may be viewed as a synthesis of the ear decomposition and tight cut decomposition theories, and have found applications in solving some of the major problems in matching theory — such as Polya’s Permanent Problem [8]. All of these results — pertaining to decompositions, generation methods and related concepts — have played indispensable roles in the advancement of matching theory, and continue to do so.
It is worth noting that all of the notions discussed above are computable in poly-time. Despite this, there are no publicly available implementations. It is for this reason that researchers in this area are at a loss, and are required to implement parts of this theory by themselves. Currently, in SageMath, a few existing matching-theoretic algorithms for general graphs have been put within the module Undirected graphs — either under the submodule Algorithmically hard stuff (for instance: matching_polynomial()) or under Leftovers (for instance: has_perfect_matching(), matching(), is_factor_critical() and perfect_matchings()), whereas that concerning the bipartite graphs have been put within the module Bipartite Graphs (for instance: matching(), matching_polynomial() and perfect_matchings()). Ergo, we propose to implement efficient algorithms pertaining to the results and concepts discussed in the above paragraph in SageMath, and to make all of these available freely to students, educators as well as researchers all across the world.
This proposal has been inspired by the book of Lucchesi and Murty — Perfect Matchings: a theory of matching covered graphs [6].
References