Excluded t-factors in bipartite graphs: A unified framework for nonbipartite matchings, restricted 2-matchings, and matroids
Excluded t-factors in bipartite graphs: A unified framework for nonbipartite matchings, restricted 2-matchings, and matroids
复制标题
二分图中排除的 t 因子：非二分匹配、受限 2 匹配和拟阵的统一框架
DOI：
10.1137/18m1176737
复制
发表时间：
2022
影响因子：
0.8
通讯作者：
Kenjiro Takazawa
中科院分区：
文献类型：
--
作者：
Nicolas Bousquet;Takehiro Ito;Yusuke Kobayashi;Haruka Mizuta;Paul Ouvrard;Akira Suzuki and Kunihiro Wasa;Kenjiro Takazawa
我们提出了一个排除二分图中规定因素的最佳匹配框架。所提出的框架是非二分匹配问题的推广，包括多个问题，例如无三角形2-匹配、无正方形2-匹配、偶数因子和树状问题。在本文中，我们通过共同扩展以前的重要结果来展示对这些问题的统一理解。 我们在合理的假设下解决我们的问题，该假设足够广泛，可以包括上面列出的具体问题。我们首先提出最小-最大定理和未加权版本的组合算法。然后，我们提供具有对偶完整性的线性规划公式和加权版本的原对偶算法。该算法的一个关键要素是收缩禁止结构的技术，它分别对应于Edmonds开花算法、无三角形2匹配算法、无正方形2匹配算法和树状算法中的奇数循环、三角形、正方形和有向循环的收缩技术。
We propose a framework for optimal-matchings excluding prescribed-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.