An efficient reduction of a gammoid to a partition matroid. (English) Zbl 07740917
Mutzel, Petra (ed.) et al., 29th annual European symposium on algorithms. ESA 2021, Lisbon, Portugal (virtual conference), September 6–8, 2021. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 204, Article 62, 13 p. (2021).
Summary: Our main contribution is a polynomial-time algorithm to reduce a k-colorable gammoid to a (2k-2)-colorable partition matroid.
It is known that there are gammoids that can not be reduced to any (2k-3)-colorable partition matroid, so this result is tight. We then discuss how such a reduction can be used to obtain polynomial-time algorithms with better approximation ratios for various natural problems related to coloring and list coloring the intersection of matroids.
For the entire collection see [Zbl 1473.68018].
It is known that there are gammoids that can not be reduced to any (2k-3)-colorable partition matroid, so this result is tight. We then discuss how such a reduction can be used to obtain polynomial-time algorithms with better approximation ratios for various natural problems related to coloring and list coloring the intersection of matroids.
For the entire collection see [Zbl 1473.68018].
MSC:
| 68Wxx | Algorithms in computer science |
