Options
FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less
Journal
Leibniz International Proceedings in Informatics, LIPIcs
ISSN
18688969
Date Issued
2023-12-01
Author(s)
Abstract
For numerous graph problems in the realm of parameterized algorithms, using the size of a smallest deletion set (called a modulator) into well-understood graph families as parameterization has led to a long and successful line of research. Recently, however, there has been an extensive study of structural parameters that are potentially much smaller than the modulator size. In particular, recent papers [Jansen et al. STOC 2021; Agrawal et al. SODA 2022] have studied parameterization by the size of the modulator to a graph family H (modH()), elimination distance to H (edH()), and H-treewidth (twH()). These parameters are related by the fact that twH lower bounds edH, which in turn lower bounds modH. While these new parameters have been successfully exploited to design fast exact algorithms their utility (especially that of edH and twH) in the context of approximation algorithms is mostly unexplored. The conceptual contribution of this paper is to present novel algorithmic meta-theorems that expand the impact of these structural parameters to the area of FPT Approximation, mirroring their utility in the design of exact FPT algorithms. Precisely, we show that if a covering or packing problem is definable in Monadic Second Order Logic and has a property called Finite Integer Index (FII), then the existence of an FPT Approximation Scheme (FPT-AS, i.e., (1)-approximation) parameterized by modH(), edH(), and twH() is in fact equivalent. As a consequence, we obtain FPT-ASes for a wide range of covering, packing, and domination problems on graphs with respect to these parameters. In the process, we show that several graph problems, that are W[1]-hard parameterized by modH, admit FPT-ASes not only when parameterized by modH, but even when parameterized by the potentially much smaller parameter twH(). In the spirit of [Agrawal et al. SODA 2022], our algorithmic results highlight a broader connection between these parameters in the world of approximation. As concrete exemplifications of our meta-theorems, we obtain FPT-ASes for well-studied graph problems such as Vertex Cover, Feedback Vertex Set, Cycle Packing and Dominating Set, parameterized by twH() (and hence, also by modH() or edH()), where H is any family of minor free graphs.
Volume
284