2023/11/20 by Miguel Bosch-Calvo, Fabrizio Grandoni, Bosch-Calvo, Miguel +3
Computer Science · #05C40 #05C70 (Secondary) #68R10 #68W25 (Primary) 68W40 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2311.11869
openalex publication_date 2023/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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⊆ 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. In his Ph.D. thesis from 1984, Harvitgsen presents a complex polynomial-time algorithm for this problem, with a very complex analysis. This result was never published in a journal nor reproved in a different way, to the best of our knowledge. 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).