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

CREATORYuhang Bai, Kristóf Bérczi, Johanna K. Siemelink
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-18263

Browse the full library · About the Tower of Babel