Abstract
Abstract
In the Triangle-Free (Simple) 2-Matching problem we are given an undirected graph
$$G=(V,E)$$
G
=
(
V
,
E
)
. Our goal is to compute a maximum-cardinality
$$M\subseteq E$$
M
⊆
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).