CS Paper Radar

Layering and reverse extension for weighted $k$-path vertex cover

Jiajing Wu, An Zhang, Shiming Li, Guohui Lin

cs.DS cs.DM ·submitted 2026-10-29 15:34 UTC · v1

Abstract

We study the weighted $k$-path vertex cover problem for any fixed integer $k \ge 2$, in which a vertex non-negatively weighted simple graph $G = (V, E)$ is given and one wants to find a minimum-weight vertex subset $C \subseteq V$ such that every simple path on $k$ vertices in $G$ contains at least one vertex of $C$. The problem generalizes the classic weighted vertex cover problem, that is, $k = 2$, and it admits a $k$-approximation algorithm of Hochbaum~[SIAM J. Comput., 1982] and a $(k - \frac 12)$-approximation algorithm of Brüstle et al.~[IWOCA 2021]. In this paper, we carefully design local weight functions in the Layering and Reverse Extension local ratio framework of Bar-Yehuda et al.~[ACM Comput. Surv., 2004], leading to an approximation algorithm of ratio $\frac {3k-1}4$ for odd $k \ge 3$ and of ratio $\frac {3k}4$ for even $k \ge 4$. When $k = 3$ and $k = 4$, these ratios are $2$ and $3$, respectively, matching the state-of-the-art approximation ratios for the corresponding special cases.

Comment
13 pages; submitted for publication

Closest papers

Nearest neighbours by meaning across the whole index.

Minimum Sum Vertex Cover via Minimum Vertex Cover

cs.DS cs.DM ·2026-09-22 ·Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Saeed Odak, Michiel Smid
theory similarity 0.70
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.

0.20

Subexponential algorithms for structural parameterizations of Vertex Cover in geometric graphs

cs.DS ·2026-11-16 ·Marin Bougeret, Juan Pablo Bravo, Daniel Gonçalves
theory similarity 0.66
Abstract · 43 pages, 8 figures, submitted

A number of recent works have investigated the existence of parameterized subexponential algorithms in geometric graph classes for hitting a fixed small graph as a subgraph or as a minor. In this setting, given an $n$-vertex graph, the goal is to decide in time $n^{O(1)}2^{o(k)}$ if a solution of size at most $k$ exists. Inspired by recent results in kernelization for structural parameters, we investigate subexponential algorithms for the Vertex Cover (VC) problem, but parameterized by distance-to-triviality instead of solution size. More formally, given a fixed "trivial" graph class $\mathcal{C}$, the problem takes as input $(G,X,k)$, where $G \setminus X \in \mathcal{C}$, and asks if $G$ admits a vertex cover of size at most $k$. Our goal is to design algorithms for this problem running in time $n^{O(1)}2^{o(|X|)}$. The motivation is that, since $|X|$ is typically arbitrarily smaller than $k$, such algorithms might be faster than ETH-tight subexponential algorithms parameterized by $k$. We identify two sets of sufficient conditions under which the problem admits a subexponential algorithm: one for the case where $\mathcal{C}$ is the class of paths, and another for the case where $\mathcal{C}$ is the class of graphs of constant treedepth. We also provide two applications of these algorithmic results: we prove that $s$-string graphs and pseudo-disk graphs satisfy the first set of conditions, whereas string graphs satisfy the second set. The two sets share a common condition that might be of independent interest, as it implies a property that bounds the treewidth of any string graph in terms of a given modulator to a fixed graph class $\mathcal{C}$. Finally, concerning more restricted graph classes having the $ASQGM(ω)$ property (such as map graphs and $H$-minor free graphs), we prove a dichotomy, depending on the maximum treewidth in $\mathcal{C}$.

0.14

Improved Multilayered PCPs and Hypergraph Vertex Cover

cs.CC cs.DS ·2026-09-06 ·Karthik C. S., Dor Minzer
similarity 0.65
Abstract

