Abstract
We consider the Sparse Hitting Set (SparseHS) problem, where we are given a set system (V,ℱ,ℬ) with two families ℱ,ℬ of subsets of the universe V. The task is to find a hitting set for ℱ that minimizes the maximum number of elements in any of the sets of ℬ. This generalizes several problems that have been studied in the literature. Our focus is on determining the complexity of some of these special cases of SparseHS with respect to the sparseness k, which is the optimum number of hitting set elements in any set of ℬ (i.e., the value of the objective function).
For the Sparse Vertex Cover (SparseVC) problem, the universe is given by the vertex set V of a graph, and ℱ is its edge set. We prove NPhardness for sparseness k ≥ 2 and polynomial time solvability for k = 1. We also provide a polynomialtime 2approximation algorithm for any k. A special case of SparseVC is Fair Vertex Cover (FairVC), where the family ℬ is given by vertex neighbourhoods. For this problem it was open whether it is FPT (or even XP) parameterized by the sparseness k. We answer this question in the negative, by proving NPhardness for constant k. We also provide a polynomialtime (21/k)approximation algorithm for FairVC, which is better than any approximation algorithm possible for SparseVC or the Vertex Cover problem (under the Unique Games Conjecture).
We then switch to a different set of problems derived from SparseHS related to the highway dimension, which is a graph parameter modelling transportation networks. In recent years a growing literature has shown interesting algorithms for graphs of low highway dimension. To exploit the structure of such graphs, most of them compute solutions to the rShortest Path Cover (rSPC) problem, where r > 0, ℱ contains all shortest paths of length between r and 2r, and ℬ contains all balls of radius 2r. It is known that there is an XP algorithm that computes solutions to rSPC of sparseness at most h if the input graph has highway dimension h. However it was not known whether a corresponding FPT algorithm exists as well. We prove that rSPC and also the related rHighway Dimension (rHD) problem, which can be used to formally define the highway dimension of a graph, are both W[1]hard. Furthermore, by the result of Abraham et al. [ICALP 2011] there is a polynomialtime O(log k)approximation algorithm for rHD, but for rSPC such an algorithm is not known. We prove that rSPC admits a polynomialtime O(log n)approximation algorithm.
BibTeX  Entry
@InProceedings{blum_et_al:LIPIcs.IPEC.2022.5,
author = {Blum, Johannes and Disser, Yann and Feldmann, Andreas Emil and Gupta, Siddharth and ZychPawlewicz, Anna},
title = {{On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension}},
booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
pages = {5:15:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772600},
ISSN = {18688969},
year = {2022},
volume = {249},
editor = {Dell, Holger and Nederlof, Jesper},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17361},
URN = {urn:nbn:de:0030drops173612},
doi = {10.4230/LIPIcs.IPEC.2022.5},
annote = {Keywords: sparse hitting set, fair vertex cover, highway dimension}
}
Keywords: 

sparse hitting set, fair vertex cover, highway dimension 
Collection: 

17th International Symposium on Parameterized and Exact Computation (IPEC 2022) 
Issue Date: 

2022 
Date of publication: 

14.12.2022 