Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2603.09144 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915849591324672 |
|---|---|
| author | Bosch-Calvo, Miguel Grandoni, Fabrizio Kobayashi, Yusuke Noguchi, Takashi |
| author_facet | Bosch-Calvo, Miguel Grandoni, Fabrizio Kobayashi, Yusuke Noguchi, Takashi |
| contents | In the Weighted Triangle-Free 2-Matching problem (WTF2M), we are given an undirected edge-weighted graph. Our goal is to compute a maximum-weight subgraph that is a 2-matching (i.e., no node has degree more than $2$) and triangle-free (i.e., it does not contain any cycle with $3$ edges). One of the main motivations for this and related problems is their practical and theoretical connection with the Traveling Salesperson Problem and with some $2$-connectivity network design problems. WTF2M is not known to be NP-hard and at the same time no polynomial-time algorithm to solve it is known in the general case (polynomial-time algorithms are known only for some special cases). The best-known (folklore) approximation algorithm for this problem simply computes a maximum-weight 2-matching, and then drops the cheapest edge of each triangle: this gives a $2/3$ approximation. In this paper we present a PTAS for WTF2M, i.e., a polynomial-time $(1-\varepsilon)$-approximation algorithm for any given constant $\varepsilon>0$. Our result is based on a simple local-search algorithm and a non-trivial analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_09144 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A PTAS for Weighted Triangle-free 2-Matching Bosch-Calvo, Miguel Grandoni, Fabrizio Kobayashi, Yusuke Noguchi, Takashi Data Structures and Algorithms In the Weighted Triangle-Free 2-Matching problem (WTF2M), we are given an undirected edge-weighted graph. Our goal is to compute a maximum-weight subgraph that is a 2-matching (i.e., no node has degree more than $2$) and triangle-free (i.e., it does not contain any cycle with $3$ edges). One of the main motivations for this and related problems is their practical and theoretical connection with the Traveling Salesperson Problem and with some $2$-connectivity network design problems. WTF2M is not known to be NP-hard and at the same time no polynomial-time algorithm to solve it is known in the general case (polynomial-time algorithms are known only for some special cases). The best-known (folklore) approximation algorithm for this problem simply computes a maximum-weight 2-matching, and then drops the cheapest edge of each triangle: this gives a $2/3$ approximation. In this paper we present a PTAS for WTF2M, i.e., a polynomial-time $(1-\varepsilon)$-approximation algorithm for any given constant $\varepsilon>0$. Our result is based on a simple local-search algorithm and a non-trivial analysis. |
| title | A PTAS for Weighted Triangle-free 2-Matching |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.09144 |