# Fixed-Parameter Algorithms for Fair Hitting Set Problems

Tanmay Inamdar  Department of Informatics, University of Bergen, Norway.
Lawqueen Kanesh Indian Institute of Technology, Jodhpur Madhumita
Kundu-1-1footnotemark: -1 Nidhi Purohit-1-1footnotemark: -1 Saket
Saurabh-1-1footnotemark: -1 Institute of Mathematical Sciences, Chennai.
This research is supported by the European Research Council (ERC) under the
European Union’s Horizon 2020 research and innovation programme (grant
agreement No. 819416) Swarnajayanti Fellowship (No. DST/SJF/MSA01/2017-18).

###### Abstract

Selection of a group of representatives satisfying certain fairness
constraints, is a commonly occurring scenario. Motivated by this, we initiate
a systematic algorithmic study of a _fair_ version of Hitting Set. In the
classical Hitting Set problem, the input is a universe $\mathcal{U}$, a family
$\mathcal{F}$ of subsets of $\mathcal{U}$, and a non-negative integer $k$. The
goal is to determine whether there exists a subset $S\subseteq\mathcal{U}$ of
size $k$ that _hits_ (i.e., intersects) every set in $\mathcal{F}$. Inspired
by several recent works, we formulate a fair version of this problem, as
follows. The input additionally contains a family $\mathcal{B}$ of subsets of
$\mathcal{U}$, where each subset in $\mathcal{B}$ can be thought of as the
group of elements of the same _type_. We want to find a set
$S\subseteq\mathcal{U}$ of size $k$ that (i) hits all sets of $\mathcal{F}$,
and (ii) does not contain _too many_ elements of each type. We call this
problem Fair Hitting Set, and chart out its tractability boundary from both
classical as well as multivariate perspective. Our results use a multitude of
techniques from parameterized complexity including classical to advanced
tools, such as, methods of representative sets for matroids, FO model
checking, and a generalization of best known kernels for Hitting Set.

##  1 Introduction

Imagine a scenario of selecting a committee of size $k$ from a group of people
$\mathcal{U}$. We need a committee of people with some given attributes. These
kinds of “attribute hitting” scenarios is modeled by a family $\mathcal{F}$
over $\mathcal{U}$, where for each attribute $\mathscr{A}$ , we have a set
$\mathcal{F}$ containing people in $\mathcal{U}$ who have the attribute
$\mathscr{A}$. As is life, not always every set of people can work
collectively. In particular, the committee cannot operate smoothly if we
select more than the desired number of people from a set
$B\subseteq\mathcal{U}$. These conflicts are modeled by another family,
$\mathcal{B}$ over $\mathcal{U}$, and a function $f:\mathcal{B}\to\mathbb{N}$,
which says that $f(B)$ is the maximum number of people from a set
$B\in\mathcal{B}$ that can serve on the committee. Specifically, we want a
committee that is a hitting set for attributes and has a set of people who are
“conflict free”. This paper aims to undertake a systematic study of a
generalization of Hitting Set, which models such scenarios, and study this
problem in the realm of parameterized complexity.

Indeed, Hitting Set is one of the 21 problems proven to be NP-complete by Karp
[9]. Recall, in this problem, we are given a set system
$(\mathcal{U},\mathcal{F})$, and an integer $k$. Here, $\mathcal{U}$ is a
finite set of elements known as _universe_ and $\mathcal{F}$ is a family of
subsets of $\mathcal{U}$. The objective is to determine whether there exists a
subset $S\subseteq\mathcal{U}$ such that $S$ _hits_ all sets in $\mathcal{F}$,
i.e., for every $F_{i}\in\mathcal{F}$, $S\cap F_{i}\neq\emptyset$. Hitting Set
is closely related to the Set Cover problem. These two problems, along with a
particularly interesting special case thereof, namely that of Vertex Cover,
are some of the most extensively studied problems in the field of
approximation algorithms and parameterized complexity. Hitting Set problem is
of particular interest, because many combinatorial problems can be modeled as
instances of Hitting Set.

Motivated from real-life applications, there has been a growing interest on
the fairness aspect of various problems and algorithms developed. This has led
to the whole new field of algorithmic fairness. Depending on the specific
application, there are numerous ways to define the notion of _fairness_. One
of the earliest definitions of fairness comes from [11], who defined fair
versions of edge deletion problems. This was motivated from the following
scenario. Suppose the graph models a communication network, with each edge
being a link between a pair of nodes. In order to achieve acyclicity in the
network, some links need to be disconnected. However, from the perspective of
each node, it is desirable that fewest possible links incident to it are
disconnected. Thus, we wish to disconnect links in a fair or equitable manner
for the nodes.

Subsequently, this notion was extended by [15, 10] to define fair versions of
vertex deletion problems. In this model, we want to delete a subset of
vertices in order to achieve a certain graph property, such that each vertex
has fewest possible neighbors deleted. As a concrete example, in a fair
version of Vertex Cover in this model, we want to find a vertex cover $S$,
such that each vertex outside $S$ has fewest neighbors in $S$. Recently, [2]
studied a generalization of this, called Sparse Hitting Set. The input to
Sparse Hitting Set consists of $(\mathcal{U},\mathcal{F},\mathcal{B})$, where
$\mathcal{U}$ is the universe, and $\mathcal{F}$ and $\mathcal{B}$ are two
families of subsets of $\mathcal{U}$. The goal is to find a hitting set
$S\subseteq\mathcal{U}$ for $\mathcal{F}$ such that
$k\coloneqq\max_{B_{i}\in\mathcal{B}}|B_{i}\cap S|$ is minimized. Here, $k$ is
called the _sparseness_ of the solution. Note that Sparse Hitting Set
generalizes Fair Vertex Cover as defined above. Along a similar line, [8]
considered _conflict-free_ versions of various problems, including Hitting
Set. In Conflict Free $d$-Hitting Set, we are given an instance
$(\mathcal{U},\mathcal{F},k)$ of Hitting Set, and a conflict graph
$H=(\mathcal{U},E)$, and the goal is to find a hitting set
$S\subseteq\mathcal{U}$ of size at most $k$, such that $S$ induces an
independent set in the conflict graph $H$.

#### Our Problem.

Along the same line of work, we define a fair version of Hitting Set, which
captures all of the aforementioned problems, and much more. Formally, the
problem is defined as follows.

Fair Hitting Set Input. An instance
$\mathcal{I}=(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$,
where $\mathcal{U}=\\{u_{1},u_{2},\ldots,u_{n}\\}$ is the universe;
$\mathcal{B}$ and $\mathcal{F}$ are two families of subsets of $\mathcal{U}$,
where $\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{m}\\}$, and
$\mathcal{B}=\\{B_{1},B_{2},\ldots,B_{\ell}\\}$, and $k$ is a positive
integer. Task. Determine whether there exists $S\subseteq\mathcal{U}$, with
the following properties. • $|S|\leq k$, • $S$ is a _hitting set_ for
$\mathcal{F}$, i.e., for every $F_{i}\in\mathcal{F}$, $S\cap
F_{i}\neq\emptyset$, and • For every $B_{j}\in\mathcal{B}$, $|S\cap B_{j}|\leq
f(B_{j})$. We refer to a set $S\subseteq\mathcal{U}$ satisfying the above
properties as a _fair hitting set_ for $\mathcal{F}$, and use $|\mathcal{I}|$
to denote the size of the instance $\mathcal{I}$.

We note that Fair Hitting Set generalizes Sparse Hitting Set. Given an
instance $(\mathcal{U},\mathcal{F},\mathcal{B})$ of Sparse Hitting Set, we
iteratively solve instances $\mathcal{I}_{i}$ of Fair Hitting Set for
$i=1,2,\ldots$. Here, an instance $\mathcal{I}_{i}$ of Fair Hitting Set is
given by $(\mathcal{U},\mathcal{F},\mathcal{B},f_{i},|\mathcal{U}|)$, where
$f_{i}(B_{j})=i$ for all $B_{j}\in\mathcal{B}$. For the smallest $i$ such that
$\mathcal{I}_{i}$ is a yes-instance of Fair Hitting Set, we stop and conclude
that $i$ is the optimal sparseness of the given instance of Sparse Hitting
Set. We note that Fair Hitting Set also generalizes the setting considered by
[8].

###  1.1 Our Results, Techniques, and Relation to Hitting Set

First, we observe that Fair Hitting Set is a generalization of Hitting Set, by
setting $\mathcal{B}=\emptyset$. Thus, Fair Hitting Set inherits all lower
bound results from Hitting Set, namely, in general the problem is NP-hard as
well as W$[2]$-hard parameterized by $k$, the solution size [3]. However, note
that in the hard instances of Hitting Set, the sets in $\mathcal{F}$ can
intersect arbitrarily. Indeed, consider an extreme case, when the sets in
$\mathcal{F}$ are pairwise disjoint. In this setting Hitting Set is trivial to
solve – an optimal solution must contain exactly one element from each set of
$\mathcal{F}$. In contrast, we show that Fair Hitting Set remains NP-hard, as
well as W$[1]$-hard w.r.t. $k$—and thus unlikely to be FPT—even in this simple
setting. In particular, we show the following lower bound results that are
proved in Section 8.

######  Theorem 1.

Fair Hitting Set remains NP-hard when (1) the sets in $\mathcal{F}$ are
pairwise disjoint, (2) each element appears in at most two distinct $B_{i}$’s
in $\mathcal{B}$, and (3) each $B_{i}\in\mathcal{B}$ has size exactly $2$.
Furthermore, assuming ETH, it is not possible to solve Fair Hitting Set in
time $2^{o(t)}$, where
$t=\max\\{|\mathcal{U}|,|\mathcal{F}|,|\mathcal{B}|\\}$..

Fair Hitting Set is W$[1]$-hard when parameterized by $k$, even when the sets
in $\mathcal{F}$ are pairwise disjoint, and each $B_{i}\in\mathcal{B}$ has
size exactly $2$.

