Inamdar, TanmayTanmayInamdarKanesh, LawqueenLawqueenKaneshKrithika, R.R.KrithikaMittal, HarshilHarshilMittalSaurabh, SaketSaketSaurabh2025-08-312025-08-312025-01-01[9783031987397]10.1007/978-3-031-98740-3_282-s2.0-105011939776http://repository.iitgn.ac.in/handle/IITG2025/28428In this work, we consider the optimization problem of finding a minimum-weight subset of vertices of a given undirected graph on n vertices whose deletion results in a d-degenerate graph. For d≥2, this problem is known to be constant-factor inapproximable implying that one cannot hope for anything better than bicriteria approximation algorithms. Towards this end, we give a randomized polynomial-time algorithm that for any value of the bicriteria approximation trade-off parameter α>1 and confidence parameter δ∈(0,1), returns a 2αd-degeneracy modulator whose weight is at most (1+δ)·2αα-1 times the weight of an optimum solution with high probability. Then, we move on to the decision problem of determining if a graph G on n vertices has a d-degeneracy modulator of size at most k. For each d≥2, this problem is known to be W[P]-hard with respect to k and we give three FPT-approximation algorithms for solving it. These algorithms return a 2αd-degeneracy modulator whose size is at most k (if a k-sized d-degeneracy modulator exists) for any α>1. All our algorithms can be tuned to return a 2d-degeneracy modulator of size at most k (if a k-sized d-degeneracy modulator exists) by setting α appropriately.falseConference Paper16113349391-40420250cpBook Series0