Approximation and exact algorithms improve vertex cover ordering in graphs
Minimum Sum Vertex Cover via Minimum Vertex Cover
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The Minimum Sum Vertex Cover problem asks how to order nodes in a network so that the connections are covered as early as possible. The authors show that by using minimum vertex covers, they can find good orderings efficiently for certain types of networks. They also develop exact algorithms for graphs with specific structural properties and prove that the problem is very hard for planar graphs. This work improves how quickly and accurately the problem can be solved under different conditions.
What this means in practice
- •For network schedulers: Create efficient sequences to monitor or cover network connections earlier by exploiting minimum vertex cover strategies for graphs with bounded node degree.
- •For graph algorithm engineers: Implement exact solutions for vertex cover ordering in planar or special graph classes to improve analysis and optimization tools.
Authors
Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Saeed Odak, Michiel Smid
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.