License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.27
URN: urn:nbn:de:0030-drops-161874
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16187/
Huang, Chien-Chung ;
Sellier, François
Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms
Abstract
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.
BibTeX - Entry
@InProceedings{huang_et_al:LIPIcs.SWAT.2022.27,
author = {Huang, Chien-Chung and Sellier, Fran\c{c}ois},
title = {{Matroid-Constrained Maximum Vertex Cover: Approximate Kernels and Streaming Algorithms}},
booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages = {27:1--27:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-236-5},
ISSN = {1868-8969},
year = {2022},
volume = {227},
editor = {Czumaj, Artur and Xin, Qin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16187},
URN = {urn:nbn:de:0030-drops-161874},
doi = {10.4230/LIPIcs.SWAT.2022.27},
annote = {Keywords: Maximum vertex cover, matroid, approximate kernel, streaming}
}
|
Keywords: |
|
Maximum vertex cover, matroid, approximate kernel, streaming |
|
Collection: |
|
18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
22.06.2022 |
