2017/08/02 by Kenjiro Takazawa, Takazawa, Kenjiro
Computer Science · Economics, Econometrics and Finance · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1708.00582
openalex publication_date 2017/08/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a framework for optimal t-matchings excluding the 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.