A PTAS for triangle-free 2-matching

Applied Nanoscience · Springer Nature · 2026-09-18 · DOI: 10.1007/s10107-026-02419-0

Аннотация

In the Triangle-Free (Simple) 2-Matching problem we are given an undirected graph $$G=(V,E)$$. Our goal is to compute a maximum-cardinality $$M\subseteq E$$ satisfying the following properties: (1) at most two edges of M are incident on each node (i.e., M is a 2-matching) and (2) M does not induce any triangle. Recently, Hartvigsen [J. Graph Theory 2024] published a complex polynomial-time algorithm for this problem, with a very complex analysis (spanning over 100 pages). This result was originally announced in his Ph.D. thesis from 1984. In this paper we have a fresh look at this problem and present a simple PTAS for it based on local search. Our PTAS exploits the fact that, as long as the current solution is far enough from the optimum, there exists a short augmenting trail (similar to the maximum matching case).

Читать у издателя →

Похожие статьи