2026-07-23T21:24:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14643 2024-03-06T10:54:31Z ddc:004 open_access

An Efficient Reduction of a Gammoid to a Partition Matroid Leichter, Marilena Moseley, Benjamin Pruhs, Kirk Matroid Gammoid Reduction Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marilena Leichter and Benjamin Moseley and Kirk Pruhs 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.62 urn:nbn:de:0030-drops-146432 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.62 eng https://creativecommons.org/licenses/by/4.0/legalcode