2025/11/23 by Bai, Yuhang, Bérczi, Kristóf, Siemelink, Johanna K.
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation
paper · doi:10.48550/arxiv.2511.18263
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].