Approximation and parameterized algorithms for geometric independent set with shrinking

Abstract

Consider the Maximum Weight Independent Setproblem for rectangles: given a family ofweighted axis-parallel rectangles in the plane, find a maximum-weight subset of non-overlappingrectangles. The problem is notoriously hard both in the approximation and in the parameterizedsetting. The best known polynomial-time approximation algorithms achieve super-constant ap-proximation ratios [5, 7], even though there is a(1+ )-approximation running in quasi-polynomialtime [2, 8]. When parameterized by the target size of the solution, the problem isW[1]-hard evenin the unweighted setting [12].To achieve tractability, we study the followingshrinking model: one is allowed to shrink eachinput rectangle by a multiplicative factor1−δfor some fixedδ >0, but the performance isstill compared against the optimal solution for the original, non-shrunk instance. We prove thatin this regime, the problem admits an EPTAS with running timef( ,δ)·nO(1), and an FPTalgorithm with running timef(k,δ)·nO(1), in the setting where a maximum-weight solutionof size at mostkis to be computed. This improves and significantly simplifies a PTAS givenearlier for this problem [1], and provides the first parameterized results for the shrinking model.Furthermore, we explore kernelization in the shrinking model, by giving efficient kernelizationprocedures for several variants of the problem when the input rectangles are squares.