{"ID":2837883,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.18263","arxiv_id":"2511.18263","title":"Approximating maximum properly colored forests via degree bounded independent sets","abstract":"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].","short_abstract":"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 ma...","url_abs":"https://arxiv.org/abs/2511.18263","url_pdf":"https://arxiv.org/pdf/2511.18263v1","authors":"[\"Yuhang Bai\",\"Kristóf Bérczi\",\"Johanna K. Siemelink\"]","published":"2025-11-23T03:26:47Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}