We present two elementary constructions of multilayered PCPs that improve upon prior constructions in two ways. Specifically, we give one construction of quasi-linear size, and another one with $2$-to-$2$ constraints. Using these constructions we obtain the following results for the hypergraph vertex cover problem: $\bullet$ For $k=3$, for all $\varepsilon>0$, approximating the minimum vertex cover of a given $3$-uniform hypergraph within factor $1+\sqrt{2}-\varepsilon$ is NP-hard. Previously, the best known result due to [Dinur, Guruswami, Khot, Regev, SICOMP 2005] achieved a factor of $2-\varepsilon$. $\bullet$ For $k\geq 4$, for all $\varepsilon>0$, approximating the minimum vertex cover of a given $k$-uniform hypergraph within factor $k-\varepsilon$ is NP-hard, which is tight. Previous works established this result assuming the Unique-Games Conjecture [Khot, Regev, JCSS 2008], and a weaker factor of $k-1-\varepsilon$ for standard NP-hardness [Dinur, Guruswami, Khot, Regev, SICOMP 2005]. $\bullet$ Assuming the Exponential Time Hypothesis, for all $k\geq 3$ and $\varepsilon>0$ there is $C>0$ such that no $2^{n/\log^C n}$-time algorithm approximates the minimum vertex cover in a $k$-uniform, $n$-vertex hypergraph within factor $k-1-\varepsilon$. The proofs were obtained using ChatGPT 5.6 Pro and subsequently rewritten by the communicators.

0.07

Online and Incremental Fractional Vertex Cover on Trees

cs.DS ·2026-08-25 ·Júlia Baligács, Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Grzegorz Gutowski +3 more
publishedtheory similarity 0.64
Abstract

In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori and the edges arrive one at a time. The goal is to maintain a fractional vertex cover of the tree, i.e., an assignment of fractional weights from [0,1] to the vertices such that the weights of endpoints of every edge sum up to at least one. After each edge arrival, we need to modify the fractional vertex cover to cover the new edge as well. However, we can only increase the values assigned to vertices. The problem was studied before (in the vertex arrival model) by Wang and Wong, who motivated it as a generalization of the ski-rental problem, but also (more importantly) by its close connection to the dual online matching problem. They presented a 1.901-competitive algorithm for general graphs in the vertex arrival model. We present an $\frac{11}{6} \approx 1.83$-competitive algorithm for trees in the more general edge arrival model. In addition, we study the fractional vertex cover problem in an incremental model, where we again seek a fractional vertex cover after every update, but all the updates to the tree are known to the algorithm a priori. In this model, we give a 1.5-competitive algorithm and provide a matching lower bound.

0.46

An iterative rounding $2$-approximation for Feedback Vertex Set via AI-assisted proof of an extreme point property

cs.DS ·2026-09-03 ·Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni
theory similarity 0.63
Abstract

We consider the Feedback Vertex Set problem (FVS): the input is an undirected graph $G=(V,E)$ and the goal is to find a minimum-cardinality (or a min-cost in the weighted case) subset $S \subseteq V$ of vertices such that $G-S$ has no cycles. A $2$-approximation via the local-ratio method was developed in the mid 90's by Bafna, Berman and Fujito (1995) and by Becker and Geiger (1996), and this approximation ratio is tight under UGC. The local-ratio algorithms were later interpreted as primal-dual algorithms via an LP relaxation by Chudak, Goemans, Hochbaum, and Williamson (1998). All known $2$-approximation algorithms for FVS have been via local-ratio and primal-dual methods, and in a quest to obtain a new LP rounding algorithm, it was conjectured (Fiorini 2021) that the Strong-Density polyhedron developed by Chudak, Goemans, Hochbaum, and Williamson has an extreme point property: every basic feasible solution to the LP has a variable with value at least $1/2$. We prove this conjecture. We also consider a related Strong-Edge-Density polyhedron and show the same extreme point property. The advantage of this polyhedron is that it admits a polynomial-time separation oracle and also a compact extended formulation. These results lead to polynomial-time iterative rounding $2$-approximation algorithms. The proof of the extreme point property is of independent technical interest and key ideas in the proof were suggested by AI tools.

0.31

Vertex-Coloring Edge-Weighting: Kernelization and Generalization

cs.DS cs.CCcs.DM ·2026-09-23 ·Shubhada Aute, Fahad Panolan, Geevarghese Philip
similarity 0.62
Abstract · 46 page, 2 figures

