2026-07-26T00:39:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16187 2024-03-06T10:57:06Z ddc:004 open_access

Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms Huang, Chien-Chung Sellier, François Maximum vertex cover matroid approximate kernel streaming Given a graph with weights on the edges and a matroid imposed on the vertices, our problem is to choose a subset of vertices that is independent in the matroid, with the objective of maximizing the total weight of covered edges. This problem is a generalization of the much studied max k-vertex cover problem, where the matroid is the simple uniform matroid, and it is also a special case of maximizing a monotone submodular function under a matroid constraint. In this work, we give a Fixed Parameter Tractable Approximation Scheme (FPT-AS) when the given matroid is a partition matroid, a laminar matroid, or a transversal matroid. Precisely, if k is the rank of the matroid, we obtain (1 - ε) approximation using (1/(ε))^{O(k)}n^{O(1)} time for partition and laminar matroids and using (1/(ε)+k)^{O(k)}n^{O(1)} time for transversal matroids. This extends a result of Manurangsi for uniform matroids [Pasin Manurangsi, 2018]. We also show that these ideas can be applied in the context of (single-pass) streaming algorithms. Our FPT-AS introduces a new technique based on matroid union, which may be of independent interest in extremal combinatorics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chien-Chung Huang and François Sellier 2022 Is Part Of LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2022.27 urn:nbn:de:0030-drops-161874 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.27 eng https://creativecommons.org/licenses/by/4.0/legalcode