A PTAS for Triangle-Free 2-Matching.
CoRR(2023)
摘要
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. 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).
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要