The first result is obtained via a reduction from a problem of finding a
“rainbow matching” on a path, and for the second result we give a parameter
preserving reduction from $k$-Multicolored Independent Set. Given these lower
bound results (Theorem 1), we study Fair Hitting Set under specific
assumptions on the instance
$\mathcal{I}=(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$. A natural question
is: under which assumptions? To answer this we look at the known fixed-
parameter tractability results for Hitting Set.

Hitting Set in Parameterized Complexity. Hitting Set is known to be
W$[2]$-complete parameterized by the solution size in general. In other words,
under widely believed complexity theoretic assumptions, it does not admit an
FPT algorithm parameterized by the solution size. This motivates the study of
Hitting Set in special cases. One particularly interesting case is Vertex
Cover when the size of each set in $\mathcal{F}$ is exactly two. Vertex Cover
is the most extensively studied problem in the parameterized complexity with a
number of results in the FPT algorithms and kernelization in general graphs as
well as special classes of graphs. Many of the techniques and results
developed for Vertex Cover also extend $d$-Hitting Set, where each set in
$\mathcal{F}$ has size at most $d$, for some constant $d$. More generally,
Hitting Set is known to be FPT and admits a polynomial kernel in the case when
the incidence graph $G_{\mathcal{U},\mathcal{F}}$, which is the bipartite
graph on the vertex set $\mathcal{U}\uplus\mathcal{F}$ with edges denoting the
set-containment, is $K_{i,j}$-free. That is, no $i$ sets in $\mathcal{F}$
contain $j$ elements in common, where $i$ and $j$ are assumed to be constants.
This setting generalizes all the above settings as well as when the
$G_{\mathcal{U},\mathcal{F}}$ is $d$-degenerate (since such graphs are
$K_{d+1,d+1}$-free).

Our Algorithmic Results. Notably, we are able to extend almost all of the
fixed-parameter tractability results for Hitting Set mentioned in the previous
paragraph, under suitable assumptions on the set system
$(\mathcal{U},\mathcal{B})$. We give a summary of our results in Figure 1.

More specifically, we obtain our results in the following steps. Consider a
special case Fair Hitting Set, when the sets in $\mathcal{F}$ are pairwise
disjoint, and each element appears in at most $q$ sets in $\mathcal{B}$. Note
that the first part of Theorem 1 implies that the problem is NP-hard even when
$q=2$. On the other hand, when $q=1$, i.e., when both $\mathcal{F}$ and
$\mathcal{B}$ are families of pairwise disjoint sets, then we observe Fair
Hitting Set can be solved in polynomial time. Thus, $q=1$ to $2$ is a sharp
transition between the tractability of the problem. Although the problem is
NP-hard even for constant values of $q$, the following results are interesting
in this setting. In particular, we show that the problem is FPT, and admits a
polynomial kernel parameterized by $k$, if $q$ is a constant.

######  Theorem 2.

Let $(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$ be an
instance of Fair Hitting Set. Then, Fair Hitting Set can be solved in time
$2^{{\mathcal{O}}(qk)}n^{{\mathcal{O}}(1)}$ time, when every element in
$\mathcal{U}$ appears in at most $q$ sets in $\mathcal{B}$ and any pair of
sets in $\mathcal{F}$ are pairwise disjoint. Further, Fair Hitting Set admits
a kernel of size ${\mathcal{O}}(kq^{2}{kq\choose q}\log k)$.

Next we generalize Theorem 2 to a scenario where every element in
$\mathcal{U}$ appears in at most $q$ sets in $\mathcal{B}$ and at most $d$
sets in $\mathcal{F}$.

######  Theorem 3.

Let $(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$ be an
instance of Fair Hitting Set. Then, Fair Hitting Set can be solved in time
$k^{{\mathcal{O}}(dk)}2^{{\mathcal{O}}(qk)}n^{{\mathcal{O}}(1)}$ time, when
every element in $\mathcal{U}$ appears in at most $q$ sets in $\mathcal{B}$
and at most $d$ sets in $\mathcal{F}$.

These results, Theorems 2 and 3, are obtained by the key observation that the
problem can be modeled as finding a hitting set for $\mathcal{F}$ that is also
an independent set in a suitably defined partition matroid that encodes the
constraints imposed by $(\mathcal{U},\mathcal{B},f)$. This enables us to use
the representative sets toolkit developed for matroids. This result is
discussed in Section 3.

Next we consider a generalization of the above setting, where (1) each element
appears in at most $q$ sets in $\mathcal{B}$, and (2) the
$G_{\mathcal{U},\mathcal{F}}$ is $K_{d,d}$-free. In this case, we combine the
techniques developed in Hitting Set literature in the $K_{d,d}$-free setting,
as well as, the representative sets based techniques developed in Section 3,
to obtain the following result.

######  Theorem 4.

Given an instance $\mathcal{I}=(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ of
Fair Hitting Set, such that $G_{\mathcal{U},\mathcal{F}}$ is $K_{d,d}$-free,
and the frequency of each element in $\mathcal{B}$ is bounded by $q$, one can
find an equivalent instance
$\mathcal{I}^{\prime}=(\mathcal{U}^{\prime},\mathcal{F}^{\prime},\mathcal{B}^{\prime},f^{\prime},k^{\prime})$
of Fair Hitting Set in polynomial time, such that
$|\mathcal{U}^{\prime}|=\mathcal{O}(k^{d^{2}+q}d^{d}q^{q})$,
$|\mathcal{F}^{\prime}|\leq dk^{d}$, and
$|\mathcal{B}^{\prime}|=\mathcal{O}(k^{d^{2}+q}\cdot d^{d}q^{q+1})$, where $d$
and $q$ are assumed to be constants.

Finally, we reach our most general case, where suppose (1) the
$(\mathcal{U},\mathcal{B})$ incidence graph is “nowhere dense” (defined
formally in Section 2.2; this class includes planar, excluded minor, bounded
degree, and bounded expansion graphs), and (2) the $(\mathcal{U},\mathcal{F})$
incidence graph is $K_{d,d}$-free. In this case, we obtain an FPT algorithm,
parameterized by $k$ and $d$. This result is in two steps. First, we proceed
as prior to the case when each element appears in $f(k,d)$ sets of
$\mathcal{F}$ (cf. Theorem 4). Next, since $(\mathcal{U},\mathcal{B})$
incidence graph is nowhere dense, we reduce the problem of finding a Fair
Hitting Set to FO model checking procedure on nowhere dense graphs, which is
known to be FPT in the size of the formula. In particular, we show that the
problem can be encoded by a variant of Induced Subgraph Isomorphism on nowhere
dense graphs, where the size of the host graph we are searching for can be
bounded by a function of $k$, $d$ and the graph class.

######  Theorem 5.

Let $\mathcal{G}$ be a nowhere dense graph class. Let
$\mathcal{I}=(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ be an instance of Fair
Hitting Set such that the incidence graph $G\coloneqq
G_{\mathcal{U},\mathcal{B}}\in\mathcal{G}$, and $G_{\mathcal{U},\mathcal{F}}$
is $K_{d,d}$-free for some $d\geq 1$. Then, one can solve Fair Hitting Set on
$\mathcal{I}$ in time $h(k,d)\cdot|\mathcal{I}|^{\mathcal{O}(1)}$, for some
function $h(\cdot,\cdot)$.

No. |  $\mathcal{G}_{\mathcal{U},\mathcal{B}}$ |  $\mathcal{G}_{\mathcal{U},\mathcal{F}}$ |  Results
---|---|---|---
$1$ |  $q=1$ |  $d=1$ |  Polynomial time
|  ($B_{i}^{\prime}s$ are disjoint) |  ($F_{i}^{\prime}s$ are disjoint) |
$2$ |  $q=2$ |  $d=1$ |  NP-Hard
|  |  |  No sub-exp algo(ETH)
$3$ |  $q$ |  $d=1$ |  $2^{\mathcal{O}(qk)}\cdot|\mathcal{I}|^{\mathcal{O}(1)}$(Theorem 2)
|  |  |  $\mathcal{O}(kq^{2}\binom{kq}{q}\log k)$(kernel)
|  |  |  (Theorem 7)
$4$ |  $q$ |  $d$ |  $k^{\mathcal{O}(dk)}2^{qk}|\mathcal{I}|^{\mathcal{O}(1)}$
|  |  |  (Theorem 3)
$5$ |  $q$ |  $K_{d,d}$-free |  $k^{\mathcal{O}(d^{2}+q)}d^{d}q^{q+1}$(kernel)
|  |  |  (Theorem 4)
$6$ |  apex-minor free |  $K_{d,d}$-free |  FPT$/(k+d)$ (Theorem 12)
$7$ |  nowhere dense |  $K_{d,d}$-free |  FPT$/(k+d)$ (Theorem 5)
$8$ |  $K_{2,2}$-free |  $d=1$ |  $W[1]$-Hard$/k$ (Theorem 14)
Figure 1: An overview of different results obtained in this paper. In the
second (resp. third) column, we state the assumption on the set system
$(\mathcal{U},\mathcal{B})$ (resp. $(\mathcal{U},\mathcal{F})$). In rows 1-5
(resp. rows 1-4) $q$ (resp. $d$) denotes the maximum frequency of an element
in $\mathcal{B}$ (in $\mathcal{F}$). In the last column, we mention our
results in the respective settings, and give corresponding references.  Figure
2: A Hasse diagram of the settings considered in Figure 1, where the number in
each node corresponds to the row in the table. An arrow from node $i$ to node
$j$ indicates that the setting in row $i$ generalizes the setting in row $j$.
Nodes colored in green, orange (resp. red) color indicate that the setting is
solvable in polynomial, FPT time (resp. is $W[1]$-hard).

##  2 Preliminaries

For an integer $\ell\geq 1$, we use the notation
$[\ell]\coloneqq\\{1,2,\ldots,\ell\\}$. Let
$\mathcal{R}=(\mathcal{U},\mathcal{S})$ be a _set system_ , where
$\mathcal{U}$ is a finite set of elements (also called the _ground set_ or the
_universe_), and $\mathcal{S}$ is a family of subsets of $\mathcal{U}$. For an
element $u\in\mathcal{U}$, and any $\mathcal{S}^{\prime}\subseteq\mathcal{S}$,
we use the notation
$\mathcal{S}^{\prime}(u)\coloneqq\\{S\in\mathcal{S}^{\prime}:u\in S\\}$, i.e.,
$\mathcal{S}^{\prime}(u)$ is the sub-family of sets from
$\mathcal{S}^{\prime}$ that contain $u$. For a subset $R\subseteq\mathcal{U}$,
we denote $\mathcal{S}-R\coloneqq\\{S\setminus R:S\in\mathcal{S}\\}$. We use
$G_{\mathcal{U},\mathcal{S}}$ to denote the incidence graph corresponding to
the set system $(\mathcal{U},\mathcal{S})$, i.e.,
$G_{\mathcal{U},\mathcal{S}}$ is a bipartite graph with bipartition
$\mathcal{U}\uplus\mathcal{S}$, such that there is an edge between an element
$e\in\mathcal{U}$ and a set $S\in\mathcal{S}$ iff $e\in S$.

In this paper, we work with finite, simple, undirected graphs. We use the
standard graph theoretic notation and terminology, as defined in [4]. In the
following subsections, we give additional preliminaries.

###  2.1 Preliminaries on Tree Decompositions

Tree Decompositions and Treewidth A _tree decomposition_ of a graph $G$ is a
pair $\mathcal{T}=(T,\beta)$, where $T$ is a tree, and $\beta:V(T)\to
2^{V(G)}$ satisfying the following properties.

  * •

$\bigcup_{t\in V(T)}\beta(t)=V(G)$.

  * •

For every edge $\\{u,v\\}\in V(G)$, there exists a $t\in V(T)$, such that
$\\{u,v\\}\subseteq\beta(t)$.

  * •

For every $u\in V(G)$, the set $T_{u}=\\{t\in V(T):u\in\beta(t)\\}$ induces a
connected subtree of $T$.

We refer to vertices of $T$ as _nodes_ in order to distinguish them vertices
of $G$, and the set $\beta(t)$ is called the _bag_ of $t$. The _width_ of a
tree decomposition $(T,\beta)$ is defined to be $\max_{t\in
V(T)}|\beta(t)|-1$. The _treewidth_ of a graph $G$ is the minimum possible
width of a tree decomposition of $G$, which we denote by $\textup{{tw}}(G)$.

Nice Tree Decompositions. It is often convenient to deal with a more
structured tree decomposition, called _nice tree decomposition_. We think of
tree decomposition $(T,\beta)$ as a rooted tree, with a distinguished node
$r\in V(T)$ called the _root_. Furthermore, the tree decomposition satisfies
the following properties.

  * •

$\beta(r)=\emptyset$.

  * •

Every non-leaf node of $T$ is of one of following three types:

    * –

Introduce node. A node $t$ with exactly one child $t^{\prime}$ such that
$\beta(t)=\beta(t^{\prime})\cup\\{v\\}$ for some $v\not\in\beta(t^{\prime})$.
We say that $v$ is _introduced at $t$_.

    * –

Forget node. A node $t$ with exactly one child $t^{\prime}$ such that
$\beta(t)=\beta(t^{\prime})\setminus\\{w\\}$ for some $w\in\beta(t^{\prime})$.
We say that $w$ _is forgotten_ at $t$.

    * –

Join node. A node $t$ with exactly two children $t_{1},t_{2}$ such that
$\beta(t)=\beta(t_{1})=\beta(t_{2})$.

It is known that any tree decomposition of $G$ can be converted into a nice
tree decomposition of $G$ of the same width in polynomial time.

For a node $t\in V(T)$, all nodes $t^{\prime}$ in the subtree rooted at $t$
(including $t$ itself) are called _descendants_ of $t$. We note that in a nice
tree decomposition $(T,\beta)$, if $v\in V(G)$ is forgotten at $t\in V(T)$,
then it must be introduced at a descendant $t^{\prime}$ of $t$, such that
$t^{\prime}\neq t$.

###  2.2 Preliminaries for Nowhere Dense Graphs

The following definitions pertaining to the class of nowhere dense graphs are
taken verbatim from [13].

######  Definition 1 (Shallow minor).

A graph $M$ is an _$r$ -shallow minor_ of $G$, where $r$ is an integer, if
there exists a set of disjoint subsets $V_{1},\ldots,V_{|M|}$ of $V(G)$ such
that

  1. 1.

Each graph $G[V_{i}]$ is connected and has radius at most $r$, and

  2. 2.

There is a bijection $\psi\colon V(M)\to\\{V_{1},\ldots,V_{|M|}\\}$ such that
for every edge $uv\in E(M)$ there is an edge in $G$ with one endpoint in
$\psi(u)$ and second in $\psi(v)$.

The set of all $r$-shallow minors of a graph $G$ is denoted by
$G\mathop{\triangledown}r$. Similarly, the set of all $r$-shallow minors of
all the members of a graph class $\cal G$ is denoted by ${\cal
G}\mathop{\triangledown}r=\bigcup_{G\in{\cal G}}(G\mathop{\triangledown}r)$.

We first introduce the definition of a nowhere dense graph class; let
$\omega(G)$ denote the size of the largest clique in $G$ and $\omega({\cal
G})=\sup_{G\in\cal G}\omega(G)$.

######  Definition 2 (Nowhere dense).

A graph class $\cal G$ is _nowhere dense_ if there exists a function
$f_{\omega}\colon\mathbb{N}\to\mathbb{N}$ such that for all $r$ we have that
$\omega({\cal G}\mathop{\triangledown}r)\leq f_{\omega}(r)$.

###  2.3 Background on First-Order Logic

In this section, we discuss preliminaries and background on first-order logic
(FO). Almost all of this exposition is taken verbatim from [7]. For additional
background, we point the reader to [7] and references therein.

A _(relational) vocabulary_ is a finite set of relation symbols, each with a
prescribed arity. Let $\sigma$ be a vocabulary. Then, a $\sigma$-structure $A$
consists of (i) a finite set $V(A)$, called the _universe_ or _vertex set_ of
$A$, and (ii) for each $k$-ary relation symbol $R\in\sigma$, a $k$-ary
relation $R(A)\subseteq V(A)^{k}$.

Let $A$ be a $\sigma$-structure. For a subset $X\subseteq V(A)$, the _induced
substructure_ of $A$ with universe $X$ is the $\sigma$-structure $A[X]$ with
$V(A[X])=X$, and $R(A[X])=R(A)\cap X^{k}$ for every $k$-ary $R\in\sigma$. For
$\sigma^{\prime}\subseteq\sigma$, the $\sigma^{\prime}$-restriction of $A$ is
the $\sigma^{\prime}$-structure $A^{\prime}$ with $V(A^{\prime})=V(A)$ and
$R(A^{\prime})=R(A)$ for all $R\in\sigma^{\prime}$.

For example, a graph $G$ can be thought of as $\\{E\\}$-structure. This notion
is generalized as follows. A _colored graph vocabulary_ consists of the binary
relation symbol $E$, and possibly finitely many unary relation symbols. A
$\sigma$-colored graph is a $\sigma$-structure, whose $\\{E\\}$-restriction is
a simple undirected graph. We call the $\\{E\\}$-restriction of a
$\sigma$-colored graph the _underlying graph_ of $G$.

_First-order formulas_ of vocabulary $\sigma$ are formed from atomic formulas
$x=y$, and $R(x_{1},x_{2},\ldots,x_{k})$, where $R\in\sigma$ is a $k$-ary
relation symbol, and $x,y,x_{1},\ldots,x_{k}$ are variables (assuming an
infinite supply of variables). Atomic formulas can be combined by Boolean
connectives $\neg$ (negation), $\land$ (conjunction), $\lor$ (disjunction),
and existential and universal quantification $\exists x,\forall x$,
respectively. The set of all first-order formulas of vocabulary $\sigma$ is
denoted by $\textup{{FO}}[\sigma]$, and the set of all first order formulas by
FO. The free variables of a formula are the variables that are not in the
scope of a quantifier, and we write $\varphi(x_{1},\ldots,x_{k})$ to indicate
that the free variables of the formula $\varphi$ are among
$x_{1},\ldots,x_{k}$. A sentence is a formula without free variables.

To define semantics, a satisfaction relation $\models$ is defined inductively
as follows. For a $\sigma$-structure $A$, a formula
$\varphi(x_{1},\ldots,x_{k})$, and elements $a_{1},\ldots,a_{k}\in V(A)$,
$A\models\varphi(a_{1},\ldots,a_{k})$ means that $A$ satisfies $\varphi$ if
the free variables $x_{1},\ldots,x_{k}$ are interpreted by
$a_{1},\ldots,a_{k}$, respectively. If
$\varphi(x_{1},\ldots,x_{k})=R(x_{1},\ldots,x_{k})$ is an atomic formula, then
$A\models\varphi(a_{1},\ldots,a_{k})$ iff $(a_{1},\ldots,a_{k})\in R(A)$. The
meanings of equality symbol, the Boolean connectives, and the quantifiers are
the usual ones.

Whenever a $\sigma$-structure occurs as the input of an algorithm, we assume
that it is finite, and is encoded in a suitable way. Similarly, we assume that
the formulas $\varphi$ appearing as input are encoded suitably. We denote the
length of the encoding of $\varphi$ by $|\varphi|$.

Finally, we will use the following theorem from [7].

######  Theorem 6.

For every nowhere dense class $\cal G$, every $\epsilon>0$, every colored-
graph vocabulary $\sigma$, and every first-order formula
$\varphi(x)\in\textup{{FO}}[\sigma]$, there is an algorithm that, given a
$\sigma$-colored graph $G$ whose underlying graph $G\in\cal G$, computes the
set of all $v\in V(G)$ such that $G\models\varphi(v)$ in time
$\mathcal{O}(n^{1+\epsilon})$.

##  3 FPT Algorithm and Kernel Based on Representative Sets

In this section we design an algorithm and a kernel for a special case of Fair
Hitting Set, using methods based on representative sets [6, 14]. Let
$(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$ be an
instance of Fair Hitting Set. The first special case we consider is the
following: every element in $\mathcal{U}$ appears in at most $q$ sets in
$\mathcal{B}$ and any pair of sets in $\mathcal{F}$ are pairwise disjoint.

Before this, however, we consider the special case of $q=1$, i.e., when any
pair of sets in $\mathcal{B}$, as well as that in $\mathcal{F}$ are disjoint.
In this case, we can solve the problem in polynomial time, by reducing it to
the problem of finding maximum flow in an auxiliary directed graph, defined as
follows. The vertices of the graph are
$\mathcal{B}\uplus\mathcal{U}\uplus\mathcal{F}\uplus\\{s,t\\}$. First, we add
arcs (i.e., directed edges) from source $s$ to each $B_{j}\in\mathcal{B}$,
with capacity $f(B_{j})$. Next, for every $u\in B_{j}$, we add an arc
$(B_{j},u)$ of capacity $1$. Similarly, for each $u\in F_{i}$, we add an arc
$(u,F_{i})$, of capacity $1$. Finally, we add arcs $(F_{i},t)$ of capacity
$\infty$. It is straightforward to show that there exists a flow of value $k$
in the graph iff there exists a fair hitting set of size $k$. We omit the
details.

Note that $q\geq 2$, but the sets in $\mathcal{F}$ are pairwise disjoint, the
problem is NP-hard. In this case, To design both our algorithm and the kernel
we first embed the fairness constraints imposed by $\mathcal{B}$ in a
combinatorial object called a _partition matroid_. A partition matroid is a
set system $\mathcal{M}=(E,\mathcal{I})$, defined as follows. The ground set
$E$ is partitioned into $\ell$ subsets $E_{1}\uplus E_{2}\uplus\ldots\uplus
E_{\ell}$, such that a set $S\subseteq E$ belongs to the family $\mathcal{I}$
iff for each $1\leq j\leq\ell$, it holds that $|E_{j}\cap S|\leq k_{j}$, where
$k_{1},k_{2},\ldots,k_{\ell}$ are non-negative integers.

It might be observed that the definition of a partition matroid closely
resembles the fairness constraints, i.e., for each $B_{j}$, the hitting set
$H$ must satisfy $|H\cap B_{i}|\leq f(B_{i})$. However, this idea does not
quite work, since the sets $B_{j}\in\mathcal{B}$ are not disjoint – indeed,
otherwise we could solve the problem in polynomial time, as discussed earlier.
Nevertheless, we can salvage the situation by making $q$ distinct copies of
every element $u\in\mathcal{U}$, and replacing each of the occurrences of $u$
in $q$ distinct $B_{j}$’s with a unique copy. The resulting set system is a
partition matroid that exactly captures the fairness constraints.
Correspondingly, in each set of $\mathcal{F}$, we replace an original element
with all of its $q$ copies. Recall that we want to find a hitting set for
$\mathcal{F}$; however, in the new formulation, we must now ensure that if we
pick _at least_ one copy of element in the solution, we pick _all_ of its
copies in the solution.

Thus, our solution is an independent set of $\mathcal{M}$ that (1) is a
hitting set for $\mathcal{F}$, and (2) picks either $0$ or $q$ copies of every
element. To find such a solution in time FPT in $k$ and $q$ (resp. to reduce
the size of the instance), we use a sophisticated tool developed in
parameterized complexity, called _representative sets_. Later, we generalize
this idea to the case where very element in $\mathcal{U}$ appears in at most
$q$ sets in $\mathcal{B}$ _and_ at most $d$ sets in $\mathcal{F}$. In the next
section, we formally define the partition matroid, and in the subsequent
sections, we apply the toolkit of representative sets to design our FPT
algorithm and the kernel.

###  3.1 Partition Matroid and Our Solution

In a partition matroid we have a universe $\widetilde{U}$, partitioned into
$\widetilde{U}_{1},\cdots,\widetilde{U}_{\ell}$, together with positive
integers $k_{1},\cdots,k_{\ell}$, and a family of independent sets $\cal I$,
such that $X\subseteq\widetilde{U}$ is in $\mathcal{I}$ if and only if
$|X\cap\widetilde{U}_{i}|\leq k_{i}$, $i\in[\ell]$.

Let $(\mathcal{U},\mathcal{B})$ be the given set system such that each element
$u\in\mathcal{U}$ appears in at most $q$ sets of $\mathcal{B}$. For an element
$u\in\mathcal{U}$, let $q(u)\leq q$ denote the number of sets in
$\mathcal{B}$, that $u$ appears in. Further, for an element $u\in\mathcal{U}$,
let ${\sf copies}(u)=\\{u^{1},u^{2},\ldots,u^{q(u)}\\}$. We define

$\widetilde{U}=\bigcup_{u\in\mathcal{U}}{\sf copies}(u).$

Next, we need to define a partition of $\widetilde{U}$. Towards this we use
the information about the sets in $\cal B$. We know that each element $u\in B$
appears in $q(u)$ sets and we have made $q(u)$ copies of $u$, thus we use
distinct and unique copy of $u$ in each sets in $\mathcal{B}$ in which $u$
appears. This results in
$\widetilde{\mathcal{B}}=\\{\widetilde{B}_{i}:B_{i}\in\mathcal{B}\\}$, where
$\widetilde{B}_{i}$ is the set corresponding to an original set $B_{i}$, after
replacing elements with their copies. Observe that for every pair of indices
$i\neq j$ we have that $\widetilde{B}_{i}\cap\widetilde{B}_{j}=\emptyset$ and
$\cup_{i}\widetilde{B}_{i}=\widetilde{U}$. This immediately gives a partition
of $\widetilde{U}$. Finally, we define $k_{i}=f(B_{i})$. This completes the
description of the partition matroid we will be using. We will call this
matroid as ${\cal M}=(\widetilde{U},\mathcal{I})$

Given a subset $X\subseteq\widetilde{U}$, we define a set associated with $X$,
called ${\sf projection}(X)$ as follows. The set ${\sf projection}(X)\subseteq
U$, contains an element $u\in U$ if and only if ${\sf copies}(u)\cap
X\neq\emptyset$. Similarly, we define a notion of embedding. For a set
$A\subseteq\mathcal{U}$, let ${\sf embed}(A)=\cup_{u\in A}{\sf copies}(u)$.
This brings us to the following lemma which relates our problem and finding an
independent set in the matroid.

######  Lemma 1.

An input $(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$
is a yes-instance if and only if there exists an independent set
$X\in\mathcal{I}$ of the matroid ${\cal M}=(\widetilde{U},\mathcal{I})$ such
that (1) $|{\sf projection}(X)|\leq k$, (2) $X={\sf embed}({\sf
projection}(X))$, and (3) ${\sf projection}(X)$ is a hitting set for
$\mathcal{F}$.

###### Proof.

In the forward direction, let $S\subseteq\mathcal{U}$ be a solution to the
original problem. Suppose $S=\\{s_{1},s_{2},\ldots,s_{k}\\}$. Consider $X={\sf
embed}(S)$. Observe that by definition, $S={\sf projection}(X)$. So $|{\sf
projection}(X)|=k$ and ${\sf projection}(X)$ is a hitting set for
$\mathcal{F}$. We claim that $X$ is an independent set because if not, there
exists a part $\widetilde{B}_{i}$ which satisfies that
$|X\cap\widetilde{B}_{i}|>k_{i}=f(B_{i})$. As $S={\sf projection}(X)$ and for
every $u\in\widetilde{B}_{i}$, $B_{i}$ contains a $v$ such that $u\in{\sf
copies}(v)$, this results in $|S\cap B_{i}|>k_{i}$ implying $|S\cap
B_{i}|>f(B_{i})$ which contradicts that $S$ is a valid solution to the
original problem.

In the reverse direction, let $X\in\mathcal{I}$ be an independent set
satisfying both the conditions. Let $S={\sf projection}(X)$. We claim that,
$S$ is a solution for the original instance because if not, there exist a part
$B_{i}$ which satisfies that $|S\cap B_{i}|>f(B_{i})=k_{i}$. As $X={\sf
embed}(S)$ and for every $u\in B_{i}$, an unique copy from ${\sf copies}(u)$
is contained in $\widetilde{B}_{i}$, which results in
$|X\cap\widetilde{B}_{i}|>k_{i}$ which contradicts that $X$ is an independent
set. ∎

###  3.2 Computation of the Desired Independent Set

In this section we give an algorithm to compute an independent set
$X\in\mathcal{I}$ of the matroid ${\cal M}=(\widetilde{U},\mathcal{I})$ such
that $|{\sf projection}(X)|\leq k$ and ${\sf projection}(X)$ is a hitting set
for $\mathcal{F}$ (as given by Lemma 1). We will design a dynamic programming
algorithm based on representative families to compute the desired independent
set. Towards this, we first give the required definitions. We start with the
definition of an $\ell$-representative family.

######  Definition 3 ($\ell$-Representative Family).

Given a matroid $M=(E,{\cal I})$ and a family $\cal S$ of subsets of $E$, we
say that a subfamily $\widehat{\cal{S}}\subseteq\cal S$ is
$\ell$-representative for $\cal S$ if the following holds: for every set
$Y\subseteq E$ of size at most $\ell$, if there is a set $X\in\cal S$ disjoint
from $Y$ with $X\cup Y\in\cal{I}$, then there is a set
$\widehat{X}\in\widehat{\cal S}$ disjoint from $Y$ with $\widehat{X}\cup
Y\in\cal{I}$. If $\hat{\cal S}\subseteq{\cal S}$ is $\ell$-representative for
${\cal S}$ we write $\widehat{{\cal S}}\subseteq_{rep}^{\ell}{\cal S}$.

In other words if some independent set in $\cal S$ can be extended to a larger
independent set by adding $\ell$ new elements, then there is a set in
$\widehat{\cal S}$ that can be extended by the same $\ell$ elements. We say
that a family $\mathcal{S}=\\{S_{1},\ldots,S_{t}\\}$ of sets is a $p$-family
if each set in $\cal S$ is of size $p$.

######  Proposition 1.

[6, 12, Theorem $3.8$, Theorem $1.3$] Let $M=(E,{\cal I})$ be a partition
matroid, $\mathcal{S}=\\{S_{1},\ldots,S_{t}\\}$ be a $p$-family of independent
sets. Then there exists $\widehat{{\cal S}}\subseteq_{rep}^{\ell}{\cal S}$ of
size $\binom{{p+\ell}}{{p}}$. Furthermore, given a representation $A_{M}$ of
$M$ over a field $\mathbb{F}$, there is a deterministic algorithm computing
$\widehat{{\cal S}}\subseteq_{rep}^{\ell}{\cal S}$ of size at most
$\binom{{p+\ell}}{{p}}$ in ${\mathcal{O}}\left({p+\ell\choose
p}tp^{\omega}+t{p+\ell\choose
p}^{\omega-1}+||A_{M}||^{{\mathcal{O}}(1)}\right)$ operations over
$\mathbb{F}$, where $||A_{M}||$ denotes the length of $A_{M}$ in the input.

For the purpose of this article, it is enough to know that partition matroids
are “representable” [14, Proposition $3.5$] and a “truncation” of partition
matroids are computable in deterministic polynomial time [12, Theorem $1.3$].
This results in Proposition 1, which we will use for our algorithm without
giving further definitions of representation and truncation [6, 12, 14].

Let $\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{m}\\}$ be the subsets of
$\mathcal{U}$, $k$ be a positive integer. Since, the sets in $\mathcal{F}$ are
pairwise disjoint, the number of sets in $\mathcal{F}$ is upper bounded by
$k$. We call a set $S\subseteq U$, a potential solution, if for all
$j\in[\ell]$, $|S\cap B_{j}|\leq f(B_{j})$. Let

$\displaystyle{\mathcal{S}}_{i}$ $\displaystyle\coloneqq\\{S:S\text{ is a
potential solution },|S|=i\text{ and for all }j\in[i]|S\cap F_{j}|=1\\}.$

Given ${\mathcal{S}}_{i}$, we define ${\mathcal{S}}_{i}^{{\sf emb}}$ as
$\\{{\sf embed}(S)~{}|~{}S\in{\mathcal{S}}_{i}\\}$. Observe that
${\mathcal{S}}_{i}^{{\sf emb}}\subseteq\mathcal{I}$ and each set has size at
most $qi$. Notice that, each set in $\mathcal{S}$ has size exactly $i$, but
the same can not be said about the sets in ${\mathcal{S}}_{i}^{{\sf emb}}$.
However, since each element occurs in at most $q$ sets of $\mathcal{B}$, we
have that each set in ${\mathcal{S}}_{i}^{{\sf emb}}$ has size at most $qi$.

Our algorithm checks whether ${\mathcal{S}}_{k}$ is non-empty or not. Towards
that first observe that ${\mathcal{S}}_{k}$ is non-empty if and only if
${\mathcal{S}}_{k}^{{\sf emb}}$ is non-empty. So the testing of non-emptiness
of ${\mathcal{S}}_{k}$ boils down to checking whether ${\mathcal{S}}_{k}^{{\sf
emb}}$ is non-empty or not. We test whether ${\mathcal{S}}_{k}^{{\sf emb}}$ is
non-empty by computing $\widehat{\mathcal{S}}_{k}^{{\sf
emb}}\subseteq_{rep}^{0}{\mathcal{S}}_{k}^{{\sf emb}}$ and checking whether
${\widehat{\mathcal{S}}}_{k}^{{\sf emb}}$ is non-empty. To argue the
correctness of the algorithm, first we have the following observation.

######  Observation 1.

${\mathcal{S}}_{k}^{{\sf emb}}\neq\emptyset$ iff
$\widehat{\mathcal{S}}_{k}^{{\sf emb}}\neq\emptyset$.

###### Proof.

Since $\widehat{\mathcal{S}}_{k}^{{\sf emb}}\subseteq{\mathcal{S}}_{k}^{{\sf
emb}}$, the reverse direction is immediate. Now we argue the forward
direction. Suppose ${\mathcal{S}}_{k}^{{\sf emb}}$, then it contains some set
$A$. Note that $A$ trivially satisfies $A\cap\emptyset=\emptyset$. Therefore,
since $\widehat{\mathcal{S}}_{k}^{{\sf
emb}}\subseteq_{rep}^{0}{\mathcal{S}}_{k}^{{\sf emb}}$, there must exist a set
$\hat{A}\in\widehat{\mathcal{S}}_{k}^{{\sf emb}}$ such that
$\hat{A}\cap\emptyset=\emptyset$, i.e., $\widehat{\mathcal{S}}_{k}^{{\sf
emb}}\neq\emptyset$. ∎

Thus, having computed the representative family
$\widehat{\mathcal{S}}_{k}^{{\sf emb}}$ all we need to do is to check whether
it is non-empty. All that remains is an algorithm that computes the
representative family $\widehat{\mathcal{S}}_{k}^{{\sf emb}}$.

Let ${\cal Z}$ be a family of sets and $\ell$ be an integer, then ${\cal
Z}[\ell]$ is a subset of $\cal Z$ that contains all the sets of $\cal Z$ of
size exactly $\ell$. We describe a dynamic programming based algorithm. Let
${\cal D}$ be an array indexed from integers in $\\{0,1,\ldots,k\\}$. The
entry ${\cal D}[i]$ stores the following for all $j\in\\{i,\ldots,qi\\}$,
$\widehat{\mathcal{S}}_{i}^{{\sf
emb}}[j]\subseteq_{rep}^{qk-j}{\mathcal{S}}_{i}^{{\sf emb}}[j]$.

We fill the entries in the matrix $\cal D$ in the increasing order of indexes.
For $i=0$, ${\cal D}[0]=\emptyset$. Suppose, we have filled all the entries
until the index $i$. Then consider the set

$\displaystyle{\cal N}^{i+1}$ $\displaystyle=\\{X^{\prime}=X\cup{\sf
embed}(\\{u\\}):X\in{\cal D}[i],~{}u\in F_{i+1},{\sf
projection}(X^{\prime})\text{ is a potential solution}\\}$

We partition sets in ${\cal N}^{i+1}$ based on sizes. Let ${\cal N}^{i+1}[j]$
denote all the sets in ${\cal N}^{i+1}$ of size $j$.

######  Claim 1.

For all $j\in\\{i+1,\ldots,q(i+1)\\}$, ${\cal
N}^{i+1}[j]\subseteq_{rep}^{qk-j}{\mathcal{S}}_{i+1}^{{\sf emb}}[j]$.

###### Proof.

Let $S\in{\mathcal{S}}_{i+1}^{{\sf emb}}[j]$ and $Y$ be a set of size at most
$qk-j$ (which is essentially an independent set of the matroid ${\cal
M}=(\widetilde{U},\mathcal{I})$) such that $S\cap Y=\emptyset$ and $S\cup
Y\in\mathcal{I}$. We will show that there exists a set $S^{\prime}\in{\cal
N}^{i+1}[j]$ such that $S^{\prime}\cap Y=\emptyset$ and $S\cup
Y\in\mathcal{I}$. This will imply the desired result. Since
$S\in{\mathcal{S}}_{i+1}^{{\sf emb}}[j]$ there exists an element $u\in
F_{i+1}$ such that

$S=(S\setminus{\sf embed}(\\{u\\}))\cup{\sf embed}(\\{u\\}).$

Let $S_{i}=(S\setminus{\sf embed}(\\{u\\}))$. Since, $S$ is an independent set
of the matroid ${\cal M}=(\widetilde{U},\mathcal{I})$, we have that $S_{i}$ is
an independent set of the matroid ${\cal M}=(\widetilde{U},\mathcal{I})$
(hereditary property). Further, $|{\sf projection}(S_{i})|=i$ and ${\sf
projection}(S_{i})$ is a hitting set for $F_{1},\ldots,F_{i}$. This implies
that $S_{i}\in{\mathcal{S}}_{i}^{{\sf emb}}$. Let $Y_{i}=Y\cup{\sf
embed}(\\{u\\})$. Notice that since $S\cap Y=\emptyset$ and $S\cup
Y\in\mathcal{I}$, we have that $Y_{i}$ is an independent set and $S_{i}\cup
Y_{i}=S\cup Y\in\mathcal{I}$. Let $|S_{i}|=j^{\prime}$. Then, we know that
${\cal D}[i]$ contains $\widehat{\mathcal{S}}_{i}^{{\sf
emb}}[j^{\prime}]\subseteq_{rep}^{qk-j^{\prime}}{\mathcal{S}}_{i}^{{\sf
emb}}[j^{\prime}]$. This implies that there exists a set
$S_{i}^{\prime}\in\widehat{\mathcal{S}}_{i}^{{\sf emb}}[j^{\prime}]$ such that
$S_{i}^{\prime}\cup Y_{i}\in\mathcal{I}$. This implies that
$S_{i}^{\prime}\cup{\sf embed}(\\{u\\})$ is in ${\cal N}^{i+1}$. Further,
since $|S|=\sum_{x\in{\sf projection}(S)}|{\sf embed}(\\{x\\})|$, we have that
$|S_{i}^{\prime}\cup{\sf embed}(\\{u\\})|=|S_{i}|=j$. This implies that
$S_{i}^{\prime}\cup{\sf embed}(\\{u\\})$ is in ${\cal N}^{i+1}[j]$. Thus, we
can take $S^{\prime}=S_{i}^{\prime}\cup{\sf embed}(\\{u\\})$. This completes
the proof. ∎

We fill the entry for ${\cal D}[i+1]$ as follows. We first compute ${\cal
N}^{i+1}$. Observe that the sets in ${\cal N}^{i+1}$ have sizes ranging from
$i+1$ to $q(i+1)$. Now we apply Proposition 1 on each of ${\cal N}^{i+1}[j]$,
$j\in\\{i+1,\ldots,q(i+1)\\}$, and compute $qk-j$ representative. That is, we
compute $\widehat{{\cal N}}^{i+1}[j]\subseteq_{rep}^{qk-j}{\cal N}^{i+1}[j]$.
We set

${\cal D}[i+1]=\bigcup_{j=i+1}^{q(i+1)}\widehat{{\cal N}}^{i+1}[j].$

Observe that the number of sets in ${\cal D}[i]$ of size $j$ is upper bounded
by ${q(k-i)+j\choose j}\leq{qk\choose di}\leq 2^{{\mathcal{O}}(qk)}$. Hence,
the time taken to compute ${\cal D}[i]$ is upper bounded by
$2^{{\mathcal{O}}(qk)}n^{{\mathcal{O}}(1)}$. Thus, the time taken to compute
${\cal D}[i+1]$ requires at most $qk$ invocations of Proposition 1. This
itself takes $2^{{\mathcal{O}}(qk)}n^{{\mathcal{O}}(1)}$ time. This completes
the proof, resulting in the following result.

See 2

Theorem 2 can be generalized to the scenario where every element in
$\mathcal{U}$ appears in at most $q$ sets in $\mathcal{B}$ and at most $d$
sets in $\mathcal{F}$. Observe that if each element appear in at most $d$ sets
of $\mathcal{F}$, then the total number of sets that a subset of size $k$ of
$\mathcal{U}$ can hit is upper bounded by $dk$, else we immediately return
that given instance is a NO-instance. Let $S=\\{u_{1},\ldots,u_{k}\\}$ be a
hypothetical solution to our problem. Now, with the help of $S$, we partition
$\mathcal{F}$ as follows. Let ${\cal F}_{i}$ denote all sets in $\mathcal{F}$
that contain $u_{i}$ and none of $\\{u_{1},\ldots,u_{i-1}\\}$. Clearly, ${\cal
F}_{i}$, $i\in[k]$, partitions $\mathcal{F}$. Now we can design a dynamic
programming algorithm similar to the one employed in Theorem 2, where in each
iteration we grow our representative family by elements that only hit sets in
${\cal F}_{i}$ and not in ${\cal F}_{j}$, $j>i$. This will result in the
following theorem.

See 3

###  3.3 A Kernel for a Special Case of Fair Hitting Set using Matroids

In this section we design a polynomial kernel for the same special case of
Fair Hitting Set, that we considered in the last section. Let
$(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$ be an
instance of Fair Hitting Set and assume that every element in $\mathcal{U}$
appears in at most $q$ sets in $\mathcal{B}$ and any pair of sets in
$\mathcal{F}$ are pairwise disjoint. To design our kernel we will again use
Lemma 1 that says that an input
$(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$ is a yes-
instance if and only if there exists an independent set $X\in\mathcal{I}$ of
the matroid ${\cal M}=(\widetilde{U},\mathcal{I})$ such that $|{\sf
projection}(X)|\leq k$ and ${\sf projection}(X)$ is a hitting set for
$\mathcal{F}$.

Let $\mathcal{F}=\\{F_{1},F_{2},\ldots,F_{m}\\}$ be the subsets of
$\mathcal{U}$, and $k$ be a positive integer. Since, the sets in $\mathcal{F}$
are pairwise disjoint, the number of sets in $\mathcal{F}$ is upper bounded by
$k$. In particular, we assume that $m=k$. We define ${\cal F}_{i}^{{\sf
emb}}=\\{{\sf embed}(\\{u\\})~{}|~{}u\in F_{i}\\}$. For our kernel we apply
the following reduction rules. We start with some simple reduction rules.

######  Reduction Rule 1.

Let $(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$ be an
instance of Fair Hitting Set.

  * •

If there exists an element $u\in\mathcal{U}$, such that $u$ does not appear in
any sets in $\mathcal{F}$ then delete it from $\mathcal{U}$ and all the sets
in $\mathcal{B}$ that it appears in.

  * •

If there exists a set $B\in\mathcal{B}$ such that $B=\emptyset$, then delete
$B$, and take $f$ as the restriction of $f$ on $\mathcal{B}\setminus\\{B\\}$.

  * •

If there exists a set $B\in\mathcal{B}$ such that $f(B)=0$, then we do as
follows: $\mathcal{U}:=\mathcal{U}\setminus\\{B\\}$; delete all the elements
of $B$ from all the sets in $\mathcal{B}$ and $\mathcal{F}$ that it appears
in. If some set in $\cal F$ becomes empty then return a trivial No-instance.
Else, take $f$ as the restriction of $f$ on $\mathcal{B}\setminus\\{B\\}$ and
keep the integer $k$ unchanged.

Soundness of Reduction Rule 1 is obvious and hence omitted. The next reduction
rule is the main engine of our kernel.

######  Reduction Rule 2.

Let $(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$ be an
instance of Fair Hitting Set. If there exists a pair of integers $i\in[k]$ and
$j\in[q]$ such that $|{\cal F}_{i}^{{\sf emb}}[j]|>{kq\choose j}$, then do as
follows. Compute $\widehat{\cal F}_{i}^{{\sf
emb}}[j]\subseteq_{rep}^{qk-j}{\cal F}_{i}^{{\sf emb}}[j]$. Let $F\in{\cal
F}_{i}^{{\sf emb}}[j]$ that do not appear in $\widehat{\cal F}_{i}^{{\sf
emb}}[j]$. Then obtain a reduced instance as follows.

  * •

$\mathcal{U}:=\mathcal{U}\setminus{\sf projection}(F)$

  * •

Delete ${\sf projection}(F)$ from all the sets in $\mathcal{B}$ and
$\mathcal{F}$ that it appears in.

  * •

The function $f$ and $k$ remains the same.

######  Lemma 2.

Reduction Rule 2 is sound.

###### Proof.

Let $(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$ be an
instance of Fair Hitting Set, and let
$(\mathcal{U}^{\prime},\mathcal{F}^{\prime},\mathcal{B}^{\prime},f:\mathcal{B}\to\mathbb{N},k)$
be the reduced instance, after an application of Reduction Rule 2. It is easy
to see that a solution to the reduced instance can directly be lifted to the
input instance. Thus, we focus on forward direction.

In the forward direction, let $S$ be a solution to
$(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$. Then, by
Lemma 1, it implies that ${\sf embed}(S)\in\mathcal{I}$ (of the matroid ${\cal
M}=(\widetilde{U},\mathcal{I})$) and $|S|\leq k$ and $S={\sf projection}({\sf
embed}(S))$ is a hitting set for $\mathcal{F}$. Let $u={\sf projection}(F)$.
Then, we have that $\mathcal{U}:=\mathcal{U}\setminus\\{u\\}$. If $u\notin S$,
then $S$ is also the solution to
$(\mathcal{U}^{\prime},\mathcal{F}^{\prime},\mathcal{B}^{\prime},f:\mathcal{B}^{\prime}\to\mathbb{N},k)$.
So we assume that $u\in S$.

Observe that $F={\sf embed}(\\{u\\})$, $|F|=j$, and $u$ belongs to $F_{i}$.
Further, since every set in $\cal F$ are pairwise disjoint we have that the
only job of $u$ is to hit the set $F_{i}$. Consider, $Y={\sf
embed}(S)\setminus{\sf embed}(\\{u\\})$. Since, ${\sf
embed}(S)\in\mathcal{I}$, we have that $Y\in\mathcal{I}$ (hereditary property
of the matroid), and the size of $Y$ is upper bounded by $qk-j$. The last
assertion follows from the fact that for any element $v\in\mathcal{U}$, the
size of ${\sf embed}(\\{v\\})$ is upper bounded by $q$ and $|{\sf
embed}(S)|=\sum_{x\in S}|{\sf embed}(\\{x\\})|\leq qk$. This implies that
there exists $F^{\prime}\in\widehat{\cal F}_{i}^{{\sf
emb}}[j]\subseteq_{rep}^{qk-j}{\cal F}_{i}^{{\sf emb}}[j]$ such that
$Y\cup\\{F^{\prime}\\}\in\mathcal{I}$. Since, $|{\sf projection}({\sf
embed}(S))|\leq k$, we have that $|{\sf projection}(Y)|\leq k-1$. Thus, $|{\sf
projection}(Y\cup\\{F^{\prime}\\})|\leq k$. Now we need to show that ${\sf
projection}(Y\cup\\{F^{\prime}\\})$ is a hitting set for $\mathcal{F}$. This
follows from the fact that $u^{\prime}={\sf projection}(F^{\prime})\in F_{i}$.
In other words, we have shown that
$S^{\prime}=S\setminus\\{u\\}\cup\\{u^{\prime}\\}$ is a desired hitting set
for $\mathcal{F}$. This concludes the proof. ∎

Finally, we get the following kernel.

######  Theorem 7.

Let $(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$ be an
instance of Fair Hitting Set such that every element in $\mathcal{U}$ appears
in at most $q$ sets in $\mathcal{B}$ and any pair of sets in $\mathcal{F}$ are
pairwise disjoint. Then, Fair Hitting Set admits a kernel of size
${\mathcal{O}}(kq^{2}{kq\choose q}\log k)$.

###### Proof.

For our algorithm we apply Reduction Rules 1 and 2 exhaustively. If any
application of these rules return that the input is a No-instance, we return
the same. The correctness of the algorithm follows from the correctness of
Reduction Rules 1 and 2. Further it is clear that the algorithm runs in
polynomial time. What remains to show is that the reduced instance is upper
bounded by the claimed function.

For convenience we assume that the reduced instance is also denoted by
$(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$. Since,
Reduction Rule 2 is not applicable we have that each set $F_{i}$, $i\in[k]$,
is upper bounded by $\sum_{j=1}^{q}{kq\choose j}\leq q{kq\choose q}$. This
implies that $|\mathcal{U}|\leq kq{kq\choose q}$. Further, since every element
in $\mathcal{U}$ appears in at most $q$ sets in $\mathcal{B}$, we have that
the number of non-empty sets in $\mathcal{B}$ is upper bounded by
$q|\mathcal{U}|\leq kq^{2}{kq\choose q}$. Since, Reduction Rule 1 is not
applicable we have that there are no empty-sets and hence $|\mathcal{B}|\leq
kq^{2}{kq\choose q}$. Further, to represent the function $f$ we need at most
${\mathcal{O}}(|\mathcal{B}|\log k)\leq{\mathcal{O}}(kq^{2}{kq\choose q}\log
k)$ bits. This completes the proof. ∎

##  4 Reduction from $K_{d,d}$-free $G_{\mathcal{U},\mathcal{F}}$ to Bounded
Frequency in $\mathcal{F}$

We give an alternate, self-contained proof of this theorem in Section 4. This
reduction is used as the first step in some of our results, such as Section 6.
We note that a part of the kernelization procedure in Section 5 can also be
used to prove the following theorem.

######  Theorem 8.

Let $\mathcal{I}=(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ be an instance of
Fair Hitting Set, where $G_{\mathcal{U},\mathcal{F}}$ is $K_{d,d}$ free, and
$G_{\mathcal{U},\mathcal{B}}$ satisfies a hereditary property $\Pi$.

Suppose there exists an algorithm $\mathcal{A}$ that, given an instance
$\mathcal{I}^{\prime}=(\mathcal{U}^{\prime},\mathcal{F}^{\prime},\mathcal{B}^{\prime},f^{\prime},k^{\prime})$
such that (1) every element of $\mathcal{U}^{\prime}$ appears in at most
$\Delta$ sets of $\mathcal{F}^{\prime}$, and (2)
$G_{\mathcal{U}^{\prime},\mathcal{B}^{\prime}}$ satisfies $\Pi$, decides in
time $h(k^{\prime},\Delta)\cdot|\mathcal{I}^{\prime}|^{\mathcal{O}(1)}$,
whether $\mathcal{I}^{\prime}$ is a yes-instance of Fair Hitting Set. Then,
there exists an algorithm that runs in time
$g(k,d)\cdot|\mathcal{I}|^{\mathcal{O}(1)}$ to decide whether $\mathcal{I}$ is
a yes-instance of Fair Hitting Set.

###### Proof.

Let $G=G_{\mathcal{U},\mathcal{F}}$ be an incidence graph corresponding to the
set system $(\mathcal{U},\mathcal{F})$ in instance $\mathcal{I}$. The proof of
the theorem relies on the following modification of a classical lemma from
parameterized algorithms. The lemma guarantees that, as long as there exists
an element that is contained in a large number of sets in $\mathcal{F}$, we
can branch on a set of at most $d-1$ elements.

######  Lemma 3.

If there exists an element $u\in\mathcal{U}$ such that $deg_{G}(u)\geq
dk^{d-1}$, then in polynomial time we can find a set $X\subseteq\mathcal{U}$
of size at most $d-1$ that intersects every fair hitting set for $\mathcal{F}$
of size at most $k$.

###### Proof.

Suppose there exists $u\in\mathcal{U}$ such that $deg_{G}(u)\geq dk^{d-1}$.
Let $X=\\{u_{1},\ldots,u_{\ell}\\}\subseteq\mathcal{U}$ be a maximal set such
that for all $p\leq\ell$ we have that $\bigcap_{i=1}^{p}N_{G}(u_{i})\geq
dk^{d-p}$. Such a set $X$ can be found in polynomial time by greedily
selecting the vertices. Observe that $\ell\leq d-1$, otherwise
$\bigcap_{i=1}^{\ell}N_{G}(u_{i})\geq dk^{d-\ell}\geq d$, , it would imply an
existence of $K_{d,d}$ in $(\mathcal{U},\mathcal{F})$.

Let $\mathcal{F}_{X}=\bigcap_{i=1}^{\ell}N_{G}(u_{i})$, and note that
$|\mathcal{F}_{X}|\geq dk^{d-\ell}$. For every vertex
$u^{\prime}\in\mathcal{U}\setminus X$, we have
$|N(u^{\prime})\cap\mathcal{F}_{X}|<dk^{d-\ell-1}$. We next claim that every
fair hitting set $H\subseteq\mathcal{U}$ for $\mathcal{F}$ of size at most $k$
satisfies $H\cap X\neq\emptyset$. Fix, a hitting set $H^{\prime}$ for
$\mathcal{F}$ of size $k$ and suppose $H^{\prime}\cap X=\emptyset$. Then the
number of sets of $\mathcal{F}_{X}$ that are hit by $k$ elements of
$H^{\prime}\subseteq\mathcal{U}\setminus X$ is less than $k\cdot
dk^{d-\ell-1}=dk^{d-\ell}\leq|\mathcal{F}_{X}|$. Thus, there exists a set in
$\mathcal{F}_{X}\subseteq\mathcal{F}$ not hit by $H^{\prime}$, which
contradicts the assumption that $H^{\prime}$ hits $\mathcal{F}$. Therefore,
$|H^{\prime}\cap X|\neq\emptyset$. ∎

Suppose there exists an element with at least $dk^{d-1}$ neighbors in
$\mathcal{F}$. Then, we use the algorithm from Lemma 3 to obtain a set
$X=\\{u_{1},\ldots u_{\ell}\\}$, where $\ell\leq d-1$. Now, we branch on each
element $u\in X$. More specifically, we make a recursive corresponding to a
new instance defined w.r.t. $u$, as follows.
$\tilde{\mathcal{I}}=(\tilde{\mathcal{U}},\tilde{\mathcal{F}},\tilde{\mathcal{B}},\tilde{k},\tilde{f})$,
where $\widetilde{\mathcal{U}}=\mathcal{U}\setminus\\{u\\}$,
$\widetilde{\mathcal{F}}=\mathcal{F}-\\{u\\}$,
$\widetilde{\mathcal{B}}=\mathcal{B}-\\{u\\}$, $\widetilde{k}=k-1$, and for
every $B_{j}\in\mathcal{B}$, we set
$\tilde{f}(B_{j})=\begin{cases}f(B_{j})&\text{ if $u\not\in B_{j}$}\\\
f(B_{j})-1&\text{ if $u\in B_{j}$}\end{cases}$.

Else, there is no element with at least $dk^{d-1}$ neighbors in $\mathcal{F}$.
Thus, every element in $\mathcal{U}$ appears in at most $dk^{d-1}$ sets in
$\mathcal{F}$. We set $\Delta=dk^{d-1}$, then use algorithm $\mathcal{A}$ to
solve the instance $\mathcal{I}$ in
$h(k,\Delta)\cdot|\mathcal{I}|^{\mathcal{O}(1)}$ time.

Now we analyze the running time. At every recursive call we decrease $k$ by 1,
and thus the height of the search tree does not exceed $k$. At every step we
branch on at most $d-1$ subproblems. Hence, the number of leaves in the search
tree is at most $(d-1)^{k}$. At each leaf node either $k\leq 0$, in which case
we solve instance $\mathcal{I}$ in polynomial time. Otherwise, a leaf node
corresponds to the case when we cannot branch, since Lemma 3 cannot be
applied. In this case, each element of $\mathcal{U}$ is contained in at most
$\Delta\coloneqq dk^{d-1}$ sets of $\mathcal{F}$. In this case, we use
algorithm $\mathcal{A}$, which solves instance $\mathcal{I}^{\prime}$ in
$h({k^{\prime}},\Delta)\cdot|{\mathcal{I}^{\prime}}|^{\mathcal{O}(1)}=h^{\prime}(k,d)\cdot|\mathcal{I}|^{\mathcal{O}(1)}$
time, for some function $g$. Thus, the total time taken by the algorithm is
$(d-1)^{k}\cdot
h^{\prime}(k,d)\cdot|\mathcal{I}|^{\mathcal{O}(1)}=g(k,d)\cdot|\mathcal{I}|^{\mathcal{O}(1)}$,
as desired. ∎

##  5 Polynomial Kernel for $K_{d,d}$-free $G_{\mathcal{U},\mathcal{F}}$ and
Bounded Frequency in $\mathcal{B}$

Consider an input
$(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$ of Fair
Hitting Set. In this section we design a polynomial kernel for Fair Hitting
Set problem when $G_{\mathcal{U},\mathcal{F}}$ is $K_{d,d}$-free and frequency
of each element in $\mathcal{B}$ is at most $q$. We fix $d$ and $q$ for the
rest of the section. Without loss of generality we assume that $d\geq 2$,
$k\geq 2$. We also assume that we do not have multisets in $\mathcal{F}$ and
$\mathcal{B}$. The kernelization algorithm consists of two phases: In phase
one we apply some reduction rules to bound the size of $|\mathcal{F}|$. In
phase two we use partition matroid ${\cal M}=(\widetilde{U},\mathcal{I})$
defined in Section 3.1 using $\mathcal{B}$ to design a reduction rule to bound
the number of elements. Next, we state our reduction rules that the
kernelization algorithm applies in the order in which they are stated. For a
subset $\mathcal{B}^{\prime}\subseteq\mathcal{B}$, by
$f^{\prime}=f_{|\mathcal{B}^{\prime}}$, we denote the function $f$ restricted
to $\mathcal{B}^{\prime}$. We begin with the following simple reduction rule
that removes empty sets from $\mathcal{B}$.

######  Reduction Rule 3.

If there exists a set $B\in\mathcal{B}$ such that $B=\emptyset$, then delete
$B$, and take $f$ as the restriction of $f$ on $\mathcal{B}\setminus\\{B\\}$.
Return the instance
$\mathcal{I}^{\prime}=(\mathcal{U},\mathcal{F},\mathcal{B}^{\prime},f^{\prime},k)$,
where $\mathcal{B}^{\prime}=\mathcal{B}\setminus\\{B\\}$ and
$f^{\prime}=f_{|\mathcal{B}^{\prime}}$.

Next reduction rule removes sets in $\mathcal{B}$ that do not interest with
any set in $\mathcal{F}$.

######  Reduction Rule 4.

If there exists an element $u\in\mathcal{U}$ such that $u$ is not contained in
any set in $\mathcal{F}$, that is for every $F\in\mathcal{F}$, $u\notin F$,
then remove $u$ from every set in $B$. Return the instance
$\mathcal{I}^{\prime}=(\mathcal{U}^{\prime},\mathcal{F},\mathcal{B}^{\prime},f,k)$,
where $\mathcal{U}^{\prime}=\mathcal{U}\setminus\\{u\\}$,
$\mathcal{B}^{\prime}=\mathcal{B}-\\{u\\}$.

The next reduction rule removes sets in $\mathcal{B}$ that have $f$ value less
than 1.

######  Reduction Rule 5.

If there exists a set $B\in\mathcal{B}$ such that $f(B)\leq 0$, if there
exists a set $F\in\mathcal{F}$ such that $F\subseteq B$, then return that
$(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ is a no-instance of Fair Hitting
Set, otherwise from every set $F\in\mathcal{F}$ delete elements that are
contained in $B$. Return the instance
$\mathcal{I}^{\prime}=(\mathcal{U}^{\prime},\mathcal{F}^{\prime},\mathcal{B}^{\prime},f^{\prime},k)$,
where $\mathcal{U}^{\prime}=\mathcal{U}\setminus B$,
$\mathcal{F}^{\prime}=\mathcal{F}-B$,
$\mathcal{B}^{\prime}=\mathcal{B}\setminus\\{B\\}$,
$f^{\prime}=f_{|\mathcal{B}^{\prime}}$.

We will use the following variant of Lemma 3 to design our next reduction rule
which will bound the degree of a vertex in $U$ in the graph
$G_{U,\mathcal{F}}$.

######  Claim 2.

If there exists an element $u\in\mathcal{U}$ such that $|\mathcal{F}(u)|\geq
dk^{d-1}$, then in polynomial time we can find a inclusion-maximal set
$X\subseteq\mathcal{U}$ of size at most $d-1$ such that $|\bigcap_{v\in
X}\mathcal{F}(v)|\geq dk^{d-|X|}$ and for every fair hitting set $S$ for
$\mathcal{F}$ of size at most $k$, $S\cap X\neq\emptyset$.

Observe that in the above claim when $|X|>1$, $|\bigcap_{v\in
X}\mathcal{F}(v)|\geq 2$. The proof of Lemma 3 also holds for the above claim.

######  Reduction Rule 6.

If there exists an element $u\in\mathcal{U}$ such that $\mathcal{F}(u)\geq
dk^{d-1}$, then let $X$ be the output of the algorithm in Claim 2. Consider
the following cases:

  1. 1.

If $|X|=1$, and let $X=\\{u\\}$, then proceed as follows; Delete all the sets
containing $u$ from $\mathcal{F}$. Let $\mathcal{F}^{\prime}=\\{F|u\notin
F,F\in\mathcal{F}\\}$. Next,delete $u$ from every set $B\in\mathcal{B}$ and
reduce $f(B)$ by 1, let $\mathcal{B}^{\prime}=\mathcal{B}-\\{u\\}$. Finally
reduce $k$ by 1. Return the instance
$\mathcal{I}^{\prime}=(\mathcal{U}^{\prime},\mathcal{F}^{\prime},\mathcal{B}^{\prime},f,k^{\prime})$,
where $\mathcal{U}^{\prime}=\mathcal{U}\setminus\\{u\\}$, $f^{\prime}=f(B)-1$,
if $u\in B$, otherwise $f^{\prime}=f(B)$ and $k^{\prime}=k-1$.

  2. 2.

If $|X|>1$, then we delete all the sets from $\mathcal{F}$ that contain the
set $X$ and add the set $X$ to $\mathcal{F}$. Return the instance
$\mathcal{I}^{\prime}=(\mathcal{U}^{\prime},\mathcal{F}^{\prime},\mathcal{B},f,k)$,
where $\mathcal{F}^{\prime}=\\{F|X\nsubseteq F,F\in\mathcal{F}\\}\cup\\{X\\}$,
$\mathcal{U}^{\prime}=\bigcup_{F\in\mathcal{F}^{\prime}}F$.

######  Lemma 4.

Reduction Rule 6 is correct, and either reduces the size of $\mathcal{U}$ or
that of $\mathcal{F}$.

###### Proof.

Note that $G_{\mathcal{U}^{\prime},cF^{\prime}}$ remains $K_{d,d}$-free even
after adding the set $X$ to $\mathcal{F}^{\prime}$. The proof of case when
$|X|=1$ follows from the Claim 2. Next we prove lemma for case when $|X|>1$.
To show that the lemma holds we will show that
$(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ is a yes-instance of Fair Hitting
Set if and only if
$(\mathcal{U}^{\prime},\mathcal{F}^{\prime},\mathcal{B},f,k)$ is a yes
instance of Fair Hitting Set. In the forward direction suppose that
$(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ is a yes-instance of Fair Hitting
Set and let $S$ be its solution. By Claim 2, $S\cap X\neq\emptyset$, therefore
$S$ is also a hitting set of $\mathcal{F}^{\prime}$ and hence a fair hitting
set of $(\mathcal{U}^{\prime},\mathcal{F}^{\prime},\mathcal{B},f,k)$. In the
backward direction suppose that
$(\mathcal{U}^{\prime},\mathcal{F}^{\prime},\mathcal{B},f,k)$ is a yes
instance of Fair Hitting Set. and let $S^{\prime}$ be its solution. We claim
that $S^{\prime}$ is also a hitting set of $\mathcal{F}$. Suppose that for a
contradiction there exists $F\in\mathcal{F}$, that is not hit by $S^{\prime}$.
Then $F\notin\mathcal{F}^{\prime}$, however by our construction of
$\mathcal{F}^{\prime}$, $X\subseteq F$. As $X\in\mathcal{F}^{\prime}$, $X\cap
S^{\prime}\neq\emptyset$ and $S^{\prime}$ must hit $F$, a contradiction. Hence
$S^{\prime}$ is a fair hitting set of
$(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$. This concludes the proof. ∎

Observe that the Reduction Rule 6 is not applicable in polynomial time and
only polynomial many times as in the first case when $|X|=1$ since Reduction
Rule 4 is not applicable the sets in $\mathcal{F}$ containing $X$ must be at
least 1, and in second case when $|X|>1$, by Claim 2, the sets in
$\mathcal{F}$ containing $X$ must be at least $2$.

Observe that when Reduction Rule 6 is no longer applicable then each element
is contained in at most $dk^{d-1}$ sets in $\mathcal{F}$.

######  Reduction Rule 7.

If Reduction Rules 4-6 are no longer applicable and $|\mathcal{F}|>dk^{d}$,
then return that $(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ is a no-instance
of Fair Hitting Set.

Note that if Reduction rule 7 is not applicable, then the size of
$|\mathcal{F}|$ is bounded by $dk^{d}$.

######  Remark 1.

Note that in Reduction rule 3 to Reduction rule 7, we did not use any property
of the $(\mathcal{U},\mathcal{B})$ set system, except that we may delete an
element of $\mathcal{U}$ or a set from $\mathcal{B}$. Thus, in the resulting
instance, the $G_{\mathcal{U},\mathcal{B}}$ satisfies the property $\Pi$.
Therefore, we can use Reduction rule 3 to Reduction rule 7 as an alternate way
of obtaining a proof of Theorem 8.

######  Remark 2.

As observed before, at this point the size of $|\mathcal{F}|$ is upper bounded
by $dk^{d}$. Now, we use an approach similar to Theorem 3 to obtain an FPT
algorithm for Fair Hitting Set that runs in time $d^{k}k^{kd}\cdot
2^{\mathcal{O}(kq)}\cdot|\mathcal{I}|^{\mathcal{O}(1)}$.

Back to kernelization. Let $A_{\geq d}$ be the set of all the elements with
degree at least $d$ in $G_{\mathcal{U},\mathcal{F}}$. As
$G_{\mathcal{U},\mathcal{F}}$ is $K_{d,d}$-free we obtain the following
observation.

######  Observation 2.

$|A_{\geq d}|\leq{{|\mathcal{F}|}\choose{d}}\cdot d$.

For a set $\mathcal{Y}\subseteq\mathcal{F}$ of size at most $d-1$, we denote
the set ${\sf ExactNbr}(\mathcal{Y})$ to be the set of all the elements
$u\in\mathcal{U}$ such that $\mathcal{F}(u)=\mathcal{Y}$, that is $u$ is only
contained in all the sets in $\mathcal{Y}$. Next, we state a reduction rule
that bounds elements in ${\sf ExactNbr}(\mathcal{Y})$. For this purpose we use
partition matroid ${\cal M}=(\widetilde{U},\mathcal{I})$ defined in Section
3.1. Recall that for constructing $\mathcal{M}$, we add ${\sf
copies}(u)=\\{u^{1},u^{2},\ldots,u^{deg_{G_{\mathcal{U},\mathcal{B}}}(u)}\\}$
for each element $u\in\mathcal{U}$ to $\widetilde{U}$. For ease of proof we
add dummy copies of every element to make the frequency of every element
exactly $q$ in $\mathcal{B}$, that is we let ${\sf
copies}(u)=\\{u^{1},u^{2},\ldots,u^{q}\\}$ for every element
$u\in\mathcal{U}$. We add a new set $B^{*}$ to $\mathcal{B}$ and for every
element $u$ with frequency $q^{\prime}<q$ in $\mathcal{B}$, we add
$\\{u^{q^{\prime}+1},\ldots,u^{q}\\}$ to $B^{*}$. We let $f(B^{*})=kq$. Now we
define the partition matroid ${\cal M}=(\widetilde{U},\mathcal{I})$ as defined
in Section 3.1. Next, we define a family $\mathcal{P}_{\mathcal{Y}}=\\{{\sf
copies}(u)|u\in{\sf ExactNbr}(\mathcal{Y})\\}$ and apply the for reduction
rule for every set $\mathcal{Y}\subseteq\mathcal{F}$ of size at most $d-1$.

######  Reduction Rule 8.

Let $(\mathcal{U},\mathcal{F},\mathcal{B},f:\mathcal{B}\to\mathbb{N},k)$ be an
instance of Fair Hitting Set. If there exists a set
$\mathcal{Y}\subseteq\mathcal{F}$ such that $|\mathcal{Y}|\leq d-1$ and ${\sf
ExacrNbr}(\mathcal{Y})>{kq\choose j}$, then do as follows. Compute
$\widehat{\mathcal{P}}_{\mathcal{Y}}\subseteq_{rep}^{kq-q}{\mathcal{P}}_{\mathcal{Y}}$.
Let $u\in{\sf ExacrNbr}(\mathcal{Y})$ such that ${\sf
copies}(u)\in{\mathcal{P}}_{\mathcal{Y}}$ and ${\sf
copies}(u)\notin\widehat{\mathcal{P}}_{\mathcal{Y}}$. Then delete $u$ from
every set in $\mathcal{F}$ and every set in $\mathcal{B}$. Let
$\mathcal{U}^{\prime}=\mathcal{U}\setminus\\{u\\}$,
$\mathcal{F}^{\prime}=\\{F\setminus\\{u\\}|F\in\mathcal{F}\\}$,
$\mathcal{B}^{\prime}=\\{B\setminus\\{u\\}|B\in\mathcal{B}\\}$, and
$f^{\prime}(B\setminus\\{u\\})=f(B)$ for each $B\in\mathcal{B}$. Return the
instance
$\mathcal{I}^{\prime}=(\mathcal{U}^{\prime},\mathcal{F}^{\prime},\mathcal{B}^{\prime},f,k)$.

######  Lemma 5.

Reduction Rule 8 is correct.

###### Proof.

To show that the lemma holds we will show that
$(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ is a yes-instance of Fair Hitting
Set if and only if
$(\mathcal{U}^{\prime},\mathcal{F}^{\prime},\mathcal{B}^{\prime},f,k)$ is a
yes instance of Fair Hitting Set. Observe that the backward direction holds
trivially. To prove the forward direction suppose that
$(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ is a yes-instance of Fair Hitting
Set and let $S\subseteq\mathcal{U}$ be its solution of size at most $k$.
Observe that if $u\notin S$, then $S$ is also a solution to
$(\mathcal{U}^{\prime},\mathcal{F}^{\prime},\mathcal{B}^{\prime},f,k)$.
Suppose that $u\in S$. Let $\mathcal{S}=\\{{\sf copies}(v)|v\in S\\}$. By
Lemma 1 $\mathcal{S}$ is an independent set of the matroid ${\cal
M}=(\widetilde{U},\mathcal{I})$. Let
$\mathcal{S}^{\prime}=\mathcal{S}\setminus\\{{\sf copies}(u)\\}$. Notice that
$|\mathcal{S}^{\prime}|\leq kq-q$, as we have frequency exactly $q$ for each
element of $\mathcal{U}$ in $\mathcal{B}$. Therefore as
$\widehat{\mathcal{P}}_{\mathcal{Y}}$, is a ${kq-q}$ representative family of
${\mathcal{P}}_{\mathcal{Y}}$ and ${\sf
copies}(u)\notin\widehat{\mathcal{P}}_{\mathcal{Y}}$ there must exists an
element $v\in{\sf ExacrNbr}(\mathcal{Y})$ such that ${\sf
copies}(v)\in\widehat{\mathcal{P}}_{\mathcal{Y}}$ and
$\mathcal{S}^{\prime}\cup\\{{\sf copies}(v)\\}$ must be an independent set of
the matroid ${\cal M}=(\widetilde{U},\mathcal{I})$. Let $S^{\prime}={\sf
projection}(\mathcal{S}^{\prime})$, by our construction of matroid ${\cal M}$,
$S^{\prime}$ satisfies $f$. Also observe that $S^{\prime}$ is a hitting set of
$\mathcal{F}$ since $S\setminus\\{u\\}=S^{\prime}\setminus\\{v\\}$ and
$\mathcal{F}(u)=\mathcal{F}(v)=\mathcal{Y}$. ∎

######  Observation 3.

When Reduction Rule 8 is no longer applicable, then for every
$\mathcal{Y}\subseteq\mathcal{F}$ size of the set ${\sf
ExactNbr}(\mathcal{Y})$ is bounded by ${kq\choose q}$.

By the above observation the number of elements with degree at most $d-1$ in
$G_{\mathcal{U},\mathcal{F}}$ is bounded by
$d\cdot{{|\mathcal{F}|}\choose{d}}\cdot{kq\choose q}$. Therefore by
observation 2 the number of elements in $\mathcal{U}$ is bounded by
$\mathcal{O}(k^{\mathcal{O}(d^{2}+q)}d^{d}q^{q})$. Observe that each of our
reduction rules can be applied in polynomial time and only polynomial times.
Thus we obtain the following theorem.

See 4

##  6 Parameterization by $k+d$ when $G_{\mathcal{U},\mathcal{B}}$ is Nowhere
Dense and $G_{\mathcal{U},\mathcal{F}}$ is $K_{d,d}$-free

In this section, we give a formal proof of Theorem 5. For convenience, we
restate the theorem. See 5

We prove Theorem 5 by reducing the problem to FO model checking on a colored
graph, whose $\\{E\\}$-restriction is equal to $G$.

We define the following notation. For a non-empty set $A$, and an integer
$0\leq b\leq|A|$, we use $\binom{A}{\leq b}$ to denote the family of all
subsets of $A$ of size at most $b$. For each subset
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$, we define
$\mathcal{U}_{\mathcal{F}^{\prime}}\coloneqq\\{u\in\mathcal{U}:\mathcal{F}(u)=\mathcal{F}^{\prime}\\}$,
that is, $\mathcal{U}_{\mathcal{F}^{\prime}}$ is the subset of elements $u$
such that $\mathcal{F}^{\prime}$ is exactly the subset of $\mathcal{F}$
containing $u$ (alternatively, $\mathcal{F}^{\prime}$ is the subset hit by
$u$). Note that
$\mathcal{P}_{U}\coloneqq\\{\mathcal{U}_{\mathcal{F}^{\prime}}:\mathcal{F}^{\prime}\subseteq\mathcal{F}\text{
and }\mathcal{U}_{\mathcal{F}^{\prime}}\neq\emptyset\\}$ is a partition of the
universe $\mathcal{U}$ into at most $2^{m}$ parts, where $m=|\mathcal{F}|$.
Similarly, for $1\leq t\leq k$, we define
$\mathcal{B}_{t}\coloneqq\\{B_{j}\in\mathcal{B}:f(B_{j})=t\\}$. Again, observe
that $\mathcal{P}_{B}\coloneqq\\{\mathcal{B}_{t}:1\leq t\leq k\text{ and
}\mathcal{B}_{t}\neq\emptyset\\}$ is a partition of $\mathcal{B}$ into at most
$k$ parts

Let $\sigma^{\prime}=\\{E(G)\\}$, and recall that recall that the graph $G$
can be thought of as an $\sigma^{\prime}$-structure. Now, we define
$\sigma=\sigma^{\prime}\cup\mathcal{P}_{U}\cup\mathcal{P}_{B}$, where we think
of each $\mathcal{U}_{\mathcal{F}^{\prime}}$, and $\mathcal{B}_{t}$ as a unary
relation on $V(G)$. Note that the number of relations in $\sigma$ is at most
$1+k+2^{m}$. Let $G^{\prime}$ be the resulting $\sigma$-structure, and note
that its underlying graph $G$ belongs to a nowhere dense class $\mathcal{G}$.

We need the following definition.

######  Definition 4 (Valid Pair).

We say that a pair $(k^{\prime},\mathbb{F})$ is a _valid pair_ if it satisfies
the following properties.

  1. 1.

$k^{\prime}\in[k]$, and

  2. 2.

$\mathbb{F}=(\mathcal{F}_{1},\mathcal{F}_{2},\ldots,\mathcal{F}_{k^{\prime}})$,
where each $\mathcal{F}_{i}$ is a non-empty subset of $\mathcal{F}$, and
$\bigcup_{i=1}^{k^{\prime}}\mathcal{F}_{i}=\mathcal{F}$.

We observe that the number of valid pairs is upper bounded by $k\cdot
2^{\mathcal{O}(km)}$.

Next, corresponding to each valid pair $(k^{\prime},\mathbb{F})$, we define a
formula in $\textup{{FO}}[\sigma]$, as follows:

######  Definition 5 (Formula corresponding to a valid pair).

Fix a valid pair $(k^{\prime},\mathbb{F})$, where
$\mathbb{F}=(\mathcal{F}_{1},\mathcal{F}_{2},\ldots,\mathcal{F}_{k^{\prime}})$.
We define $\varphi_{k^{\prime},\mathbb{F}}\in\textup{{FO}}[\sigma]$ as
follows:

$\displaystyle\varphi_{k^{\prime},\mathbb{F}}\coloneqq\exists
u_{1},u_{2},\ldots,u_{k^{\prime}}$
$\displaystyle\left(\textup{{enforce-}}\mathbb{F}(U)\land\left(\bigwedge_{t\in[k]:\mathcal{B}_{t}\neq\emptyset}\psi_{t}(U)\right)\right)$

where, we use the shorthand $U=(u_{1},u_{2},\ldots,u_{k^{\prime}})$, and

  * •

$\textup{{enforce-}}\mathbb{F}(U)\coloneqq\bigwedge_{i=1}^{k^{\prime}}(u_{i}\in\mathcal{U}_{\mathcal{F}_{i}})$,

  * •

For $1\leq t\leq k$,

$\displaystyle\psi_{t}(U)\coloneqq\forall B_{t},$
$\displaystyle\qquad(B_{t}\in\mathcal{B}_{t})\ \implies\
\bigvee_{Q\in\binom{[k^{\prime}]}{\leq t}}\textup{{exact-nbr}}_{Q}(B_{t},U)$

  * •

For $1\leq t\leq k$, and $Q\in\binom{[k^{\prime}]}{\leq t}$,

$\displaystyle\textup{{exact-nbr}}_{Q}(B_{t},U)\coloneqq$
$\displaystyle\left(\bigwedge_{j\in Q}\\{B_{t},u_{j}\\}\in E(G)\right)\land$
$\displaystyle\left(\bigwedge_{j^{\prime}\not\in
Q}\\{B_{t},u_{j^{\prime}}\\}\not\in E(G)\right)$

######  Observation 4.

For any valid pair $(k^{\prime},\mathbb{F})$, it holds that
$|\varphi_{k^{\prime},\mathbb{F}}|\leq h^{\prime}(k,m)$ for some function
$h(\cdot,\cdot)$, assuming a suitable encoding.

###### Proof.

For every $1\leq t\leq k$, and $Q\in\binom{[k]}{\leq t}$, the formula
$\textup{{exact-nbr}}_{t},Q(B_{t},U)$ is a conjunction of $2^{m}$ atomic
formulas of constant size. Then, for $1\leq t\leq k$, the formula
$\psi_{t}(U)$ is a conjunction of an atomic formula of a constant size, and
the disjunction of $\sum_{i=0}^{t}\binom{k}{t}\leq 2^{k}$ formulas of the type
$\textup{{exact-nbr}}_{t},Q(B_{t},U)$, and the size of each such formula is
bounded by $2^{\mathcal{O}(m)}$. Therefore, the size of each $\psi_{t}(U)$ is
upper bounded by $2^{\mathcal{O}(km)}$. The formula
$\textup{{enforce-}}\mathbb{F}(U)$ is of size $\mathcal{O}(k^{\prime})$.
Finally, the formula $\varphi_{k^{\prime},\mathbb{F}}$ is obtained by taking
conjunction of $\textup{{enforce-}}\mathbb{F}(U)$, along with
$\psi_{1}(U),\psi_{2}(U),\ldots,\psi_{k}(U)$. Therefore, the size of
$\varphi_{k^{\prime},\mathbb{F}}$ is upper bounded by $2^{\mathcal{O}(km)}$. ∎

Now, we are ready to prove the main technical lemma of this section.

######  Lemma 6.

$\mathcal{I}$ is a yes-instance of Fair Hitting Set iff for some valid pair
$(k^{\prime},\mathbb{F}^{\prime})$, it holds that
$V(G)\models\varphi_{k^{\prime},\mathbb{F}}$.

###### Proof.

Forward direction. Let $S\subseteq\mathcal{U}$ be a fair hitting set of
$\mathcal{F}$ of size $1\leq k^{\prime}\leq k$. Let us arbitrarily number the
vertices of $S$ as $v_{1},v_{2},\ldots,v_{k^{\prime}}$. For each $1\leq i\leq
k^{\prime}$, let $\mathcal{F}_{i}=\mathcal{F}(u_{i})$, i.e.,
$u_{i}\in\mathcal{U}_{\mathcal{F}_{i})}$. Let
$\mathbb{F}=(\mathcal{F}_{1},\mathcal{F}_{2},\ldots,\mathcal{F}_{k^{\prime}})$.
We claim that $V(G)\models\varphi_{k^{\prime},\mathbb{F}}$, for the setting
$u_{i}=v_{i}$ of the existentially quantified variables.

First, it is easy to see that $\textup{{enforce-}}\mathbb{F}(U)$ is satisfied
since every $v_{i}$ belongs to $\mathcal{U}_{\mathcal{F}_{i})}$ by
construction. Next, we claim that every $\psi_{t}$, such that
$\mathcal{B}_{t}\neq\emptyset$ is satisfied. Fix one such $t$. Note that for
the formula $\psi_{t}$, it suffices to focus on $B_{t}\in\mathcal{B}_{t}$,
i.e., for the $B_{t}$’s such that $f(B_{t})=t$. In other words, it suffices to
show that for every $B_{t}\in\mathcal{B}_{t}$, the formula $\textup{{exact-
nbr}}_{Q,t}(B_{t},U)$ is satisfied for some $Q\in\binom{[k]}{\leq t}$. To this
end, let $Q=\\{j\in[k^{\prime}]:v_{j}\in B_{t}\\}$. Note that since $S$ is a
fair hitting set, $|Q|\leq f(B_{t})=t$. It is easy to verify that the formula
$\textup{{exact-nbrhood}}_{Q,t}(B_{t},U)$ is satisfied, since it checks
whether the intersection of $S$ with $B_{t}$ is exactly the set corresponding
to $Q$. Thus, $V(G)\models\varphi_{k^{\prime},\mathbb{F}}$.

Reverse direction. Suppose $V(G)\models\varphi_{k^{\prime},\mathbb{F}}$ for
some valid pair $(k^{\prime},\mathbb{F})$, with
$\mathbb{F}=(\mathcal{F}_{1},\mathcal{F}_{2},\ldots,\mathcal{F}_{k^{\prime}})$.
For $1\leq i\leq k^{\prime}$, let $v_{i}$ be equal to the existentially
quantified vertex $u_{i}$ in a model of $\varphi_{k^{\prime},\mathbb{F}}$. Let
$S=\\{v_{1},v_{2},\ldots,v_{k^{\prime}}\\}$. We claim that $S$ is a fair
hitting set for $\mathcal{F}$. Note that for $1\leq i\leq k^{\prime}$,
$v_{i}\in\mathcal{F}_{k^{\prime}}$. Then, from the definition of a valid pair,
it follows that $\bigcup_{i=1}^{k^{\prime}}\mathcal{F}_{i}=\mathcal{F}$, which
implies that $S$ hits every set in $\mathcal{F}$.

Now we argue that for every $B_{j}\in\mathcal{B}$, $|S\cap B_{j}|\leq
f(B_{j})$. First, note that at most one formula from the disjunction
$\bigvee_{Q\in\binom{[k^{\prime}]}{\leq t}}\textup{{exact-
nbr}}_{t,Q}(B_{j},U)$ can be satisfied, since the disjunction is over mutually
exclusive choices for the intersection of a $B_{j}$ with $U$. Now Consider a
$B_{j}\in\mathcal{B}_{t}$, i.e.,$f(B_{j})=t$. Then, $\mathcal{B}_{t}$ is non-
empty. Consider the formula $\psi_{t}(U)$, and note that $B_{j}$ satisfies
$B_{j}\in\mathcal{B}_{t}$. This implies that the consequent formula of the
implication is also satisfied, which, in turn implies that there exists a
unique $Q\in\binom{[k^{\prime}]}{\leq t}$ such that the formula
$\textup{{exact-nbr}}_{t,Q}(B_{j},U)$ is satisfied. Now, let
$S_{Q}=\\{v_{i}:i\in Q\\}$, and note that $S_{Q}=S\cap B_{j}$. Therefore,
$|B_{j}\cap S|=|S_{Q}|=|Q|\leq t=f(B_{j})$. This shows that $S$ is a fair
hitting set for $\mathcal{F}$. ∎

Completing the proof of Theorem 5. The algorithm iterates over all
$2^{\mathcal{O}(km)}$ valid pairs $(k^{\prime},\mathbb{F})$, and uses the
algorithm from Theorem 6 to check whether the colored graph $G^{\prime}$
models the formula $\varphi_{k^{\prime},\mathbb{F}}$. Since the underlying
graph $G$ belongs to a nowhere dense class $\mathcal{G}$, it follows that the
model checking algorithm runs in time
$f(|\varphi_{k^{\prime},\mathbb{F}}|)n^{\mathcal{O}(1)}$ (by setting
$\epsilon$ to be some constant, say). If in any iteration the FO model
checking algorithm answers yes, the algorithm concludes that $\mathcal{I}$ is
a yes-instance of Fair Hitting Set. Otherwise, the algorithm returns that
$\mathcal{I}$ is a no-instance of Fair Hitting Set. This concludes the proof
of Theorem 5.

##  7 Parameterization by $k+|\mathcal{F}|$ when $G_{\mathcal{U},\mathcal{B}}$
is Apex-Minor Free

An apex graph is a graph $G$ such that for some vertex $v$ (the apex), $G-v$
is planar. Let $\mathcal{H}$ be a minor-closed family of graphs. Then
$\mathcal{H}$ is an apex-minor free if and only if $\mathcal{H}$ does not
contain all apex graphs. In this section, we will design an FPT algorithm for
Fair Hitting Set when $G_{\mathcal{U},\mathcal{B}}$ belongs to an apex-minor
closed family of graphs, parameterized by $k+|\mathcal{F}|$. In Section 7.1,
we first design an FPT algorithm for Fair Hitting Set parameterized by the
treewidth of $G_{\mathcal{U},\mathcal{F}}+|\mathcal{F}|$. Note that if, in the
given instance the $(\mathcal{U},\mathcal{F})$ graph is $K_{d,d}$ free, then
we can use Theorem 8 to reduce to the case when the size $\mathcal{F}$ is
bounded by $k^{\mathcal{O}(d)}$. Then, in Section 7.2, we use the shifting
technique to reduce the treewidth of $G_{\mathcal{U},\mathcal{B}}$ to a
function of $k$, which enables us to use the result from Section 7.1 to obtain
the desired result.

###  7.1 Parameterization by
$\textup{{tw}}(G_{\mathcal{U},\mathcal{B}})+|\mathcal{F}|$

In this section, we design an FPT algorithm for an Fair Hitting Set instance
$(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$, parameterized by the treewidth of
the incidence graph $G_{\mathcal{U},\mathcal{B}}$, plus the number of sets in
$\mathcal{F}$.

For a node $t\in V(T)$, we define the following notation. Let
$\mathcal{B}(t)\coloneqq\mathcal{B}\cap\beta(t)$, and
$\mathcal{U}(t)\coloneqq\mathcal{U}\cap\beta(t)$ denote the subsets of
$\mathcal{B}$ and $\mathcal{U}$ from the bag of $t$, respectively. Similarly,
let $\mathcal{B}_{d}(t)\coloneqq\mathcal{B}\cap V(t)$, and
$\mathcal{U}_{d}(t)\coloneqq\mathcal{U}\cap V(t)$ denote the subsets of
$\mathcal{B}$ and $\mathcal{U}$ from the subtree rooted at $t$, respectively.

For a node $t\in V(T)$, we define a family of functions
$\mathcal{G^{\prime}}(t)$, such that each $g$ is a function with domain
$\mathcal{B}(t)$, and co-domain $\\{0,1,\ldots,k\\}$. Then, we define a sub-
family of _valid functions_ as follows
$\mathcal{G}(t)\coloneqq\\{g\in\mathcal{G^{\prime}}(t):g(B_{j})\leq
f(B_{j})\text{ for all }B_{j}\in\mathcal{B}(t)\\}$.

For every node $t\in V(T)$, each function $g\in\mathcal{G}(t)$, each subset
$\mathcal{F}^{\prime}\subseteq\mathcal{F}$, and
$\mathcal{U}^{\prime}\subseteq\mathcal{U}(t)$ with $|\mathcal{U}^{\prime}|\leq
k$, we define a table entry
$T[t,g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}]$, defined as the size of the
smallest $S\subseteq\mathcal{U}_{d}(t)$ with the following properties.

  1. 1.

$S$ hits $\mathcal{F}^{\prime}$, i.e., for each
$F_{i}\in\mathcal{F}^{\prime}$, $S\cap F_{i}\neq\emptyset$,

  2. 2.

For every $B_{j}\in\mathcal{B}_{d}(t)$, $|B_{j}\cap S|\leq f(B_{j})$,

  3. 3.

For every $B_{j^{\prime}}\in\mathcal{B}(t)$, $|B_{j^{\prime}}\cap
S|=g(B_{j^{\prime}})$, and

  4. 4.

$S\cap\mathcal{U}(t)=\mathcal{U}^{\prime}$.

If no such $S\subseteq\mathcal{U}_{d}(t)$ exists, then the entry is defined to
be $\infty$. We observe that for each node $t\in V(T)$, there are at most
$(2(k+1))^{\textup{{tw}}+1}\cdot 2^{|\mathcal{F}|}$ table entries.

Thus, in the following we show how to use dynamic programming to compute table
entries $T[t,g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}]$ such that (i)
$g(B_{j})\leq f(B_{j})$ for all $B_{j}\in\mathcal{B}(t)$, and (ii)
$|\mathcal{U}^{\prime}|\leq k$. Note that since we are interested in solutions
of size at most $k$, we may discard entries corresponding to partial solutions
of size larger than $k$. However, since this does not affect the computation
or the correctness, we do not perform this clean-up during the course of
algorithm for the sake of convenience. Finally, in the following we adopt the
convention that $\infty+p=\infty$ for any $p\in\mathbb{Z}\cup\\{\infty\\}$.

Leaf node. Consider a node $t\in V(T)$ without any child in $T$. Then, let
$T[t,g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}]=|\mathcal{U}^{\prime}|$ if
$|\mathcal{U}^{\prime}\cap B_{j}|\leq g(B_{j})$ for each
$B_{j}\in\mathcal{B}(t)$, and $\mathcal{U}^{\prime}$ hits
$\mathcal{F}^{\prime}$. Otherwise, we define
$T[t,g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}]=\infty$.

Introduce node.

  * •

Consider a node $t\in V(T)$ with a child $t^{\prime}\in V(T)$ such that
$\beta(t)=\beta(t^{\prime})\cup\\{u\\}$, where $u\in\mathcal{U}$. In this
case,

    * –

If $u\not\in\mathcal{U}^{\prime}$, then
$T[t,g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}]=T[t^{\prime},g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}]$.

    * –

If $u\in\mathcal{U}^{\prime}$, then
$T[t,g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}]=1+T[t,g^{\prime},\mathcal{F}^{\prime\prime},\mathcal{U}^{\prime\prime}]$,
where
$\mathcal{F}^{\prime\prime}=\mathcal{F}^{\prime}\setminus\mathcal{F}(u)$,
$\mathcal{U}^{\prime\prime}=\mathcal{U}^{\prime}\setminus\\{u\\}$, and
$g^{\prime}(B_{j})=\begin{cases}g(B_{j})&\text{ if $u\not\in B_{j}$}\\\
g(B_{j})-1&\text{ if $u\in B_{j}$}\end{cases}$

  * •

Consider a node $t\in V(T)$ with a child $t^{\prime}\in V(T)$ such that
$\beta(t)=\beta(t^{\prime})\cup\\{B_{q}\\}$, where $B_{q}\in\mathcal{B}$. In
this case,

    * –

If $|\mathcal{U}^{\prime}\cap B_{q}|>g(B_{q})$, then
$T[t,g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}]=\infty$.

    * –

If $|\mathcal{U}^{\prime}\cap B_{q}|\leq g(B_{q})$, then
$T[t,g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}]=T[t^{\prime},g^{\prime},\mathcal{F}^{\prime},\mathcal{U}^{\prime}]$,
where $g^{\prime}(B_{j})=g(B_{j})$ for all
$B_{j}\in\mathcal{B}(t)\setminus\\{B_{q}\\}$.

Forget node.

  * •

Consider a node $t\in V(T)$ with a child $t^{\prime}\in V(T)$ such that
$\beta(t)=\beta(t^{\prime})\setminus\\{u\\}$, where $u\in\mathcal{U}$. In this
case,

$T[t,g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}]=\min\Big{\\{}T[t^{\prime},g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}],\
T[t^{\prime},g^{\prime},\mathcal{F}^{\prime},\mathcal{U}^{\prime\prime}]\Big{\\}},$

where $\mathcal{U}^{\prime\prime}=\mathcal{U}^{\prime}\cup\\{u\\}$, and for
all $B_{j}\in\mathcal{B}(t^{\prime})=\mathcal{B}(t)$,
$g^{\prime}(B_{j})=\begin{cases}g(B_{j})&\text{ if $u\not\in B_{j}$}\\\
g(B_{j})+1&\text{ if $u\in B_{j}$}\end{cases}$

  * •

Consider a node $t\in V(T)$ with a child $t^{\prime}\in V(T)$ such that
$\beta(t)=\beta(t^{\prime})\setminus\\{B_{q}\\}$, where $B_{q}\in\mathcal{B}$.
In this case, let

$T[t,g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}]=\min_{g^{\prime}\in\mathcal{G}}\Big{\\{}T[t^{\prime},g^{\prime},\mathcal{F}^{\prime},\mathcal{U}^{\prime}]\Big{\\}}$

where $\mathcal{G}$ is a set of functions
$g^{\prime}:\mathcal{B}(t)\to\\{0,\ldots,k\\}$ satisfying the following two
properties: (1) $g^{\prime}(B_{j})=g(B_{j})\leq f(B_{j})$ for all
$B_{j}\in\mathcal{B}(t^{\prime})\setminus\\{B_{q}\\}$, and
$g^{\prime}(B_{q})\geq|B_{q}\cap\mathcal{U}^{\prime}|$.

Join node. Consider a node $t\in V(T)$ with two children $t_{1},t_{2}\in
V(T)$, such that $\beta(t)=\beta(t_{1})=\beta(t_{2})$. Fix an entry
$T[t,g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}]$. Before discussing how to
compute this entry, we define some notation. Let $\mathcal{F}_{\text{good}}$
be a set of pairs $(\mathcal{F}_{1},\mathcal{F}_{2})$, where
$\mathcal{F}_{1},\mathcal{F}_{2}\subseteq\mathcal{F}^{\prime}$ are sub-
familites satisfying the following two conditions: (i)
$\mathcal{F}_{1}\cup\mathcal{F}_{2}=\mathcal{F}^{\prime}$, and (ii)
$\bigcup_{u\in\mathcal{U}^{\prime}}\mathcal{F}(u)\subseteq\mathcal{F}_{1}\cap\mathcal{F}_{2}$.
Furthermore, let $\mathcal{G}_{\text{good}}$ be a set of pairs $(g_{1},g_{2})$
of functions, where $g_{1}\in\mathcal{G}(t_{1})$, and
$g_{2}\in\mathcal{G}(t_{2})$ that satisfy the following property: for every
$B_{j}\in\mathcal{B}(t)$:
$g_{1}(B_{j})+g_{2}(B_{j})=g(B_{j})+|\mathcal{U}^{\prime}\cap B_{j}|$.

$\displaystyle T[t,g,\mathcal{F}^{\prime},\mathcal{U}^{\prime}]$
$\displaystyle=\min_{\begin{subarray}{c}(\mathcal{F}_{1},\mathcal{F}_{2})\in\mathcal{F}_{\text{good}},\\\
(g_{1},g_{2})\in\mathcal{G}_{\text{good}}\end{subarray}}\Big{\\{}T[t_{1},g_{1},\mathcal{F}_{1},\mathcal{U}^{\prime}]+T[t_{2},g_{2},\mathcal{F}_{2},\mathcal{U}^{\prime}]-|\mathcal{U}^{\prime}|\Big{\\}}$
(1)

It is easy to see that each table entry can be computed in
$k^{\mathcal{O}(\textup{{tw}})}\cdot
2^{\mathcal{O}(|\mathcal{F}|)}\cdot|\mathcal{I}|^{\mathcal{O}(1)}$ time.
Finally, to compute the final answer, we examine the entries
$T[r,\cdot,\mathcal{F}^{\prime},\cdot]$ corresponding to the root bag $r\in
V(T)$ such that $\mathcal{F}^{\prime}=\mathcal{F}$, i.e., the partial solution
hits all sets in $\mathcal{F}$. If any such entry is a finite integer that is
at most $k$, we conclude that the given instance admits a solution of size at
most $k$. Otherwise, if each such entry is either infinite, or is an integer
larger than $k$, then we conclude that there is no solution of size at most
$k$, i.e., that the given instance is a no-instance. Thus, we conclude with
the following theorem.

######  Theorem 9.

Given an instance $\mathcal{I}=(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$, and
a nice tree-decomposition of the incidence graph $G_{\mathcal{U},\mathcal{B}}$
of width tw, there exists an $k^{\mathcal{O}(\textup{{tw}})}\cdot
2^{\mathcal{O}(|\mathcal{F}|)}\cdot|\mathcal{I}|^{\mathcal{O}(1)}$ time
algorithm to decide whether $\mathcal{I}$ is a yes-instance of Fair Hitting
Set.

###  7.2 The case when $G_{\mathcal{U},\mathcal{F}}$ is Apex-Minor Free

For a vertex $v$ of a graph $G$ and an integer $r\geq 0$, by $G_{v}^{r}$ we
denote the subgraph of $G$ induced by vertices within a distance at most $r$
from $v$ in $G$. We already know the dependence of treewidth on $r$ in a apex-
minor free graph from some of the following known results, e.g., [5].

######  Theorem 10.

Let $\mathcal{H}$ be a family of apex-minor free graphs, and
$G\in\mathcal{H}$. Let $v\in V(G)$ be an arbitrary vertex, and $r$ be a
nonnegative integer. Then $\textup{{tw}}(G_{v}^{r})\leq g(r)$, for some
function $g$. Moreover, decomposition of $G_{v}^{r}$ of width at most $g(r)$
can be constructed in polynomial time.

By theorem 10, we have the following corollary, the proof of which is
analogous to the proof of Corollary 7.34 in [3].

######  Corollary 1.

Let $v$ be a vertex of an apex-minor free graph $G$, and $i\geq 0$. Let
$L_{i}$ be the set of vertices of $G$ that are at distance exactly $i$ from
$v$. Then for any $i,j\geq 1$, the treewidth of the subgraph
$G_{i,i+j-1}=G[L_{i}\cup L_{i+1}\cup\ldots\cup L_{i+j-1}]$ does not exceed
$g(r)$. Moreover, a tree decomposition of $G_{i,i+j-1}$ of width at most
$g(r)$ can be computed in polynomial time.

We now consider an instance
$\mathcal{I}=(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ of a Fair Hitting Set
such that $G=G_{\mathcal{U},\mathcal{B}}\in\mathcal{H}$. We will design an FPT
algorithm for this case.

######  Definition 6.

A partition $\mathcal{P}=\\{\mathcal{U}_{1},\ldots,\mathcal{U}_{\ell}\\}$ of
$\mathcal{U}$ in $G=G_{\mathcal{U},\mathcal{B}}$ is called a $g$-_treewidth
bounded partition_ of $\mathcal{U}$ , if for given an integer $k\geq 0$ and
some function $g$ it satisfies the following property: for any $i\in[k+1]$,
the graph $G[(\mathcal{U}\setminus\mathcal{U}_{i})\cup\mathcal{B}]$ has
treewidth at most $g(k)$.

We now prove the following result.

######  Lemma 7.

Let $\mathcal{H}$ be an apex-minor closed family, and let $G\in\mathcal{H}$,
then there exists a function $g$, such that $G$ admits a $g$-treewidth bounded
partition. Moreover, such a partition, together with the corresponding tree
decompositions of width at most $g(k)$ can be found in polynomial time.

###### Proof.

Without loss of generality, we assume that $G$ is connected – otherwise we can
apply the following procedure for each connected component, and take the union
of the corresponding $g$-treewidth bounded partitions for each connected
component.

We select an arbitrary vertex $v\in\mathcal{U}$ and run a breadth first search
(BFS) from $v$. Let $L_{1},L_{2},\ldots$ be the layers of the BFS tree.
Observe that all the odd layers contain exactly the elements of $\mathcal{U}$
and the even layers comprise of elements of $\mathcal{B}$. We partition
$\mathcal{U}=\\{\mathcal{U}_{1},\ldots,\mathcal{U}_{k+1}\\}$, where
$\mathcal{U}_{i}=\bigcup_{a\geq 0}L_{a(2k+2)+2i-1}$, for $i\geq 1$. Note that,
using the notation from the statement of Corollary 1, the graph
$G[\mathcal{U}\setminus\mathcal{U}_{i},\mathcal{B}]$ is a disjoint union of
graphs $G_{a(2k+2)+2i,(a+1)(2k+2)+2i-2}$ for $a\geq 0$ and $G_{v}^{i-1}$, for
$i>0$. Then by theorem 10 and Corollary 1, for each of these graphs we can
construct a tree decomposition of width at most $g(k)$; connecting these tree
decompositions arbitarily yields a tree decomposition of
$G[\mathcal{U}\setminus\mathcal{U}_{i},\mathcal{B}]$ of width at most $g(k)$.
Hence, partition $\left\\{\mathcal{U}_{i}\right\\}_{1\leq i\leq k+1}$ is
$g$-treewidth bounded partition of $\mathcal{U}$ in $G$. ∎

In the following theorem, we use the $g$-treewidth bounded partition of $G$ to
reduce the problem to an instance where $G_{\mathcal{U},\mathcal{B}}$
incidence graph has bounded treewidth.

######  Theorem 11.

Let $\mathcal{H}$ be a apex-minor free graph class. Let
$\mathcal{I}=(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ be an instance of Fair
Hitting Set such that $G:=G_{\mathcal{U},\mathcal{B}}\in\mathcal{H}$. Let
$\mathcal{P}=\left\\{\mathcal{U}_{1},\ldots,\mathcal{U}_{\ell}\right\\}$ be a
$g$-treewidth bounded partition of $\mathcal{U}$. Then $\mathcal{I}$ is a yes-
instance of Fair Hitting Set if and only if there exists some $j\in[k+1]$ such
that instance
$\mathcal{I}_{j}=(\mathcal{U}\setminus\mathcal{U}_{j},\mathcal{F}-\mathcal{U}_{j},\mathcal{B}-\mathcal{U}_{j},f,k)$
is a yes-instance of Fair Hitting Set.

###### Proof.

In the forward direction. Assume $X\subseteq\mathcal{U}$ is a fair hitting set
for $\mathcal{F}$. Observe $|X|\leq k$, thus for some $j\in[k+1]$, there
exists a partition set $\mathcal{U}_{j}$ such that
$X\cap\mathcal{U}_{j}=\emptyset$. Clearly,
$X\subseteq\mathcal{U}\setminus\mathcal{U}_{j}$, and note that it is a hitting
set for $\mathcal{F}^{\prime}=\mathcal{F}-\mathcal{U}_{j}$ of size at most
$k$. Also, for every
$B^{\prime}_{i}\in\mathcal{B}^{\prime}=\mathcal{B}-\mathcal{U}_{j}$, we have
$|X\cap B^{\prime}_{i}|\leq f(B_{i})$. Hence, $X$ is a fair hitting set for
$\mathcal{F}^{\prime}$.

In the reverse direction, suppose
$X\subseteq\mathcal{U}\setminus\mathcal{U}_{j}$ is a fair hitting set for
$\mathcal{F}^{\prime}$ of size at most $k$. We claim that $X$ is also a fair
hitting set for $\mathcal{F}$ of size at most $k$. Since set $X$ hits
$\mathcal{F}^{\prime}$ and there is a bijection between the elements of set
$\mathcal{F}^{\prime}$ and $\mathcal{F}$, therefore, $X$ also hits
$\mathcal{F}$. Again, since there is a bijection between the elements of
$\mathcal{B}^{\prime}$ and $\mathcal{B}$ and $f^{\prime}s$ value remain
unchanged, it follows that for every $B_{i}\in\mathcal{B}$, we have $|X\cap
B_{i}|\leq f(B_{i})$. Hence, $X$ is also a fair hitting set for $\mathcal{F}$.
∎

Thus, our algorithm uses Lemma 7 to compute a $g$-treewidth bounded partition
of $\mathcal{U}$. Note that for any $j\in[k+1]$, the treewidth of graph
$G[(\mathcal{U}\setminus\mathcal{U}_{j})\cup\mathcal{B}]$ is upper bounded by
$g(k)$. Furthermore, using Theorem 11, it follows that $\mathcal{I}$ is a yes-
instance iff there exists a $j\in[k+1]$ such that $\mathcal{I}_{j}$ is a yes-
instance of Fair Hitting Set. Thus, the algorithm uses Theorem 9 to solve each
instance $\mathcal{I}_{j}$, and if any such instance is a yes-instance, it
concludes that $\mathcal{I}$ is a yes-instance. Otherwise, the algorithm
concludes that $\mathcal{I}$ is a no-instance. Thus, we obtain the following
theorem.

######  Theorem 12.

Given an instance $\mathcal{I}=(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ such
that $G_{\mathcal{U},\mathcal{B}}$ belongs to a family of apex-minor free
graphs, and $G_{\mathcal{U},\mathcal{F}}$ is $K_{d,d}$-free, there exists an
$g(k,d)\cdot|\mathcal{I}|^{\mathcal{O}(1)}$ time algorithm to decide whether
$\mathcal{I}$ is a yes-instance of Fair Hitting Set.

######  Remark 3.

Note that if $\mathcal{H}$ is the family of planar graphs, then the function
$g(k)$ from Lemma 7 is $\mathcal{O}(k)$. Thus, in this case, the running time
of the algorithm is $k^{\mathcal{O}(k)}\cdot
2^{|\mathcal{F}|}\cdot|\mathcal{I}|^{\mathcal{O}(1)}$.

##  8 Lower Bounds

First, we observe that Hitting Set is a special case of Fair Hitting Set, when
$\mathcal{B}=\emptyset$. Thus, the problem is NP-hard, and W$[1]$-hard
parameterized by the solution size $k$.

In the following two subsections, we show two lower bound results for Fair
Hitting Set that hold in special cases of interest. First, in Section 8.1, we
show that Fair Hitting Set remains NP-hard even in a very special case. Next,
in Section 8.2, we show that Fair Hitting Set remains W$[1]$-hard, again, in a
very special case.

###  8.1 NP-hardness for a Special Case of Fair Hitting Set

In this section, we show that Fair Hitting Set remains NP-hard even in the
special case when the sets in $\mathcal{F}$ are disjoint, and each element of
the universe is contained in at most $2$ sets of $\mathcal{B}$. To this end,
we reduce from the following problem, shown to be NP-hard in [1].

Exact Rainbow Matching Input. A proper edge-colored graph $G=(V,E)$ on $n$
vertices, where each $uv\in E(G)$ is colored with a color from
$\\{1,\ldots,q\\}$. Question. Does there exist a matching $M\subseteq E(P)$
such that $M$ contains _exactly_ one edge of each color $c$, $1\leq c\leq q$?

######  Proposition 2.

(Theorem 5 from [1]) Exact Rainbow Matching is NP-complete even on $n$-vertex
properly edge-colored paths, such that the number of colors is $\Theta(n)$.
Furthermore, assuming ETH, the problem does not admit a $2^{o(n)}$ algorithm
in the same setting.

Reduction. Let $P$ be a path that is input to Fair Matching on a Path. For
$1\leq c\leq q$, let $E_{c}$ denote the set of edges colored with $c$. Note
that $\\{E_{1},E_{2},\ldots,E_{q}\\}$ is a partition of $E(P)$, and we can
assume that each $E_{c}$ is non-empty (otherwise we can immediately conclude
that it is a no-instance). Let us also assume that the vertices of the path
are numbered from left to right as $v_{1},v_{2},\ldots,v_{n}$, and
$e_{i}=v_{i}v_{i+1}\in E(P)$ for $1\leq i\leq n-1$.

Now we construct an equivalent instance of Fair Hitting Set as follows. For
each edge $e_{i}$, we add an element $u_{i}$ to the universe. Thus,
$\mathcal{U}=\\{u_{1},\ldots,u_{n-1}\\}$. For each color $1\leq c\leq q$, we
add a set $F_{c}$ that contains the elements corresponding to the edges in
$E_{c}$. For each $1\leq i\leq n-1$, we add a set $B_{i}=\\{u_{i},u_{i+1}\\}$
to $\mathcal{B}$, and set $f(B_{i})=1$ for all $B_{i}\in\mathcal{B}$. Finally,
we set $k=q$, and let $\mathcal{I}=(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$
be the resulting instance of Fair Hitting Set. Note that the sets in
$\mathcal{F}$ are disjoint, and the frequency of any element of $\mathcal{U}$
in the sets of $\mathcal{B}$ is at most two.

Equivalence. In the forward direction, suppose $P$ admits a matching
$M\subseteq E(P)$ that contains exactly one edge of each color. Then, let
$S\subseteq\mathcal{U}$ be the set of elements corresponding to the edges of
$M$. We claim that $S$ is a Fair Hitting Set for $\mathcal{F}$ of size $k=q$.
First, since $M$ contains exactly one edge of each color, $|S|=|M|=q=k$, and
it also follows that $S$ hits every set in $\mathcal{F}$. Finally, since $M$
is a matching, it does not contain two edges incident to the same vertex. It
follows that $|S\cap B_{i}|\leq 1$ for every $B_{i}\in\mathcal{B}$. This
completes the forward direction.

In the reverse direction, let $S$ be a fair hitting set for $\mathcal{F}$ of
size at most $k$, and let $M$ be the set of edges corresponding to the
elements of $S$. Since $S$ hits every set in $\mathcal{F}$, $M$ contains
exactly one edge of each color. Furthermore, since $S$ hits every set in
$\mathcal{F}$, $|S|=|\mathcal{F}|=k$, which means that $M$ contains _exactly_
one edge of each color. Finally, since $|S\cap B_{i}|\leq 1=f(B_{i})$ for
every $B_{i}\in\mathcal{B}$, it follows that $M$ does not contain two edges
incident to a particular vertex, which means that $M$ is a matching. Thus, we
conclude with the following theorem.

######  Theorem 13.

Fair Hitting Set is NP-hard, and does not admit a $2^{o(n)}$ time algorithm,
even in the following special case, when the instance
$\mathcal{I}=(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ satisfies following
properties.

  * •

The sets in $\mathcal{F}$ are pairwise disjoint,

  * •

The sets in $\mathcal{B}$ have size exactly $2$,

  * •

Each $u\in\mathcal{U}$ belongs to at most $2$ different sets of $\mathcal{B}$,

  * •

The incidence graph $G_{\mathcal{U},\mathcal{B}}$ is a path, and

  * •

$|\mathcal{B}|=n-2,|\mathcal{U}|=n-1,$ and $|\mathcal{F}|=k=\Theta(n)$.

###  8.2 $\textup{W}[1]$-hardness of Fair Hitting Set

In this section, we show that Fair Hitting Set is W[1]-hard parameterized by
$k$. This result holds when the the family $\mathcal{F}$ is disjoint, but the
sets in $\mathcal{B}$ can intersect arbitrarily.

We establish the result for the fixed-parameter intractability of Fair Hitting
Set assuming sets in $\mathcal{B}$ are arbitrary. For this, we give a
parameter-preserving reduction from the $W[1]$-complete $k$-Multicolored
Independent Set to Fair Hitting Set parameterized by $k$. In $k$-Multicolored
Independent Set, given an undirected graph $G$, an integer $k$, and
$(V_{1}\ldots,V_{k})$ a partition of $V(G)$. Decide whether $G$ has a set
$I\subseteq V(G)$ such that $|I\cap V_{i}|=1$ for every $i\in[k]$, and $G[I]$
is edgeless.

Formally, we prove the following result.

######  Theorem 14.

Fair Hitting Set is W$[1]$-hard when parameterized by $k$, assuming the sets
in $\mathcal{B}$ are arbitrary.

###### Proof.

Let $(G,k,V_{1}\ldots V_{k})$ be an instance of $k$-Multicolored Independent
Set. We construct an instance $(\mathcal{U},\mathcal{F},\mathcal{B},f,k)$ as
follows.

  * •

For every vertex $v\in V(G)$, we add an element $e(u)$ to $\mathcal{U}$.

  * •

For every $1\leq i\leq k$, we make the set $F_{i}=\\{e(u):u\in V_{i}\\}$. Also
set $\mathcal{F}:=\\{F_{1},\ldots,F_{k}\\}$.

  * •

For every edge $\\{u,v\\}\in E(G)$, we introduce a set
$V_{\\{u,v\\}}:=\\{e(u),e(v)\\}$. Set $\mathcal{B}:=\cup_{\\{u,v\\}\in
E(G)}V_{\\{u,v\\}}$ and $f(V_{\\{u,v\\}})=1$.

We claim that $G$ has an independent set with exactly one vertex from each
$V_{i}$ if and only if $\mathcal{U}$ has a fair hitting set for $\mathcal{F}$
of size $k$.

In the forward direction, suppose there is an independent set $I$ in $G$ with
$|I\cap V_{1}|=|I\cap V_{2}|=\ldots=|I\cap V_{k}|=1$ that is, one vertex from
each $V_{i}$. We show that $I$ is a fair hitting set for $\mathcal{F}$.
Clearly, $I\cap F_{i}\neq\emptyset$ for each $i\in\\{1,\ldots,k\\}$, as $I\cap
V_{i}\neq\emptyset$. Moreover, $|I\cap F_{i}|=|I\cap V_{i}|=1$ and
$|\mathcal{F}|=k$, thus, $I$ is a hitting set for $\mathcal{F}$ of size $k$.
We next claim that for every set $V_{\\{u,v\\}}\in\mathcal{B}$, $|I\cap
V_{\\{u,v\\}}|\leq f(V_{\\{u,v\\}})=1$. Assume to the contrary, that there
exists a set $V_{\\{u^{\prime},v^{\prime}\\}}\in\mathcal{B}$ such that $|I\cap
V_{\\{u^{\prime},v^{\prime}\\}}|>1$. This implies that $I$ contains both the
endpoints $u^{\prime}$ and $v^{\prime}$ of an edge, contradicts the assumption
that $I$ is an independent set in $G$.

In the reverse direction, suppose $S\subseteq\mathcal{U}$ is a fair hitting
set for $\mathcal{F}$ of size $k$. Denote by $S^{\prime}$ the set of vertices
in $G$ corresponding to the elements of $S$ in $\mathcal{U}$. First, as
$|\mathcal{F}|=k$ and $S\cap F_{i}\neq\emptyset$, for each
$i\in\\{1,\ldots,k\\}$ implies that $|S^{\prime}\cap V_{i}|=1$. We now claim
that $S^{\prime}$ forms an independent set in $G$. Suppose not, this means
there exists an edge $\\{u,v\\}\in E(G)$ such that
$|S^{\prime}\cap\\{u,v\\}|=2$. This implies that $|S\cap
V_{\\{u,v\\}}|=|S\cap\\{e(u),e(v)\\}|=2>1$, contradicting the assumption that
$|S\cap V_{\\{u,v\\}}|\leq f(V_{\\{u,v\\}})=1$, for all $\\{u,v\\}\in E(G)$. ∎

Note that it is necessary in the construction that the $B_{i}\in\mathcal{B}$
can intersect arbitrarily. Nevertheless, we observe that in the constructed
instance of Fair Hitting Set, it holds that the sets in $\mathcal{F}$ are
disjoint, and $|B_{i}|=2$ for all $B_{i}\in\mathcal{B}$, which also implies
that the graph $G_{\mathcal{U},\mathcal{B}}$ is $K_{2,2}$-free, and even
$2$-degenerate. This shows the limit of fixed-parameter tractability of Fair
Hitting Set.

## References

  * [1] S. Bandyapadhyay, F. V. Fomin, T. Inamdar, and K. Simonov, Proportionally fair matching with multiple groups, 2023.
  * [2] J. Blum, Y. Disser, A. E. Feldmann, S. Gupta, and A. Zych-Pawlewicz, On sparse hitting sets: from fair vertex cover to highway dimension, CoRR, abs/2208.14132 (2022).
  * [3] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized Algorithms, Springer, 2015\.
  * [4] R. Diestel, Graph Theory, 4th Edition, vol. 173 of Graduate texts in mathematics, Springer, 2012.
  * [5] D. Eppstein, Diameter and treewidth in minor-closed graph families, Algorithmica, 27 (2000), pp. 275–291.
  * [6] F. V. Fomin, D. Lokshtanov, F. Panolan, and S. Saurabh, Efficient computation of representative families with applications in parameterized and exact algorithms, J. ACM, 63 (2016), pp. 29:1–29:60.
  * [7] M. Grohe, S. Kreutzer, and S. Siebertz, Deciding first-order properties of nowhere dense graphs, J. ACM, 64 (2017), pp. 17:1–17:32.
  * [8] P. Jain, L. Kanesh, and P. Misra, Conflict free version of covering problems on graphs: Classical and parameterized, Theory Comput. Syst., 64 (2020), pp. 1067–1093.
  * [9] R. M. Karp, Reducibility among combinatorial problems, in Complexity of computer computations, Springer, 1972, pp. 85–103.
  * [10] D. Knop, T. Masarík, and T. Toufar, Parameterized complexity of fair vertex evaluation problems, in 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, P. Rossmanith, P. Heggernes, and J. Katoen, eds., vol. 138 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, pp. 33:1–33:16.
  * [11] L. Lin and S. Sahni, Fair edge deletion problems, IEEE Trans. Computers, 38 (1989), pp. 756–761.
  * [12] D. Lokshtanov, P. Misra, F. Panolan, and S. Saurabh, Deterministic truncation of linear matroids, ACM Trans. Algorithms, 14 (2018), pp. 14:1–14:20.
  * [13] D. Lokshtanov, F. Panolan, S. Saurabh, R. Sharma, and M. Zehavi, Covering small independent sets and separators with applications to parameterized algorithms, ACM Trans. Algorithms, 16 (2020), pp. 32:1–32:31.
  * [14] D. Marx, A parameterized view on matroid optimization problems, Theor. Comput. Sci., 410 (2009), pp. 4471–4479.
  * [15] T. Masarík and T. Toufar, Parameterized complexity of fair deletion problems, Discret. Appl. Math., 278 (2020), pp. 51–61.