Matroid-constrained vertex cover

DOI10.1016/J.TCS.2023.113977MaRDI QIDQ6162073zbMATH OpenFDO

Authors Chien-Chung Huang

Publication date 15 June 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2306.04342

zbMATH Keywords

kernellocal searchmatroidvertex cover

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Signed and weighted graphs (05C22) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Abstract: In this paper, we introduce the problem of Matroid-Constrained Vertex Cover: 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, in which the matroid is the simple uniform matroid, and it is also a special case of the problem of maximizing a monotone submodular function under a matroid constraint. First, 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-varepsilon)$ approximation using $(1/varepsilon{)}^{O(k)}{n}^{O(1)}$ time for partition and laminar matroids and using $(1/varepsilon+k{)}^{O(k)}{n}^{O(1)}$ time for transversal matroids. This extends a result of Manurangsi for uniform matroids [Manurangsi, 2018]. We also show that these ideas can be applied in the context of (single-pass) streaming algorithms. Besides, our FPT-AS introduces a new technique based on matroid union, which may be of independent interest in extremal combinatorics. In the second part, we consider general matroids. We propose a simple local search algorithm that guarantees $2/3approx0.66$ approximation. For the more general problem where two matroids are imposed on the vertices and a feasible solution must be a common independent set, we show that a local search algorithm gives a $2/3cdot(1-1/(p+1))$ approximation in $n^{O(p)}$ time, for any integer $p$. We also provide some evidence to show that with the constraint of one or two matroids, the approximation ratio of $2/3$ is likely the best possible, using the currently known techniques of local search.

Recommendations

• The matroid intersection cover problem
• Deterministic parameterized connected vertex cover
• On the max min vertex cover problem
• On the max min vertex cover problem
• The minimum generalized vertex cover problem
• Algorithms - ESA 2003
• Approximation algorithm for vertex cover with multiple covering constraints
• Approximation algorithm for vertex cover with multiple covering constraints
• scientific article; zbMATH DE number 2119748
• Vertex cover problem parameterized above and below tight bounds

Cites work

• A new series of dense graphs of high girth
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• A simple PTAS for weighted matroid matching on strongly base orderable matroids
• Algorithms and Data Structures
• An improved rounding method and semidefinite programming relaxation for graph partition
• Applications of the notion of independence to problems of combinatorial analysis
• Approximate multi-matroid intersection via iterative refinement
• Approximation algorithms for maximization problems arising in graph partitioning
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Data streams: algorithms and applications.
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
• scientific article; zbMATH DE number 50766 (Why is no real title available?)
• scientific article; zbMATH DE number 1323125 (Why is no real title available?)
• scientific article; zbMATH DE number 1342117 (Why is no real title available?)
• Improved competitive ratio for the matroid secretary problem
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Lossy kernelization
• Matroids, secretary problems, and online mechanisms
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Monotone submodular maximization over a matroid via non-oblivious local search
• New bounds for the CLIQUE-GAP problem using graph decomposition theory
• On approximation of max-vertex-cover
• Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
• Secretary problems: laminar matroid and interval scheduling
• Streaming algorithms for submodular function maximization
• Submodular maximization over multiple matroids via generalized exchange properties
• Testing membership in matroid polyhedra
• The power of local search: maximum coverage over a matroid
• Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
• Transversal Theory and Matroids
• Transversals and matroid partition

Cited in

(2)

• Knapsack Cover Subject to a Matroid Constraint
• A note on robust subsets of transversal matroids

This page was built for publication: Matroid-constrained vertex cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6162073)