Approximating Maximum Properly Colored Forests via Degree Bounded Independent Sets
Yuhang Bai, Kristóf Bérczi, Johanna K. Siemelink · 2025
Read Approximating Maximum Properly Colored Forests via Degree Bounded Independent Sets by Yuhang Bai, Kristóf Bérczi, Johanna K. Siemelink (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-18263.txt.
Description
Yuhang Bai, Kristof Berczi, and Johanna Siemelink study a combinatorial problem. In a graph whose edges are colored, the goal is to find a forest with as many edges as possible such that no two edges sharing a vertex share a color. They approach it through a broader problem about independent sets in matroids with limits on how many elements each group may contribute.
They give approximation algorithms whose guarantees depend only on the maximum degree of the grouping structure. Applied to the colored forest problem on multigraphs, the method guarantees two thirds of the optimum, improving a previously known factor. The broader framing may help other constrained selection problems.
Catalog record
| CREATOR | Yuhang Bai, Kristóf Bérczi, Johanna K. Siemelink |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-18263