Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden Triangles

• 成果类型: Article
• 署名作者: Kobayashi, Yusuke
• 署名单位: Kyoto University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01661-y
• 发表日期: 2022
• 页码: 675-702
• 关键词: square-free 2-matchings; minimum cut-sets; even factors; t-matchings; bipartite; algorithms

摘要

The weighted T-free 2-matching problem is the following problem: given an undirected graph G, a weight function on its edge set, and a set T of triangles in G, find a maximum weight 2-matching containing no triangle in T. When T is the set of all triangles in G, this problem is known as the weighted triangle-free 2-matching problem, which is a long-standing open problem. A main contribution of this paper is to give the first polynomial-time algorithm for the weighted T-free 2-matching problem under the assumption that T is a set of edge-disjoint triangles. In our algorithm, a key ingredient is to give an extended formulation representing the solution set, that is, we introduce new variables and represent the convex hull of the feasible solutions as a projection of another polytope in a higher dimensional space. Although our extended formulation has exponentially many inequalities, we show that the separation problem can be solved in polynomial time, which leads to a polynomial-time algorithm for the weighted T-free 2-matching problem.