Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids
Kenjiro Takazawa · SIAM Journal on Discrete Mathematics · 2022
We propose a framework for optimal $t$-matchings excluding prescribed $t$-factors in bipartite graphs. The proposed framework is a generalization of the nonbipartite matching problem and includes several problems, such as the triangle-free 2-matching, square-free 2-matching, even factor, and arborescence problems. In this paper, we demonstrate a unified understanding of these problems by commonly extending previous important results. We solve our problem under a reasonable assumption, which is sufficiently broad to include the specific problems listed above. We first present a min-max theorem and a combinatorial algorithm for the unweighted version. We then provide a linear programming formulation with dual integrality and a primal-dual algorithm for the weighted version. A key ingredient of the proposed algorithm is a technique to shrink forbidden structures, which corresponds to the techniques of shrinking odd cycles, triangles, squares, and directed cycles in Edmonds' blossom algorithm, a triangle-free 2-matching algorithm, a square-free 2-matching algorithm, and an arborescence algorithm, respectively.