Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2511.18263 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912726099427328 |
|---|---|
| author | Bai, Yuhang Bérczi, Kristóf Siemelink, Johanna K. |
| author_facet | Bai, Yuhang Bérczi, Kristóf Siemelink, Johanna K. |
| contents | In the Maximum-size Properly Colored Forest problem, we are given an edge-colored undirected graph and the goal is to find a properly colored forest with as many edges as possible. We study this problem within a broader framework by introducing the Maximum-size Degree Bounded Matroid Independent Set problem: given a matroid, a hypergraph on its ground set with maximum degree $Δ$, and an upper bound $g(e)$ for each hyperedge $e$, the task is to find a maximum-size independent set that contains at most $g(e)$ elements from each hyperedge $e$. We present approximation algorithms for this problem whose guarantees depend only on $Δ$. When applied to the Maximum-size Properly Colored Forest problem, this yields a $2/3$-approximation on multigraphs, improving the $5/9$ factor of Bai, Bérczi, Csáji, and Schwarcz [Eur. J. Comb. 132 (2026) 104269]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_18263 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximating maximum properly colored forests via degree bounded independent sets Bai, Yuhang Bérczi, Kristóf Siemelink, Johanna K. Data Structures and Algorithms In the Maximum-size Properly Colored Forest problem, we are given an edge-colored undirected graph and the goal is to find a properly colored forest with as many edges as possible. We study this problem within a broader framework by introducing the Maximum-size Degree Bounded Matroid Independent Set problem: given a matroid, a hypergraph on its ground set with maximum degree $Δ$, and an upper bound $g(e)$ for each hyperedge $e$, the task is to find a maximum-size independent set that contains at most $g(e)$ elements from each hyperedge $e$. We present approximation algorithms for this problem whose guarantees depend only on $Δ$. When applied to the Maximum-size Properly Colored Forest problem, this yields a $2/3$-approximation on multigraphs, improving the $5/9$ factor of Bai, Bérczi, Csáji, and Schwarcz [Eur. J. Comb. 132 (2026) 104269]. |
| title | Approximating maximum properly colored forests via degree bounded independent sets |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.18263 |