An edge weighting of a graph induces a coloring of its vertices in which the color of a vertex is the total weight of the edges incident with it. Such an edge weighting is proper if adjacent vertices always receive distinct colors. Deciding whether a graph admits a proper weighting is known to be NP-complete for the weight set $\{0,1\}$, and also for $\{1,2\}$. In recent work (arXiv:2604.12363) we showed that both problems are FPT parameterized by the vertex cover number $k$, but it was open -- to the best of our knowledge -- whether either parameterized problem had a polynomial kernel. In this work, we show that both problems have polynomial kernels when parameterized by $k$. We also show that both problems are W[1]-hard parameterized by treedepth, answering another question from our earlier work. We then study the pre-weighted versions of the two problems, in which the weights of some edges are fixed in advance, and the task is to extend the assignment to a proper weighting of the whole graph. We show that both pre-weighted problems are FPT parameterized by the vertex cover number $k$. For the $\{1,2\}$ version the running time is $2^{O(k \log k)} \cdot n$; for the $\{0,1\}$ version we obtain the same running time when every pre-weight is $1$, and a slower FPT algorithm in the general case. We also show that both pre-weighted problems are W[1]-hard parameterized by either of (i) the feedback vertex set number or (ii) the treedepth of the input graph. Since a graph with no pre-assigned weights is a special case, our algorithms for the pre-weighted versions solve the two original problems as well, in time $2^{O(k \log k)} \cdot n$, significantly improving on the bound of $2^{O(k^4)} \cdot n^{O(1)}$ from our earlier work.

0.29

When is greedy exact for weighted minimum 3-cut?

cs.DS ·2026-10-26 ·Armando Rodado Amaris
theorycode/data similarity 0.62
Abstract · 16 pages. Lean 4 proofs and Python reproduction scripts are provided as ancillary files and at https://github.com/armandorodado/minimum-3cut…

The greedy algorithm for minimum 3-cut splits a global minimum-weight cut and then the cheaper of its two sides; it is a tight $4/3$-approximation. We show that it is exact, from every global minimum-weight cut, whenever some optimal 3-partition has two parts joined by total weight at least the weighted edge connectivity $λ$. This extends both theorems of Hochbaum and Shmoys from unweighted planar graphs to all weighted graphs, recovers the $4/3$ bound, and generalizes to minimum $k$-cut with a one-paragraph proof. The remaining hard instances have all pair weights below $λ$; for them we prove a merge lemma for Gomory-Hu sides. Finally, we give a 7-vertex graph with a unique Gomory-Hu tree whose unique optimal 3-partition contains no side of that tree, so the first stage of Kapoor's algorithm does not suffice on its own. The main theorem, the 4/3 bound, the merge lemmas and the counterexample are verified in the Lean 4 proof assistant.

0.44

A 4.542-approximation for the Small Cuts Cover problem via a multi-rate primal-dual algorithm

cs.DS ·2026-11-17 ·Zeev Nutov, Elazar Koren
similarity 0.62
Abstract

In the Small Cuts Cover problem we seek to cover by a min-cost edge-set the set-family of cuts of size $<k$ of a graph. Bansal, Cheriyan, Grout, and Ibrahimpur [ICALP 2023: 15:1-15:19] showed that the classic primal-dual algorithm with reverse delete of Williamson, Goemans, Mihail, and Vazirani [STOC 1993: 708-717] achieves approximation ratio $16$ for this problem. The analysis of the approximation ratio was then improved in a sequence of papers, culminating in the $5$-approximation by Simons, Bansal, and Cheriyan. A matching example of Nutov shows that this bound is tight for the classic algorithm. We improve the approximation ratio to $(3+\sqrt{37})/2<4.542$ using a multi-rate primal-dual algorithm (that applies for strongly pliable set-families) in which the dual variables of the inclusion-minimal violated sets are not raised uniformly, but with different rates. We also provide a tight example. To the best of our knowledge, this is the first example in network design where for the standard LP, an efficiently computable choice of growth rates improves on the tight guarantee of uniform growth.

0.21