arXiv preprint ·
Minimum Sum Vertex Cover via Minimum Vertex Cover
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered. We study the problem through the structure of vertex covers and obtain new approximation and exact algorithms, together with conditional lower bounds. For graphs of maximum degree $Δ$, we show that a simple ordering algorithm based on a minimum vertex cover achieves approximation ratio $R_Δ\le {(\sqrtΔ+1)}/{2}$. For $d$-regular graphs, we give a polynomial-time $1.184$-approximation by combining Max-$k$-Vertex-Cover approximation with a structural bound on optimal prefixes. On the exact side, we give an algorithm parameterized by the vertex cover number $k$ running in $2^{O(k\log k)} + O(n+m)$ time, improving the previous dependence on $k$, where $n$ and $m$ are the number of vertices and edges in the graph, respectively. We also develop a separator-based exact algorithm running in $ 2^{O(\sqrt n \log n)}$ time on planar, bounded-genus, and fixed-minor-free graph classes. Finally, we prove that Minimum Sum Vertex Cover is NP-hard on planar graphs and, assuming ETH, admits no $2^{o(\sqrt n)}$-time exact algorithm on $n$-vertex planar graphs. Thus our planar upper bound is tight up to logarithmic factors in the exponent.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Factorisability of Low Dimensional Non-Negative Integer Matrices
Vertex-Coloring Edge-Weighting: Kernelization and Generalization
Backtracking Candidate Elimination: A One-Pass Algorithm for the Chip Testing Problem
Inverse knapsack at two capacities: which pairs of value-cardinality hulls are realizable?
Transposition achieves OPT$+O(1)$ in polynomial time for IID list update
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.