We study bi-criteria approximation algorithms for vertex deletion problems in the (k,W) setting, where both the solution size and total weight are bounded simultaneously. Given a graph G, a weight function w:V → ℚ^+, a size bound k, and a weight budget W, a bi-criteria (a,b)-approximation algorithm either certifies that no solution of size at most k and weight at most W exists, or returns a solution of size at most ak and weight at most bW. Parameterizing by the solution size k - rather than the weight budget W - allows our algorithms to handle arbitrary positive rational weights without any lower bound assumption, addressing a fundamental limitation of prior W-parameterized approaches. We obtain two families of results. For general vertex deletion problems Π-Deletion admitting a polynomial-time weighted α-approximation, we obtain a polynomial-time (α(λ+1),α(1+1/(λ)))-approximation for any λ > 0, a randomized FPT improvement for problems admitting a sampling step, and a deterministic FPT version for problems with bounded obstruction size. For (k,W)-d-Hitting Set, which captures vertex deletion problems with obstruction size at most d, we design a polynomial-time (d,d)-approximation, a parameterized family of ((1-ε)d, d)-approximations improving the size factor below d, and two algorithms that simultaneously push both factors below d: a ((d+1)/2,(d+1)/2)-approximation and a more refined (d-γ,d-γ)-approximation for any γ ∈ (0,(d-1)/2). All algorithms work with arbitrary positive rational weights and are parameterized by the solution size k. To demonstrate the broad applicability of our framework, we instantiate our results on six well-studied vertex deletion problems: Cluster Vertex Deletion, FVS in Tournaments, Split Vertex Deletion, Feedback Vertex Set, d-Path Vertex Cover, and Pathwidth-One Vertex Deletion. In fact, our general results apply to any vertex deletion problem admitting a polynomial-time weighted approximation algorithm, and the six problems serve as representative examples spanning a range of obstruction structures - from bounded-size obstructions to unbounded ones. For (k,W) setting of Feedback Vertex Set and Pathwidth-One Vertex Deletion, we establish new sampling steps enabling the FPT approximation results. For Pathwidth-One Vertex Deletion, we additionally prove a polynomial-time 3-approximation for the weighted version on general graphs.

The pathwidth of a graph is a measure of how path-like the graph is. The Pathwidth One Vertex Deletion (POVD) problem asks whether, given an undirected graph G and an integer k, one can delete at most k vertices from G so that the remaining graph has pathwidth at most one. This is a natural variation of the classical Feedback vertex Set (FVS) problem, where the deletion of at most k vertices results in a graph of treewidth at most one. In this work, we investigate POVD in the realm of approximation algorithms. We first design a 3-approximation algorithm for POVD running in polynomial time. Then, using this constant factor approximation algorithm, we obtain a randomized parameterized approximation algorithm for POVD running in time 𝒪^*((h_β)^k), that improves the fastest existing running times for approximation ratios in the range (1.76147,3). Here the constant h_β depends on the approximation factor β alone and has value 2^{(3-β)}, which lies in the range (1,2.3596), when β ∈ (1.76147,3). Taking inspiration from two extensively studied problems, namely Connected FVS and Independent FVS, we investigate two variations of the POVD problem from the perspective of parameterized algorithms. These variations are the connected variant, called Connected pathwidth One Vertex Deletion (CPOVD) and the independent variant, called Independent Pathwidth One Vertex Deletion (IPOVD). While in CPOVD the subgraph G[S] induced by the vertices to be deleted needs to be connected, in IPOVD it needs to be independent. Specifically, we show the following results. - CPOVD can be solved in {𝒪}^*(14^k) time and admits no polynomial kernel unless NP ⊆ {co-NP/poly}. - IPOVD can be solved in {𝒪}^*(7^k) time, and admits a kernel of size 𝒪(k³).