dominates all the vertices in $S$, which is a subset of $T$. However, two
different optimum solutions in $R_{i}$ will induce different partitions of
$R\cup B$. To accommodate this, we define the notion of _valid tuples_. For an
integer $i\in[0,\ell]$ and a subset $S\subseteq T$, we say a tuple
$(i,\mathcal{P},S)$ is a _valid tuple_ if $\mathcal{P}$ is a refinement of
$\mathcal{P}_{0}$ and it satisfies the three properties mentioned below. Note
that these properties are the consequences of the fact that we require
$\mathcal{P}$ to be such that, for any (partial) solution $C$ with vertices
upto $r_{i}$ in the ordering of $R\setminus C_{0}$, we can have
$\mathcal{P}(C)=\mathcal{P}$ and $N(C)=S$.

  1. 1.

For any $i\in[0,\ell]$, the partition $\mathcal{P}$ restricted to any $P_{j}$,
where $j\in[\pi(i)-1]$, is the identity partition of $P_{j}$. This is because,
if on the contrary, $\mathcal{P}$ restricted to $P_{j}$ for some
$j\in[\pi(i)-1]$ is not the identity partition, it would imply that there
exists a part $P$, say, of $\mathcal{P}$ with $|P|\geq 2$ which cannot be
refined by picking vertices of $R$ in the final solution $C$ (upto
$r_{\ell}$), as $R$ is an independent set.

  2. 2.

There may be at most one vertex $r$, say, in $P_{\pi(i)}\cap R_{i}$ which is
not yet picked in $C$. This is because if two vertices
$r^{\prime},r^{\prime\prime}$ of $P_{\pi(i)}\cap R_{i}$ are not picked in $C$,
the final solution $C$ cannot induce the identity partition, since
$\\{r^{\prime}\\},\\{r^{\prime\prime}\\}\notin\mathcal{P}(C)$. Thus, since for
any $r^{\prime}\in P_{\pi(i)}\cap R_{i}\setminus\\{r\\}$, we have
$\\{r^{\prime}\\}\in\mathcal{P}(C)$, we therefore require the partition $P$ of
$\mathcal{P}$ to be a singleton set if $P\cap P_{\pi(i)}\cap
R_{i}\neq\emptyset$ and $r\notin P$. Moreover, since $(\\{r\\}\cup
P_{\pi(i)}\setminus R_{i})\in\mathcal{P}(C)$, we require that for $r\in P$,
the part $P$ must be $(\\{r\\}\cup P_{\pi(i)}\setminus
R_{i})\in\mathcal{P}(C)$.

  3. 3.

Since any (partial) solution upto $r_{i}$ does not refine any of the parts
$P_{\pi(i)+1},\ldots,P_{t}$, for every part $P\in\mathcal{P}$ that does not
intersect $P_{1}\cup P_{2}\cup\ldots\cup P_{\pi(i)}$, $P$ must be of the form
$P_{x}$, where $x\in[\pi(i)+1,t]$.

From the above three properties of how the refinements $\mathcal{P}$ of
$\mathcal{P}_{0}$ can be, we find that $\mathcal{P}$ restricted to $B$ can be
any partition on $B$ (which can be at most
$\mathcal{O}(2^{\mathcal{O}(|B|\log|B|)})$ many) and the sets
$P\in\mathcal{P}$ containing the vertex $r\in P_{\pi(i)}$ can be as many as
the number of vertices in $P_{\pi(i)}\cap R_{i}$, that is, at most $|R|$ many.
Let $\mathcal{X}$ be the collection of all the valid tuples. Then, for any
$i\in[\ell]$ and any $S\subseteq T$, the number of partitions $\mathcal{P}$
for which $(i,\mathcal{P},S)\in\mathcal{X}$ is
$\mathcal{O}(2^{\mathcal{O}(|B|\log|B|)}\cdot|R|)$.

###### Dynamic Programming.

For every valid tuple $(i,\mathcal{P},S)\in\mathcal{X}$, we define

$\texttt{opt}[i,\mathcal{P},S]$ | = | the minimum cardinality of a set $C$ that is _compatible_ with the
---|---|---
|  | valid triple $(i,\mathcal{P},S)$, i.e., $(i)\ C\subseteq R_{i}\ (ii)\ \mathcal{P}_{0}\Cap\mathcal{P}(C)=\mathcal{P}\ \&\ (iii)\ N(C)=S$.

If no such $(i,\mathcal{P},S)$-compatible set exists, then we let the value of
$\texttt{opt}[i,\mathcal{P},S]$ to be $\infty$. Moreover, any
$(i,\mathcal{P},S)$-compatible set $C$ of minimum cardinality is called a
_minimum $(i,\mathcal{P},S)$-compatible set_. The quantities
$\texttt{opt}[i,\mathcal{P},S]$ for all $(i,\mathcal{P},S)\in\mathcal{X}$ are
updated inductively. Then finally, the quantity
$\texttt{opt}[\ell,\mathcal{I}(R\cup B),T]$ gives us the required output of
the problem. To start with, we define the quantity
$\texttt{opt}[0,\mathcal{P}_{0},N(C_{0})]=|C_{0}|$ and set
$\texttt{opt}[i,\mathcal{P},S]=\infty$ for each triple
$(i,\mathcal{P},S)\in\mathcal{X}$ such that
$(i,\mathcal{P},S)\neq(0,\mathcal{P}_{0},N(C_{0}))$. Then, the value of each
$\texttt{opt}[i,\mathcal{P},S]$ updates by the following dynamic programming
formula.

$\displaystyle\texttt{opt}[i,\mathcal{P},S]=\min\begin{cases}\texttt{opt}[i-1,\mathcal{P},S],\\\
1+\min\limits_{\begin{subarray}{c}\mathcal{P}^{\prime}\Cap\mathcal{P}(r_{i})=\mathcal{P},\\\
S^{\prime}\cup
N(r_{i})=S\end{subarray}}\texttt{opt}[i-1,\mathcal{P}^{\prime},S^{\prime}].\end{cases}$
(1)

###### Proof of Correctness.

We prove by induction on $i$ that the above formula is correct. In other
words, we show that, for any $i\in[\ell]$, if the values of
$\texttt{opt}[j,\mathcal{P}^{\prime},S^{\prime}]$ are correctly calculated for
all triples $(j,\mathcal{P}^{\prime},S^{\prime})\in\mathcal{X}$ with
$j\in[0,i-1]$, then for any couple $(\mathcal{P},S)$, the above equality
holds. Before this, we prove some technical properties.

######  Claim 1.

Let $(i,\mathcal{P},S)\in\mathcal{X}$. Then, the following hold.

  * •

The triple $(i-1,\mathcal{P},S)\in\mathcal{X}$ as well. Moreover, if $C$ is a
$(i-1,\mathcal{P},S)$-compatible set, then $C$ is also a
$(i,\mathcal{P},S)$-compatible set. In particular,
$\texttt{opt}[i,\mathcal{P},S]\leq\texttt{opt}[i-1,\mathcal{P},S]$.

  * •

Let $(i-1,\mathcal{P}^{\prime},S^{\prime})\in\mathcal{X}$ such that
$\mathcal{P}^{\prime}\Cap\mathcal{P}(r_{i})=\mathcal{P}$ and $S^{\prime}\cup
N(r_{i})=S$. If $C^{\prime}$ is a
$(i-1,\mathcal{P}^{\prime},S^{\prime})$-compatible set, then
$C=C^{\prime}\cup\\{r_{i}\\}$ is a $(i,\mathcal{P},S)$-compatible set. In
particular, $\texttt{opt}[i,\mathcal{P},S]\leq
1+\texttt{opt}[i-1,\mathcal{P}^{\prime},S^{\prime}]$.

######  Proof 6.6.

We first show that $(i-1,\mathcal{P},S)\in\mathcal{X}$. So, let
$P\in\mathcal{P}$ be such that $P\cap R_{i-1}\neq\emptyset$ and $|P|\geq 2$.
It implies that $P\cap R_{i}\neq\emptyset$ as well and hence, $P\cap
P_{j}=\emptyset$ for all $j\in[0,\pi(i)-1]$ and $P\cap P_{\pi(i)}$ is
singleton. If $\pi(i-1)<\pi(i)$, then $\pi(i-1)=\pi(i)-1$ and hence, $P\cap
P_{j}=\emptyset$ for all $j\in[0,\pi(i-1)]$. In other words, $P\cap
R_{i-1}=\emptyset$, a contradiction to our assumption. Therefore, we must have
$\pi(i-1)=\pi(i)$ and thus, clearly, $(i-1,\mathcal{P},S)\in\mathcal{X}$. Now,
let $C$ is a $(i-1,\mathcal{P},S)$-compatible set. Then clearly $C$ is also a
$(i,\mathcal{P},S)$-compatible set. Then, the inequality follows immediately.

Now, we prove the second point. Let $C^{\prime}$ be a
$(i-1,\mathcal{P}^{\prime},S^{\prime})$-compatible set. Then, we have the
following.

  * •

$C=C^{\prime}\cup\\{r_{i}\\}\subset R_{i}$;

  * •

$\mathcal{P}_{0}\Cap\mathcal{P}(C)=\mathcal{P}_{0}\Cap\mathcal{P}(C^{\prime})\Cap\mathcal{P}(r_{i})=\mathcal{P}^{\prime}\cap\mathcal{P}(r_{i})=\mathcal{P}$;
and

  * •

$N(C)=N(C^{\prime})\cup N(r_{i})=S^{\prime}\cup N(r_{i})=S$.

This implies that the set $C$ is a $(i,\mathcal{P},S)$-compatible set. Now, if
$\texttt{opt}[i-1,\mathcal{P}^{\prime},S^{\prime}]=\infty$, then, clearly,
$\texttt{opt}[i,\mathcal{P},S]\leq
1+\infty=1+\texttt{opt}[i-1,\mathcal{P},S]$. Lastly, if
$\texttt{opt}[i-1,\mathcal{P}^{\prime},S^{\prime}]<\infty$ and $C^{\prime}$ is
a minimum $(i-1,\mathcal{P}^{\prime},S^{\prime})$-compatible set, since $C$ is
$(i,\mathcal{P},S)$-compatible, we have
$\texttt{opt}[i,\mathcal{P},S]\leq|C|=1+|C^{\prime}|=1+\texttt{opt}[i-1,\mathcal{P}^{\prime},S^{\prime}]$.

We now prove by induction on $i$ that Equation (1) is correct. In other words,
we show that, for any $i\in[\ell]$, if the values of
$\texttt{opt}[j,\mathcal{P}^{\prime},S^{\prime}]$ are correctly calculated for
all triples $(j,\mathcal{P}^{\prime},S^{\prime})\in\mathcal{X}$ with
$j\in[0,i-1]$, then for any couple $(\mathcal{P},S)$, the above equality
holds. Let us therefore assume that, for all triples
$(j,\mathcal{P}^{\prime},S^{\prime})$ with $j\in[0,i-1]$, the values of
$\texttt{opt}[j,\mathcal{P}^{\prime},S^{\prime}]$ are correctly calculated.

To begin with, we show that if no $(i,\mathcal{P},S)$-compatible set exists,
then Equation (1) must compute $\infty$ as the value of
$\texttt{opt}[i,\mathcal{P},S]$. In other words, we prove that the value of
the RHS in Equation (1) is $\infty$. On the contrary, if
$\texttt{opt}[i-1,\mathcal{P},S]<\infty$, then there exists a
$(i-1,\mathcal{P},S)$-compatible set $C$ which, by Claim 1(1), is a
$(i,\mathcal{P},S)$-compatible set. This contradicts our assumption in this
case and therefore, $\texttt{opt}[i-1,\mathcal{P},S]=\infty$. Similarly, if we
assume that $\texttt{opt}[i-1,\mathcal{P}^{\prime},S^{\prime}]<\infty$ for
some refinement $\mathcal{P}^{\prime}$ of $\mathcal{P}_{0}$ and some subset
$S^{\prime}$ of $T$ such that
$\mathcal{P}^{\prime}\Cap\mathcal{P}(r_{i})=\mathcal{P}$ and $S^{\prime}\cup
N(r_{i})=S$, then there exists a
$(i-1,\mathcal{P}^{\prime},S^{\prime})$-compatible set $C^{\prime}$.
Therefore, by Claim 1(2), the set $C=C^{\prime}\cup\\{r_{i}\\}$ a
$(i,\mathcal{P},S)$-compatible set. This again implies a contradiction to our
assumption in this case and therefore,
$\texttt{opt}[i-1,\mathcal{P}^{\prime},S^{\prime}]=\infty$. Hence, this proves
that RHS $=\infty$ in Equation (1).

In view of the above argument, therefore, we assume for the rest of the proof
that $\texttt{opt}[i,\mathcal{P},S]<\infty$. We then show that LHS $=$ RHS in
Equation (1). To begin with, we first show that LHS $\leq$ RHS in Equation
(1). This is true since, by Claim 1(1), we have
$\texttt{opt}[i,\mathcal{P},S]\leq\texttt{opt}[i-1,\mathcal{P},S]$ and, by
Claim 1(2), for any $(i-1,\mathcal{P}^{\prime},S^{\prime})\in\mathcal{X}$ such
that $\mathcal{P}^{\prime}\cap\mathcal{P}(r_{i})=\mathcal{P}$ and
$S^{\prime}\cup N(r_{i})=S$, we have $\texttt{opt}[i,\mathcal{P},S]\leq
1+\texttt{opt}[i-1,\mathcal{P}^{\prime},S^{\prime}]$.

We now prove the reverse, that is, the inequality LHS $\geq$ RHS in Equation
(1). Recall that $\texttt{opt}[i,\mathcal{P},S]<\infty$ and hence,
$\texttt{opt}[i,\mathcal{P},S]=|C|$ for some minimum
$(i,\mathcal{P},S)$-compatible set $C$. We consider the following two cases.

  * •

Case 1 ($r_{i}\notin C$). In this case, $C$ is a
$(i-1,\mathcal{P},S)$-compatible set which implies that RHS
$\leq\texttt{opt}[i-1,\mathcal{P},S]\leq|C|=\texttt{opt}[i,\mathcal{P},S]$.

  * •

Case 2 ($r_{i}\in C$). Let $C^{\prime}=C\setminus\\{r_{i}\\}$. Then,
$C^{\prime}$ is a $(i-1,\mathcal{P}^{\prime},S^{\prime})$-compatible set,
where $\mathcal{P}^{\prime}\cap\mathcal{P}(r_{i})=\mathcal{P}$ and
$S^{\prime}\cup N(r_{i})=S$. Therefore, we have
$\texttt{opt}[i-1,\mathcal{P}^{\prime},S^{\prime}]\leq|C^{\prime}|$ which
implies that RHS $\leq 1+\texttt{opt}[i-1,\mathcal{P}^{\prime},S^{\prime}]\leq
1+|C^{\prime}|=|C|=\texttt{opt}[i,\mathcal{P},S]$.

This proves that LHS = RHS in Equation (1) and hence the correctness of the
algorithm.

###### Running Time.

As mentioned before, given any $i\in[\ell]$ and any $S\subseteq T$, the number
of partitions $\mathcal{P}$ for which $(i,\mathcal{P},S)\in\mathcal{X}$ is
$2^{\mathcal{O}(|B|\log|B|)}\cdot|R|$. Moreover, the number of possible
subsets $S$ of $T$ is at most $2^{|T|}\in 2^{\mathcal{O}(|B|)}$. Therefore,
there are at most $|R|\cdot 2^{\mathcal{O}(|B|\log|B|)}\cdot|R|\cdot
2^{\mathcal{O}(|B|)}\in 2^{\mathcal{O}(|B|\log|B|)}\cdot|R|^{\mathcal{O}(1)}$
many states of the dynamic programming that need to be calculated. Moreover,
to calculate each such $\texttt{opt}[i,\mathcal{P},S]$, another
$2^{\mathcal{O}(|B|\log|B|)}\cdot|R|^{\mathcal{O}(1)}$ number of
$\texttt{opt}[i-1,\mathcal{P}^{\prime},S]$’s are invoked according to the
dynamic programming formula (1). As a result therefore, we obtain a total
runtime of $2^{\mathcal{O}(|B|\log|B|)}\cdot|R|^{\mathcal{O}(1)}\times
2^{\mathcal{O}(|B|\log|B|)}\cdot|R|^{\mathcal{O}(1)}$.

This completes the proof of Lemma 6.5.

###### Beyond vertex cover.

The technique designed in this subsection can in fact be used to obtain
algorithms for two related parameters. The _distance to clique_ of a graph is
the size of a smallest set of vertices that need to be removed from a graph so
that the remaining vertices form a clique. It is a dense analogue of the
vertex cover number (which can be seen as the “distance to independent set”).
The _twin-cover number_ of a graph [32] is the size of a smallest set of
vertices such that the remaining vertices is a collection of disjoint cliques,
each of them forming a set of mutual twins. The twin-cover number is at most
the vertex cover number, since the vertices not in the vertex cover form
cliques of size 1 in the remaining graph.

We can obtain running in time
$2^{\mathcal{O}(\textsf{dc}\log\textsf{dc})}\cdot n^{\mathcal{O}(1)}$ and
$2^{\mathcal{O}(\textsf{tc}\log\textsf{tc})}\cdot n^{\mathcal{O}(1)}$ , where
dc is the distance to clique of the input graph, and tc is the twin-cover
cover number of the input graph. In both cases, the arguments are essentially
the same as for vc.

For the twin-cover parameterization, let $U$ be a set of vertices of size tc
whose removal leaves a collection $\mathcal{C}$ of cliques, each forming a
twin-class. Observe that, since we have applied Reduction Rule 6.1
exhaustively, in fact every clique in $\mathcal{C}$ has size at most 2.
Moreover, recall that for any two vertices in a twin-class $S$, we need to
select any one of them in any solution, thus those vertices are put in
$C_{0}$. Note that each such selected vertex dominates its twin in $R$, which
thus is the only vertex of $R$ in its part of $\mathcal{Q}$. Apart from this,
nothing changes, and we can apply Lemma 6.5 as above.

For distance to clique, $U$ is the set of vertices of size dc whose removal
leaves a clique, $R$. Since $R$ forms a clique, we do no longer immediately
obtain a bipartite graph, and thus we need a “split graph” version of Lemma
6.5, where $R$ is a clique and $B$ remains an independent set. Here, there are
some slight changes during the phase of pre-processing the partition in the
proof of Lemma 6.5, since any vertex in $C$ from $R$ dominates the whole of
$R$ and can thus potentially locate some vertex of $R$ from some vertex of
$B$. Nevertheless, after the pre-processing, as in Lemma 6.5, we obtain a
partition where every part is completely included either in $R$ or in $B$.
Then, selecting a vertex of $R$ does not distinguish any two other vertices of
$R$, and hence the algorithm is exactly the same from that point onwards.

###  6.2 A Linear Kernel Parameterized by Neighbourhood Diversity

We now show that Locating-Dominating Set admits a linear kernel when
parameterized by the neighbourhood diversity of the input graph. Recall that
the _neighbourhood diversity_ of a graph $G$ is the smallest integer $d$ such
that $G$ can be partitioned into $d$ sets of mutual twin vertices, each set
being either a clique or an independent set. It was introduced in [45] and can
be computed in linear time $O(n+m)$ using modular decomposition [18]. We show
the following, which implies Theorem 1.5(ii).

######  Lemma 6.7.

Locating-Dominating Set admits a kernelization algorithm that, given an
instance $(G,k)$ with $nd(G)=d$, computes an equivalent instance
$(G^{\prime},k^{\prime})$ with $2d$ vertices, and that runs in time
$\mathcal{O}(nm)$.

######  Proof 6.8.

We repeatedely apply Reduction Rule 6.1 until there are no sets of mutual
twins of size more than 2 in the graph. As each application takes time
$\mathcal{O}(n+m)$ (Lemma 6.2), overall this take at most time
$\mathcal{O}(n(n+m))=\mathcal{O}(nm)$. Thus, after applying the rule, there
are at most two vertices in each neighbourhood equivalence class. Since there
are at most $d$ such classes, the resulting graph has at most $2d$ vertices.
By Lemma 6.2, this produces an equivalent instance $(G^{\prime},k^{\prime})$.

######  Corollary 6.9.

Locating-Dominating Set admits an algorithm running in time
$2^{\mathcal{O}(d)}+\mathcal{O}(nm)$, where $d$ is the neighbourhood diversity
of the input graph.

######  Proof 6.10.

We first compute in time $\mathcal{O}(nm)$ the linear kernel from Theorem 6.7,
that is a graph with $n^{\prime}\leq 2d$ vertices. Then, a simple brute-force
algorithm running in time $2^{\mathcal{O}(n^{\prime})}=2^{\mathcal{O}(d)}$
completes the proof.

###  6.3 A Linear Kernel Parameterized by Feedback Edge Set

A set of edges $X$ of a graph is a feedback edge set if $G-X$ is a forest. The
minimum size of a feedback edge set is known as the feedback edge set number
(also known as the cyclomatic number) and is denoted by fes. It is well-known
that [25] if a graph $G$ has $n$ vertices, $m$ edges, and $r$ components, then
${\textsf{fes}}(G)=m-n+r$.

In this section, we show the following lemma proving Theorem 1.5(iii).

######  Lemma 6.11.

Locating-Dominating Set admits a kernelization algorithm that, given an
instance $(G,k)$ where $G$ has $n$ vertices, $m$ edges and feedback edge set
number fes, computes an equivalent instance $(G^{\prime},k^{\prime})$ with
$\mathcal{O}(\textsf{fes})$ vertices and edges, and that runs in
$\mathcal{O}(mn)$ time.

Note that the proof of Lemma 6.11 is nonconstructive, in the sense that it
shows the existence of a large (but constant) number of gadget types with
which the kernel can be constructed, however, as there are far too many
gadgets, we do not describe them individually.

To describe the kernelization algorithm, we first need to describe graphs of
given feedback edge set number. A graph $G$ with $n$ vertices, feedback edge
set number fes, and $c$ connected components, has exactly $n+\textsf{fes}-c$
edges. The following is a classic description of such graphs.

######  Proposition 6.12 ([41, Observation 8]).

Any graph $G$ with feedback edge set number fes is obtained from a multigraph
$\widetilde{G}$ with at most $2\textsf{fes}-2$ vertices and $3\textsf{fes}-3$
edges by first subdividing edges of $\widetilde{G}$ arbitrary number of times,
and then, repeatedely attaching degree 1 vertices to the graph, and
$\widetilde{G}$ can be computed from $G$ in $\mathcal{O}(n+\textsf{fes})$
time.

By Proposition 6.12, we compute the multigraph $\widetilde{G}$ in
$\mathcal{O}(n+\textsf{fes})$ time, and we let $\widetilde{V}$ be the set of
vertices of $\widetilde{G}$. For every edge $v_{1}v_{2}$ of $\widetilde{G}$,
we have either:

  1. 1.

$v_{1}v_{2}$ corresponds to an edge in the original graph $G$, if $v_{1}v_{2}$
has not been subdivided when obtaining $G$ from $\widetilde{G}$ (then
$v_{1}\neq v_{2}$ since $G$ is loop-free), or

  2. 2.

$v_{1}v_{2}$ corresponds to a component $C$ of the original graph $G$ with
$\\{v_{1},v_{2}\\}$ removed. Moreover, $C$ induces a tree, with two (not
necessarily distinct) vertices $c_{1},c_{2}$ in $C$, where $c_{1}$ is the only
vertex of $C$ adjacent to $v_{1}$ and $c_{2}$ is the only vertex of $C$
adjacent to $v_{2}$ in $G$. (Possibly, $v_{1}=v_{2}$ and the edge $v_{1}v_{2}$
is a loop of $\widetilde{G}$.)

To avoid dealing with the case of loops, for every component $C$ of
$G\setminus\\{v_{1}\\}$ with a loop at $v_{1}$ in $\widetilde{G}$ and with
$c_{1},c_{2}$ defined as above, we select an arbitrary vertex $x$ of the
unique path between $c_{1}$ and $c_{2}$ in $G[C]$ and add $x$ to
$\widetilde{V}$. As there can be at most fes such loops in $\widetilde{G}$, we
can assume that $\widetilde{G}$ is a multigraph with at most $3\textsf{fes}-2$
vertices and $4\textsf{fes}-3$ edges, and no loops.

We may assume that the multigraph $\widetilde{G}$ computed in Proposition 6.12
has at most $3\textsf{fes}-2$ vertices and $4\textsf{fes}-3$ edges, and no
loops.

The kernelization algorithm can be described in two steps. First, we need to
handle _hanging trees_ , that is, parts of the graph that induce trees and are
connected to the rest of the graph via a single edge. Those correspond to the
iterated addition of degree 1 vertices to the graph from $\widetilde{G}$
described in Proposition 6.12.

The second step will be to deal with the subgraphs that correspond to the
edges of $\widetilde{G}$ as described above.

####  6.3.1 Handling hanging trees

It is known that there is a linear-time dynamic programming algorithm to solve
Locating-Dominating Set on trees [54] (see also [3] for a more general
algorithm for block graphs, that also solves several types of problems related
to Locating-Dominating Set). To perform such a dynamic programming, one can in
fact define the following five types of (partial) solutions. For a tree $T$
rooted at a vertex $v$, we define five types for a subset $L$ of $V(T)$ as
follows:

  * •

Type $A$: $L$ dominates all vertices of $V(T)\setminus\\{v\\}$ and any two
vertices of $V(T)\setminus(L\cup\\{v\\})$ are located.

  * •

Type $B$: $L$ is a dominating set of $T$ and any two vertices of
$V(T)\setminus(L\cup\\{v\\})$ are located;

  * •

Type $C$: $L$ is a locating-dominating set of $T$;

  * •

Type $D$: $L$ is a locating-dominating set of $T$ with $v\in L$;

  * •

Type $E$: $L$ is a locating-dominating set of $T$ such that $v\in L$ and there
is no vertex $w$ of $T$ with $N(w)\cap L=\\{v\\}$;

Next, for convenience, we consider the lexicographic ordering $A<B<C<D<E$.
Note that these five types of solution are increasingly constrained (so, if
$X<X^{\prime}$, if $L$ is a solution of type $X^{\prime}$, it is also one of
type $X$). Those are the five possible behaviours of a locating-dominating set
of a supergraph $G$ of $T$, in which $v$ forms a cut-vertex of $G$.

For a tree $T$ rooted at $v$ and $X\in\\{A,B,C,D,E\\}$, we denote by
$opt_{X}(T,v)$ the minimum size of a set $L\subseteq V(T)$ of type $X$. Note
that $opt_{C}(T,v)$ is equal to the location-domination number of $T$.

######  Proposition 6.13.

There is a linear-time dynamic programming algorithm that, for any tree $T$
and root $v$, conjointly computes $opt_{X}(T,v)$ for all
$X\in\\{A,B,C,D,E\\}$.

######  Proof 6.14.

Use the same ideas as in the dynamic programming algorithms from [3, 54].

We next show that, for a given tree, the optimal values of solutions of
different types vary by at most one.

######  Lemma 6.15.

Let $T$ be a tree with vertex $v$, and let $X,X^{\prime}\in\\{A,B,C,D,E\\}$
with $X<X^{\prime}$. We have $opt_{X^{\prime}}(T,v)\leq opt_{X}(T,v)\leq
opt_{X^{\prime}}(T,v)+1$.

######  Proof 6.16.

The first inequality follows immediately by noticing that the conditions for
types $A$ to $E$ are increasingly constrained. Moreover, all types are
feasible by considering $L=V(T)$, so $opt_{X}(T,v)$ is always well-defined.
This implies that the first inequality is true.

For the second inequality, assume we have $X^{\prime}\in\\{A,B\\}$ and $L$ is
an optimal solution of type $X^{\prime}$. Then, $L\cup\\{v\\}$ is a solution
of type $E$. If $X^{\prime}\in\\{C,D\\}$, let $L$ be an optimal solution of
type $X^{\prime}$. If $v\notin L$ (then $X^{\prime}=C$), then again
$L\cup\\{v\\}$ is a solution of type $E$. If $v\in L$, possibly some (unique)
vertex $w$ of $T$ satisfies $N(w)\cap L=\\{v\\}$. Then, $L\cup\\{w\\}$ is a
solution of type $E$. Thus, $opt_{X}(T,v)\leq opt_{E}(T,v)\leq
opt_{X^{\prime}}(T,v)+1$. In all cases, we have $opt_{X}(T,v)\leq
opt_{E}(T,v)\leq opt_{X^{\prime}}(T,v)+1$, as claimed.

By Lemma 6.15, for any rooted tree $(T,v)$, the five values $opt_{X}(T,v)$
(for $X\in\\{A,B,C,D,E\\}$) differ by at most one, and we know that they
increase along with $X$: $opt_{A}(T,v)\leq opt_{B}(T,v)\leq\ldots\leq
opt_{E}(T,v)$. Hence, for any rooted tree $(T,v)$, there is one value
$X\in\\{A,B,C,D,E\\}$ where the “shift” occurs. More precisely, whenever
$X^{\prime}\leq X$, we have $opt_{X^{\prime}}(T,v)=opt_{X}(T,v)$, and whenever
$X^{\prime}>X$, we have $opt_{X^{\prime}}(T,v)=opt_{X}(T,v)+1$. Thus, we can
introduce the following definition, which partitions the set of rooted trees
according to one of five such possible behaviours.

######  Definition 6.17 (Rooted tree classes).

For $X\in\\{A,B,C,D,E\\}$, we define the class $\mathcal{T}_{X}$ as the set of
pairs $(T,v)$ such that $T$ is a tree with root $v$, and there is an integer
$k$ with $opt_{X^{\prime}}(T,v)=k$ whenever $X^{\prime}\leq X$, and
$opt_{X^{\prime}}(T,v)=k+1$ whenever $X^{\prime}>X$ (note that $k$ may differ
across the trees in $\mathcal{T}_{X}$).

Note that for the trees in $\mathcal{T}_{E}$, all five types of optimal
solutions have the same size.

It is clear by Lemma 6.15 that the set of all possible pairs $(T,v)$ where $T$
is a tree and $v$ a vertex of $T$, can be partitioned into the five classes
$\mathcal{T}_{X}$, where $X\in\\{A,B,C,D,E\\}$. Moreover, it is not difficult
to construct small rooted trees for each of these five classes. We next
provide five such small rooted trees, each in a different class.

|  $v_{A}$ |  $v_{B}$ |  $v_{C}$ |  $v_{D}$ |  $v_{E}$
---|---|---|---|---|---
| $T_{A}$ | $T_{B}$ | $T_{C}$ | $T_{D}$ | $T_{E}$
$opt_{A}$ | 0 | 1 | 2 | 1 | 3
$opt_{B}$ | 1 | 1 | 2 | 1 | 3
$opt_{C}$ | 1 | 2 | 2 | 1 | 3
$opt_{D}$ | 1 | 2 | 3 | 1 | 3
$opt_{E}$ | 1 | 2 | 3 | 2 | 3
Table 2: The five rooted tree gadgets with their values of the five $opt_{X}$
functions.

######  Definition 6.18 (Rooted tree gadgets).

For $X\in\\{A,B,C,D,E\\}$, let $(T_{X},v_{X})$ be the rooted tree of class
$\mathcal{T}_{X}$ from Table 2, and let $k_{X}=opt_{X}(T_{X},v_{X})$.

As these are very small, it is easy to check that the gadgets are indeed in
the claimed class.

For $X\in\\{A,B,C,D,E\\}$, $(T_{X},v_{X})$ belongs to the class
$\mathcal{T}_{X}$.

We are now ready to present our first reduction rule.

######  Reduction Rule 6.19.

Let $(G,k)$ be an instance of Locating-Dominating Set such that $G$ can be
obtained from a graph $G^{\prime}$ and a tree $T$, by identifying a vertex $v$
of $T$ with a vertex $w$ of $G^{\prime}$, such that $(T,v)$ is in class
$\mathcal{T}_{X}$ with $X\in\\{A,B,C,D,E\\}$, and with $opt_{X}(T,v)=t$. Then,
we remove all vertices of $T\setminus\\{v\\}$ from $G$ (this results in
$G^{\prime}$), we consider $G$ and a copy of the rooted tree gadget
$(T_{X},v_{X})$, and we identify $v_{X}$ with $v$, to obtain
$G^{\prime\prime}$. The reduced instance is $(G^{\prime\prime},k-t+k_{X})$.

######  Lemma 6.20.

For an instance $(G,k)$ of Locating-Dominating Set, Reduction Rule 6.19 can be
applied exhaustively in time $\mathcal{O}(n^{2})$, and for each application,
$(G,k)$ is a YES-instance of Locating-Dominating Set if and only if
$(G^{\prime\prime},k-t+k_{X})$ is a YES-instance of Locating-Dominating Set.

######  Proof 6.21.

To apply Reduction Rule 6.19, one can find all vertices of degree 1 in $G$,
mark them, and iteratively mark degree 1 vertices in the subgraph induced by
unmarked vertices. Note that a connected subset $S$ of marked vertices induces
a tree with a single vertex $v_{S}$ adjacent to a non-marked vertex $w$.
Moreover, at the end of the marking process, the subgraph induced by non-
marked vertices has minimum degree 2. This process can be done in
$\mathcal{O}(n^{2})$ time.

We form the set of candidate trees $T$ by taking the union $S_{w}$ of all
marked subsets that are connected to some common unmarked vertex $w$, together
with $w$. Note that all these candidate trees are vertex-disjoint. Again, this
can be done in $\mathcal{O}(n^{2})$ time. Let $(T,v)$ be such a rooted tree,
and let $G^{\prime}$ be the subgraph induced by $V(G)\setminus S_{v}$. Then,
we apply the linear-time dynamic programming algorithm of Proposition 6.13 to
$(T,v)$ to determine the class $\mathcal{T}_{X}$ to which $(T,v)$ belongs to,
for some $X\in\\{A,B,C,D,E\\}$, as well as $opt_{X}(T,v)=t$ for each
$X\in\\{A,B,C,D,E\\}$. Constructing $(G^{\prime\prime},k-t+k_{X})$ by
replacing $T$ by $T_{X}$ in $G$ can then be done in time
$\mathcal{O}(|V(T)|)$. Thus, overall applying the reduction rule to all trees
takes $\mathcal{O}(n^{2})$ time.

Now, we prove the second part of the statement. Assume we have applied
Reduction Rule 6.19 to a single tree $(T,v)$ to $G$,that $(G,k)$ is a YES-
instance of Locating-Dominating Set, and let $L$ be an optimal locating-
dominating set of $G$ of size at most $k$. Assume that $L\cap V(T)$ is of type
$X^{\prime}$ for $X^{\prime}\in\\{A,B,C,D,E\\}$ with respect to $(T,v)$.
Notice that the only interactions between the vertices in $V(T)$ and
$V(G^{\prime})$ are through the cut-vertex $v$. If $X^{\prime}\leq X$, then,
as $L$ is optimal, we have $|L\cap V(T)|=t$; if $X^{\prime}>X$, then by Lemma
6.15, we have $|L\cap V(T)|=t+1$. Now, we obtain a solution of
$G^{\prime\prime}$ from $L^{\prime}=L\cap V(G^{\prime})$ by adding an optimal
solution $S_{X^{\prime}}$ of type $X^{\prime}$ of $(T_{X},v_{X})$ to
$L^{\prime}$. This has size $k_{X}$ if $X^{\prime}\leq X$ and $k_{X}+1$ if
$X^{\prime}>X$. As $S_{X^{\prime}}$ behaves the same as $L\cap V(T)$ with
respect to $L^{\prime}$, $L$ is a valid locating-dominating set of
$G^{\prime\prime}$. Its size is either $|L|-(t+1)+k_{X}+1$ if $X^{\prime}>X$,
or $|L|-t+k_{X}$ if $X\leq X^{\prime}$, which in both cases is at most
$k-t+k_{X}$, thus $(G^{\prime\prime},k-t+k_{X})$ is a YES-instance.

The proof of the converse follows by the same argument: essentially, the trees
$(T,v)$ and $(T_{X},v_{X})$ are interchangeable.

We now use Lemma 6.20 to apply Reduction Rule 6.19 exhaustively in time
$\mathcal{O}(n^{2})$, before proceeding to the second part of the algorithm.

####  6.3.2 Handling the subgraphs corresponding to edges of $\widetilde{G}$.

To describe the second step of our kernelization algorithm, our aim is to
construct tree gadgets similar to those defined above, but with _two_
distinguished vertices. We thus extend the above terminology to this setting.
Let $(T,v_{1},v_{2})$, be a tree $T$ with two distinguished vertices
$v_{1},v_{2}$. We define types of trees as in the previous subsection. To do
so, we first define the types for each of $v_{1}$ and $v_{2}$, and then we
combine them. For $X\in\\{A,B,C,D,E\\}$, a subset $L$ of $V(T)$ is of _type
$(X,-)$ with respect to $v_{1}$_ if:

  * •

Type $(A,-)$: $L$ dominates all vertices of $V(T)\setminus\\{v_{1},v_{2}\\}$
and any two vertices of $V(T)\setminus(L\cup\\{v_{1},v_{2}\\})$ are located.

  * •

Type $(B,-)$: $L$ dominates all vertices of $V(T)\setminus\\{v_{2}\\}$ and any
two vertices of $V(T)\setminus(L\cup\\{v_{1},v_{2}\\})$ are located;

  * •

Type $(C,-)$: $L$ dominates all vertices of $V(T)\setminus\\{v_{2}\\}$ and any
two vertices of $V(T)\setminus(L\cup\\{v_{2}\\})$ are located;

  * •

Type $(D,-)$: $L$ dominates all vertices of $V(T)\setminus\\{v_{2}\\}$,
$v_{1}\in L$, and any two vertices of $V(T)\setminus(L\cup\\{v_{2}\\})$ are
located;

  * •

Type $(E,-)$: $L$ dominates all vertices of $V(T)\setminus\\{v_{2}\\}$,
$v_{1}\in L$, any two vertices of $V(T)\setminus(L\cup\\{v_{2}\\})$ are
located, and there is no vertex $w$ of $V(T)\setminus\\{v_{2}\\}$ with
$N(w)\cap L=\\{v_{1}\\}$;

Thus, the idea for a set $L$ of type $(X,-)$ with respect to $v_{1}$ is that
there are specific constraints for $v_{1}$, but no constraint for $v_{2}$ (and
the usual domination and location constraints for the other vertices). We say
that $L$ if of type $(X,Y)$ with respect to $(T,v_{1},v_{2})$ if $L$ is of
type $(X,-)$ with respect to $v_{1}$ and of type $(Y,-)$ with respect to
$v_{2}$. Thus, we have a total of 25 such possible types.

We let $opt_{X,Y}(T,v_{1},v_{2})$ be the smallest size of a subset $L$ of $T$
of type $(X,Y)$. Next, we argue that one can efficiently compute these values.

######  Proposition 6.22.

There is a linear-time dynamic programming algorithm that, for any tree $T$
and two vertices $v_{1},v_{2}$, conjointly computes $opt_{X,Y}(T,v_{1},v_{2})$
for all $X,Y\in\\{A,B,C,D,E\\}$.

######  Proof 6.23.

The dynamic programming is similar to that of Proposition 6.13. We root $T$ at
$v_{1}$. The main difference is that extra care must be taken around $v_{2}$
to only keep the solutions of type $(-,Y)$ for the subtrees that contain
$v_{2}$.

Next, similarly to Lemma 6.15, we show that for a triple $(T,v_{1},v_{2})$,
the optimal solution values for different types, may vary by at most 2.

######  Lemma 6.24.

Let $T$ be a tree with vertices $v_{1},v_{2}$ of $T$, and let
$X,X^{\prime},Y,Y^{\prime}\in\\{A,B,C,D,E\\}$ with $X\leq X^{\prime}$ and
$Y\leq Y^{\prime}$. If $X=X^{\prime}$ and $Y<Y^{\prime}$ or $X<X^{\prime}$ and
$Y=Y^{\prime}$, we have $opt_{X,Y}(T,v_{1},v_{2})\leq
opt_{X^{\prime},Y^{\prime}}(T,v_{1},v_{2})\leq opt_{X,Y}(T,v_{1},v_{2})+1$. If
$X<X^{\prime}$ and $Y<Y^{\prime}$, we have $opt_{X,Y}(T,v_{1},v_{2})\leq
opt_{X^{\prime},Y^{\prime}}(T,v_{1},v_{2})\leq opt_{X,Y}(T,v_{1},v_{2})+2$.

######  Proof 6.25.

The proof is similar to that of Lemma 6.15. As before, the lower bound is
clear since the conditions for type $(X^{\prime},Y^{\prime})$ are more
constrained that those for $(X,Y)$. For the upper bound, assume first that
$X=X^{\prime}$ or $Y=Y^{\prime}$ (without loss of generality, $Y=Y^{\prime}$).
Then, as before, given a solution $S$ of type $(X,Y)$, we can add to $S$ a
single vertex in the closed neighbourhood of $v_{1}$ to obtain a solution of
type $(E,Y)$. Similarly, if both $X<X^{\prime}$ and $Y<Y^{\prime}$, we can add
to $S$ a vertex to the closed neighbourhoods of each of $v_{1}$ and $v_{2}$
and obtain a solution of type $(E,E)$.

By Lemma 6.24, we can introduce the following definition. Note that for a
triple $(T,v_{1},v_{2})$, the minimum value of $opt_{X,Y}(T,v_{1},v_{2})$ over
all $X,Y\in\\{A,B,C,D,E\\}$ is reached for $X=Y=A$ (and the maximum, for
$X=Y=E$).

######  Definition 6.26 (Doubly rooted tree classes).

For a function $g:\\{A,B,C,D,E\\}^{2}\to\\{0,1,2\\}$, we define the class
$\mathcal{T}_{g}$ as the set of triples $(T,v_{1},v_{2})$ such that $T$ is a
tree, $v_{1},v_{2}$ are two of its vertices, and for every
$(X,Y)\in\mathcal{\\{}A,B,C,D,E\\}^{2}$, we have
$opt_{X,Y}(T,v_{1},v_{2})-opt_{A,A}(T,v_{1},v_{2})=g(X,Y)$.

Note that there are at most $3^{25}$ such classes of triples, since that is
the number of possible functions $g$. By Lemma 6.24, these classes define a
partition of all sets of triples $(T,v_{1},v_{2})$.777Some of these classes
are actually empty, since, for example, by Lemma 6.24,
$opt_{X,Y}(T,v_{1},v_{2})$ increases with $X$ and $Y$; however, an empirical
study shows that the number of nonempty classes is very large.

We next define suitable tree gadgets for the above classes of triples. As
there is a very large number of possible types of triples, we cannot give a
concrete definition of such a gadget, but rather, an existential one.

######  Definition 6.27 (Doubly-rooted tree gadgets).

For a function $g:\\{A,B,C,D,E\\}^{2}\to\\{0,1,2\\}$, let
$(T_{g},v_{X},v_{Y})$ be the smallest tree in $\mathcal{T}_{g}$ (if such a
tree exists), and let $k_{g}=opt_{A,A}(T_{g},v_{X},v_{Y})$.

We are now ready to present our second reduction rule, which replaces certain
triples $(T,v_{1},v_{2})$ by gadgets from Definition 6.27.

######  Reduction Rule 6.28.

Let $(G,k)$ be an instance of Locating-Dominating Set, with:

  * •

an induced subgraph $G^{\prime}$ of $G$ with two vertices $w_{1},w_{2}$;

  * •

a tree $T$ with two vertices $v_{1},v_{2}$ with $(T,v_{1},v_{2})$ in class
$\mathcal{T}_{g}$ with $g:\\{A,B,C,D,E\\}^{2}\to\\{0,1,2\\}$, and with
$opt_{A,A}(T,v_{1},v_{2})=t$;

  * •

$w_{1},w_{2}$ do not belong to a hanging tree of $G$;

  * •

$G$ can be obtained by taking a copy of $T$ and a copy of $G^{\prime}$ and
identifying, respectively, $v_{1}$ with $w_{1}$, and $v_{2}$ with $w_{2}$.

Then, we remove all vertices of $T\setminus\\{v_{1},v_{2}\\}$ from $G$ (that
is, we compute $G^{\prime}$), we consider $G^{\prime}$ and a copy of doubly-
rooted tree gadget $(T_{g},v_{X},v_{Y})$, and we identify $v_{X}$ with $v_{1}$
and $v_{Y}$ with $v_{2}$, to obtain $G^{\prime\prime}$. The reduced instance
is $(G^{\prime\prime},k-t+k_{g})$.

######  Lemma 6.29.

For an instance $(G,k)$ of Locating-Dominating Set, Reduction Rule 6.28 can be
applied to every tree component corresponding to an edge of $\widetilde{G}$ in
time $\mathcal{O}(n\textsf{fes})$, and $(G,k)$ is a YES-instance of Locating-
Dominating Set if and only if $(G^{\prime\prime},k-t+k_{g})$ is a YES-instance
of Locating-Dominating Set.

######  Proof 6.30.

To apply the reduction rule as stated, we compute the multigraph
$\widetilde{G}$ in time $\mathcal{O}(n+\textsf{fes})$ using Proposition 6.12;
by Observation 6.3, we can assume it has no loops and at most
$4\textsf{fes}-3$ edges. Now, for every edge $xy$ of $\widetilde{G}$, we
select the neighbour $v_{1}$ of $x$ and the neighbour $v_{2}$ of $y$ in $G$,
that lie on the $xy$-path corresponding to the edge $xy$ of $\widetilde{G}$.
The tree $(T,v_{1},v_{2})$ is the subgraph of $G$ corresponding to the edge
$xy$ of $\widetilde{G}$, and $G^{\prime}$ is the subgraph of $G$ obtained by
removing $T\setminus\\{v_{1},v_{2}\\}$ from $G$. Computing all these subgraphs
can be done in time $\mathcal{O}(n\textsf{fes})$. Computing the type
$\mathcal{T}_{g}$ of $(T,v_{1},v_{2})$ can be done in time $\mathcal{O}(|T|)$
by Proposition 6.22, so overall, the running time of this step is
$\mathcal{O}(n\textsf{fes})$.

Note that all the computed subgraphs are vertex-disjoint, we can thus now
apply Reduction Rule 6.28 in time $\mathcal{O}(|T|)$ to each tree $T$, noting
that the gadget $T_{g}$ is of constant size.

For the second part of the statement, the arguments are the same as those of
Lemma 6.20: since they belong to the same class $\mathcal{T}_{g}$, the trees
$(T,v_{1},v_{2})$ and $(T_{g},v_{X},v_{Y})$ have the same behaviour with
respect to Locating-Dominating Set and the overall solution for the graph.

####  6.3.3 Completion of the proof

By Lemma 6.20 and Lemma 6.29, we have applied Reduction Rule 6.19 and
Reduction Rule 6.28 in time
$\mathcal{O}(n^{2}+n\textsf{fes})=\mathcal{O}(mn)$. As we have started from a
graph $\widetilde{G}$ with at most $3\textsf{fes}-2$ vertices and
$4\textsf{fes}-3$ edges, and replaced each vertex of $\widetilde{G}$ by one
constant-size tree-gadget from Definition 6.18 and each edge of
$\widetilde{G}$ by one constant-size doubly-rooted tree gadget from Definition
6.27, the resulting graph has $\mathcal{O}(\textsf{fes})$ vertices and edges,
as claimed.

The algorithm running in time
$2^{\mathcal{O}(\textsf{fes})}+n^{\mathcal{O}(1)}$ follows by first computing
the kernel and then solving Locating-Dominating Set in time
$2^{\mathcal{O}(n)}=2^{\mathcal{O}(\textsf{fes})}$ on that kernel. This
completes the proof of Lemma 6.11.

##  7 Modifications for Test Cover

In this section, we present the small (but crucial) modifications required to
obtain similar results as mentioned in previous section for Test Cover. As in
this problem, one only need to ‘locate’ elements, the reductions in this case
are often simpler than the corresponding reductions for Locating-Dominating
Set to prove a conditional lower bound. We restate the problem definition for
readers’ convenience.

Test Cover Input: A set of items $U$, a collection of subsets of $U$ called
_tests_ and denoted by $\mathcal{F}$, and an integer $k$. Question: Does there
exist a collection of at most $k$ tests such that for each pair of items,
there is a test that contains exactly one of the two items? Auxiliary Graph: A
bipartite graph $G$ on $n$ vertices with bipartition $\langle R,B\rangle$ of
$V(G)$ such that sets $R$ and $B$ contain a vertex for every set in
$\mathcal{F}$ and for every item in $U$, respectively, and $r\in R$ and $b\in
B$ are adjacent if and only if the set corresponding to $r$ contains the
element corresponding to $b$.

We note that description of the auxiliary bipartite graph $G$ is sufficient to
describe the instance of Test Cover. We find it notationally cleaner to work
with encoding of the instance.

###  7.1 Incompressibility of Test Cover

In this section, we prove Thereom 1.1 for Test Cover. Our reduction is a
modification (and also a simplification) of the reduction mentioned in Section
3. We transfer the incompressibility of Red-Blue Dominating Set to Test Cover.
Once again, it is safe to assume that $G^{\prime}$ does not contain an
isolated vertex, $R^{\prime}\leq 2^{|B^{\prime}|}$, and
$k^{\prime}\leq|B^{\prime}|$.

##### Reduction

For notational convenience, instead of specify an instance of Test Cover, we
specify the auxiliary graph as mentioned in the definition. The reduction
takes as input an instance $(G^{\prime},\langle
R^{\prime},B^{\prime}\rangle,k^{\prime})$ of Red-Blue Dominating Set and
constructs an instance $(G,\langle R,B\rangle,k)$ of Test Cover. Suppose we
have $R^{\prime}=\\{r^{\prime}_{1},r^{\prime}_{2},\dots,r^{\prime}_{|R|}\\}$
and $B^{\prime}=\\{b^{\prime}_{1},b^{\prime}_{2},\dots,b^{\prime}_{|B|}\\}$.
The reduction constructs graph $G$ in the following steps. See Figure 2 for an
illustration.

Figure 7: An illustrative example of the graph constructed by the reduction.
Red (squared) nodes denote the tests whereas blue (filled circle) nodes the
elements. The adjacency across $B$ and $\texttt{bit-rep}(B)$ is same as it was
mentioned in Section 3. For brevity, we only show the edges incident on
$r_{3}$. The dotted line represents a non-edge. In this example, test
corresponding to $r_{3}$ only contains element corresponding to $b_{2}$. It is
easy to see that $r_{3}$ can only distinguish between the pair
$(b^{\circ}_{2},b^{\star}_{2})$.

  * •

It adds sets of vertices $R$ and $B$ to $G$, where $R$ contains a vertex
corresponding to each vertex in $R^{\prime}$ and $B$ contains two vertices
corresponding to each vertex in $B^{\prime}$. Formally, $R=\\{r_{i}|\
i\in[|R^{\prime}|]\\}$ and $B=\\{b^{\circ}_{i},b^{\star}_{i}|\
i\in[|B^{\prime}|]\\}$.

  * •

The reduction adds a bit representation gadget to locate set $B$. It adds
vertices such that for any pair $b^{\circ}_{j},b^{\star}_{j}$, the
supplementary vertices adjacent to them are identical.

    * –

The reduction sets $p:=\lceil\log(|B|/2)\rceil+1$ and for every $i\in[p]$, it
adds two vertices $z_{i,1}$ and $z_{i,2}$ and edge $(z_{i,1},z_{i,2})$. It
adds all $z_{i,1}$’s to $R$ and all $z_{i,2}$’s to $B$.

    * –

For every integer $j\in[|B|/2]$, let $\texttt{bit}(j)$ denote the binary
representation of $j$ using $q$ bits. Connect $b^{\circ}_{j},b^{\star}_{j}\in
B$ with $z_{i,1}$ if the $i^{th}$ bit (going from left to right) in
$\texttt{bit}(j)$ is $1$.

    * –

It add two vertices $z_{0,1}$ and $z_{0,2}$, and edge $(z_{0,1},z_{0,2})$. It
adds $z_{0,1}$ to $R$ and $z_{0,2}$ to $B$. It also makes every vertex in $B$
adjacent with $z_{0,1}$. Let $\texttt{bit-rep}(B)$ be the collection of all
the vertices in $R$ added in this step.

  * •

The reduction adds edges across $R$ and $B$ as follows: For every pair of
vertices $r^{\prime}_{i}\in R^{\prime}$ and $b^{\prime}_{j}\in B^{\prime}$,

    * –

if $r^{\prime}_{i}$ is _not_ adjacent with $b^{\prime}_{j}$ then it adds both
edges $(r_{i},b^{\circ}_{j})$ and $(r_{i},b^{\star}_{j})$ to $E(G)$, and

    * –

if $r^{\prime}_{i}$ is adjacent with $b^{\prime}_{j}$ then it adds
$(r_{i},b^{\circ}_{j})$ only, i.e., it does not add an edge with endpoints
$r_{i}$ and $b^{\star}_{j}$.

  * •

Finally, it adds an isolated blue vertex $b_{0}$.

This completes the construction of $G$. The reduction sets

$k=k^{\prime}+|\texttt{bit-
rep}(B)|=k^{\prime}+\log(|B|/2)+1=\mathcal{O}(|B|),$

and returns $(G,\langle R,B\rangle,k)$ as an instance of Test Cover.

It is easy to verify that $(G,\langle R,B\rangle,k)$ is a valid instance of
Test Cover. We present a brief overview of the proof of correctness. Suppose
$(G^{\prime},\langle R^{\prime},B^{\prime}\rangle,k^{\prime})$ is a Yes-
instance of Red-Blue Dominating Set and let set $S^{\prime}\subseteq
R^{\prime}$ be a solution. We argue that $S^{\prime}\cup\texttt{bit-rep}(B)$
is a locating-dominating set of $G$ of size at most $k$. Note that red vertex
$z_{0,1}$ ensures that all the pendant vertices that are adjacent with some
vertex in $\texttt{bit-rep}(B)$ has unique neighbour in $S$. Hence, apart from
the vertex pairs of the form $(b^{\circ}_{j},b^{\star}_{j})$, every other pair
of vertices is resolved by vertices in $\texttt{bit-rep}(B)$. Now, by the
construction of $G$, a vertex $r_{i}\in R$ resolves a pair vertices
$b_{j}^{\circ}$ and $b_{j}^{\star}$ if and only if $r^{\prime}_{i}$ and
$b^{\prime}_{j}$ are adjacent with each other. This concludes the forward
direction of the proof. In the reverse direction, note that $b_{0}$ is an
isolated blue vertex. Hence, all the red vertices in $\texttt{bit-rep}(B)$ are
forced into any solution, say $S_{1}$, as they are unique red vertices that
are adjacent with some blue vertex. Hence, by the property mentioned above, it
is easy to see that $S_{1}\setminus\texttt{bit-rep}(B)$ is a desired
dominating set in graph $G^{\prime}$. This concludes the overview.

The proof of Thereom 1.1 for Test Cover follows with identical arguments as
presented in Section 3. Recall that Red-Blue Dominating Set, parameterized by
the number of blue vertices, does not admit a polynomial kernel unless
$\NP\subseteq\coNP/poly$. See, for example, [24, Lemma $15.19$]. Moreover,
when parameterized by the number of red vertices, it does not admit a
polynomial kernel unless $\NP\subseteq\coNP/poly$. See, for example, [24,
Exercise $15.4.10$]. This, along with the arguments that are standard to
parameter preserving reductions, imply that Test Cover, parameterized by $(i)$
the number of items $|U|$ and the solution size $k$, or $(ii)$ the number of
sets $|\mathcal{F}|$ does not admit a polynomial kernel, unless
$\NP\subseteq\coNP/poly$,

###  7.2 Parameterization by the Solution Size

In this subsection, we present a reduction that is very close to the reduction
used in the proof of Theorem 1.2 to prove Theorem 1.3, restated below.

See 1.3

##### Reduction

For notational convenience, instead of specify an instance of Test Cover, we
specify the auxiliary graph as mentioned in the definition. The reduction
takes as input an instance $\psi$, with $n$ variables and $m$ clauses, of
3-SAT and returns a reduced instance $(G,\langle R,B\rangle,k)$ of Test Cover
and $k=\mathcal{O}(\log(n)+\log(m))$. The reduction constructs graph $G$ as
follows.

  * •

The reduction adds some dummy variables to ensure that $n=2^{2q}$ for some
positive integer $q$. This ensures that $r=\log_{2}(n)$ and $s=\frac{n}{r}$
both are integers. It partitions the variables of $\psi$ into $r$ many
_buckets_ $X_{1},X_{2},\dots,X_{r}$ such that each bucket contains $s$ many
variables. Let $X_{i}=\\{x_{i,j}\ |\ j\in[s]\\}$ for all $i\in[r]$.

  * •

For every $X_{i}$, the reduction constructs a set $A_{i}$ of $2^{s}$ many red
vertices, that is, $A_{i}=\\{a_{i,\ell}\mid\ell\in[2^{s}]\\}$. Each vertex in
$A_{i}$ corresponds to a unique assignment of the variables in $X_{i}$.
Moreover, let $A=\cup_{i=1}^{r}A_{i}$.

  * •

Corresponding to each $X_{i}$, let the reduction add a blue vertex $b_{i}$ and
the edges $(b_{i},a_{i,\ell})$ for all $i\in[r]$ and $\ell\in[2^{s}]$. Let
$B=\\{b_{i}\mid i\in[r]\\}$.

  * •

For every clause $C_{j}$, the reduction adds a pair of blue vertices
$c^{\circ}_{j},c^{\star}_{j}$. For a vertex $a_{i,\ell}\in A_{i}$ with
$i\in[r]$, and $\ell\in[2^{s}]$, if the assignment corresponding to vertex
$a_{i,\ell}$ satisfies the clause $C_{j}$, then the reduction adds the edge
$(a_{i,\ell},c^{\circ}_{j})$. Let $Y=\\{c^{\circ}_{j},c^{\star}_{j}\mid
j\in[m]\\}$.

  * •

The reduction adds a bit-representation gadget to locate set $C$. However, it
adds the vertices in such a way that for any pair
$c^{\circ}_{j},c^{\star}_{j}$, the supplementary vertices adjacent to them are
identical.

    * –

The reduction sets $p:=\lceil\log(|C|/2)\rceil+1$ and for every $i\in[p]$, it
adds two vertices, a red vertex $z_{i,1}$ and a blue vertex $z_{i,2}$, and
edge $(z_{i,1},z_{i,2})$.

    * –

For every integer $j\in[|C|/2]$, let $\texttt{bit}(j)$ denotes the binary
representation of $j$ using $q$ bits. Connect $c^{\circ}_{j},c^{\star}_{j}\in
C$ with $z_{i,1}$ if the $i^{th}$ bit (going from left to right) in
$\texttt{bit}(j)$ is $1$.

    * –

It add two vertices $z_{0,1}$ and $z_{0,2}$, and edge $(z_{0,1},z_{0,2})$. It
also makes every vertex in $C$ adjacent with $y_{0,1}$. Let $\texttt{bit-
rep}(C)$ be the collection of all the vertices added in this step.

  * •

The reduction adds an isolated blue vertex $b_{0}$.

Figure 8: An illustrative example of the graph constructed by the reduction.
Red (squared) nodes denote the tests whereas blue (filled circle) nodes the
elements. The adjacency across $B$ and $\texttt{bit-rep}(B)$ is same as it was
mentioned in Section 3.

This completes the construction. The reduction sets $k=r+|\texttt{bit-
rep}(C)|=\mathcal{O}(\log(n))+\mathcal{O}(\log(m))$, and returns $(G,\langle
R,B\rangle,k)$ as an instance of Test Cover.

We present a brief overview of the proof of correctness in the reverse
direction. Suppose $R^{\prime}$ is a set of tests of the graph $G$ of order at
most $k$. Since $b_{0}$ is an isolated blue vertex of $G$, it implies that the
set $R^{\prime}$ dominates and locates every pair of vertices in
$B\setminus\\{b_{0}\\}$. The blue vertices in $\texttt{bit-rep}(C)$ are
pendant vertices that are adjacent with red vertices in $\texttt{bit-rep}(C)$.
Hence, all the red vertices in $\texttt{bit-rep}(C)$ are in $R^{\prime}$. The
remaining $r$ many vertices need to locate vertices in pairs ($c^{\circ}_{j}$,
$c^{\star}_{j}$), for every $j\in[m]$, which have the same neighbourhood in
$\texttt{bit-rep}(C)$. To do so, note that the only vertices adjacent to
$c^{\circ}_{j}$ and _not_ to $c^{\star}_{j}$ are in $A_{i}$ and corresponds to
an assignment satisfying clause $C_{j}$. Hence, for every $j\in[m]$, the set
$R^{\prime}$ should contain at least one vertex $\\{a_{i,\ell}$ in order to
locate $c^{\circ}_{j}$, $c^{\star}_{j}$, where $(a_{i,\ell},c^{\circ}_{j})$ is
an edge for some $i\in[r]$ and $\ell\in[2^{s}]$. Moreover, in order to
dominate the vertices of $B$, for each $i\in[r]$, the set $R^{\prime}$ must
have a vertex from each $A_{i}$. Hence, the set $R^{\prime}$ is forced to
contain _exactly_ one vertex from each $A_{i}$. Concatenating the assignments
corresponding to each $a_{i,\ell}$ in $R^{\prime}$, we thus obtain a
satisfying assignment of $\psi$. The formal arguments for the correctness
follows very closely to the one mentioned in Subsection 4.2.

######  Proof 7.1 (Proof of Theorem 1.3).

Assume there is an algorithm $\mathcal{A}$ that, given an instance $(G,\langle
R,B\rangle,k)$ of Test Cover, runs in time
$2^{2^{o(k)}}\cdot(|U|+|\mathcal{F}|)^{\mathcal{O}(1)}$ and correctly
determines whether it is Yes-instance. Consider the following algorithm that
takes as input an instance $\psi$ of $3$-SAT and determines whether it is a
Yes-instance. It first constructs an equivalent instance $(G,\langle
R,B\rangle,k)$ of Test Cover as mentioned in this subsection. Note that such
an instance can be constructed in time

Then, it calls algorithm $\mathcal{A}$ as a subroutine and returns the same
answer. The correctness of this algorithm follows from the correctness of
algorithm $\mathcal{A}$ and the correctness of the reduction. Moreover, from
the reduction, we have $k=\mathcal{O}(\log(n)+\log(m))$. As the other steps,
including the construction of the instance of Test Cover, can be performed in
time $2^{\mathcal{O}(n/\log(n))}\cdot n^{\mathcal{O}(1)}=2^{o(n)}$, the
running time of the algorithm for $3$-SAT is
$2^{2^{o(\log(n)+\log(m))}}\cdot(|R|+|B|)^{\mathcal{O}(1)}=2^{o(n+m)}\cdot
n^{\mathcal{O}(1)}$. This, however, contradicts ETH (using the sparcification
lemma). Hence, our assumption is wrong, and Test Cover does not admit an
algorithm running in time
$2^{2^{o(k)}}\cdot(|U|+|\mathcal{F}|)^{\mathcal{O}(1)}$, unless the ETH fails.

###  7.3 Parameterization by Treewidth

####  7.3.1 Upper Bound

In this section, we provide a short sketch of the dynamic programming for Test
Cover when parameterized by the treewidth of the bipartite graph of the tests
and the items. Consider a bipartite graph $G$ of $n$ vertices with vertex
bipartition $\langle R,B\rangle$ of $V(G)$. The objective is to determine
whether there is a set of at most $k$ vertices from $R$ such that for each
pair $x,y\in B$, there is $r\in R$ such that $rx\in E(G)$ but $ry\notin E(G)$.
We assume without loss of generality that we have a nice tree decomposition
$\mathcal{T}=(T,\\{X_{t}\\}_{t\in V(T)})$ of $G$ of width at most
$2{\textsf{tw}}(G)+1$. We define $G_{t}$ as before. For every node $t\in
V(T)$, we define a subproblem
$[t,(Y,W),(\mathcal{A},\mathcal{D}),\mathcal{B}]$ such that
${\texttt{opt}}[t,(Y,W),(\mathcal{A},\mathcal{D}),\mathcal{B}]$ is the size of
an optimal solution $S\subseteq R\cap V(G_{t})$ satisfying the following
properties.

  * •

$Y=S\cap X_{t}\cap R$ and $W=N_{G_{t}}(S\setminus X_{t})\cap(B\cap X_{t})$,

  * •

$\mathcal{A}\subseteq 2^{Y}$ such that $A\in\mathcal{A}$ if and only if there
exists a (unique) $u\in(V(G_{t})\cap B)\setminus(S\cup X_{t})$ such that
$N_{G_{t}}(u)\cap S=A$,

  * •

$\mathcal{D}\subseteq 2^{Y}$ such that $A\in\mathcal{D}$ if and only if there
exists $u\in(X_{t}\cap B)\setminus S$ such that $N_{G_{t}}(u)\cap S=A$,

  * •

${\mathcal{B}}\subseteq{{(B\cap X_{t})\setminus Y}\choose{2}}\cup(((B\cap
X_{t})\setminus Y)\times\\{+\\})$ such that (i) a pair of vertices
$\\{x,y\\}\in\mathcal{B}$ if and only if $N_{G_{t}}(x)\cap S=N_{G_{t}}(y)\cap
S$, or (ii) $\\{x,+\\}\in\mathcal{B}$ if and only if there exists $y\in(B\cap
V(G_{t}))\setminus(S\cup X_{t})$ such that $N_{G_{t}}(x)\cap
S=N_{G_{t}}(y)\cap S$, and

  * •

There do not exist two vertices $y,z\in(B\cap V(G_{t}))\setminus(S\cup X_{t})$
such that $N_{G_{t}}(y)\cap S=N_{G_{t}}(z)\cap S$.

Observe that the DP-states are almost similar to that of Section 5.1. The only
difference is that the objective is to pick a smallest size subset of $R$ such
that the vertices of $B$ have to be located. We illustrate how the DP works in
leaf nodes, introduce nodes, forget nodes, and join nodes. Let $r$ be the root
node. Same as before, if we compute the values of

###### Leaf Node:

Let $t$ be a leaf node and $X_{t}=\emptyset$. Then, the following four types
of DP-states are possible. These DP-states are
$[t,(\emptyset,\emptyset),(\emptyset,\emptyset),\emptyset]$,
$[t,(\emptyset,\emptyset),(\emptyset,\\{\emptyset\\}),\emptyset]$,
$[t,(\emptyset,\emptyset),(\\{\emptyset\\},\emptyset),\emptyset]$ and
$[t,(\emptyset,\emptyset),(\\{\emptyset\\},\\{\emptyset\\}),\emptyset]$.
Observe that each of the values
$\texttt{opt}[t,(\emptyset,\emptyset),(\emptyset,\emptyset),\emptyset]$,
$\texttt{opt}[t,(\emptyset,\emptyset),(\emptyset,\\{\emptyset\\}),\emptyset]$,
$\texttt{opt}[t,(\emptyset,\emptyset),(\\{\emptyset\\},\emptyset),\emptyset]$
and
$\texttt{opt}[t,(\emptyset,\emptyset),(\\{\emptyset\\},\\{\emptyset\\}),\emptyset]$
are zero since $\emptyset$ is the only set that is a candidate solution for
each of these DP-states.

Let $t$ be an introduce/forget node and $t^{\prime}$ be its unique child in
$T$. Then, the two DP-states $[t,(Y,W),(\mathcal{A},\mathcal{D}),\mathcal{B}]$
and
$[t^{\prime},(Y^{\prime},W^{\prime}),(\mathcal{A}^{\prime},\mathcal{D}^{\prime}),\mathcal{B}^{\prime}]$
are compatible to each other if an optimal solution $S$ to the state
$[t,(Y,W),(\mathcal{A},\mathcal{D}),\mathcal{B}]$ satisfies that $S^{\prime}$
is an optimal solution to
$[t^{\prime},(Y^{\prime},W^{\prime}),(\mathcal{A}^{\prime},\mathcal{D}^{\prime}),\mathcal{B}^{\prime}]$
such that $S^{\prime}=S\cap V(G_{t^{\prime}})$.

###### Introduce Node:

Let $t$ be an introduce node such that $t^{\prime}$ is the unique child of $t$
and $X_{t}=X_{t^{\prime}}\cup\\{u\\}$. Similar as in the case of Locating-
Dominating Set, if $Y^{\prime}\neq Y$ and $Y^{\prime}\neq Y\setminus\\{u\\}$,
then the DP-states $[t,(Y,W),(\mathcal{A},\mathcal{D}),\mathcal{B}]$ and
$[t^{\prime},(Y^{\prime},W^{\prime}),(\mathcal{A}^{\prime},\mathcal{D}^{\prime}),\mathcal{B}^{\prime}]$
are not compatible to each other. Consider the set $\mathcal{C}$ of all the
DP-states
$[t^{\prime},(Y^{\prime},W^{\prime}),(\mathcal{A}^{\prime},\mathcal{D}^{\prime}),\mathcal{B}^{\prime}]$
for the node $t^{\prime}$ that are compatible to the DP-state
$[t,(Y,W),(\mathcal{A},\mathcal{D}),\mathcal{B}]$. Using arguments similar to
Section 5.1, we can prove that if $u\in R$, then

${\texttt{opt}}[t,(Y,W),(\mathcal{A},\mathcal{D}),\mathcal{B}]=1+\min\limits_{\mathcal{C}}[t^{\prime},(Y^{\prime},W^{\prime}),(\mathcal{A}^{\prime},\mathcal{D}^{\prime}),\mathcal{B}^{\prime}]$

Otherwise, if $u\in B$, then

${\texttt{opt}}[t,(Y,W),(\mathcal{A},\mathcal{D}),\mathcal{B}]=\min\limits_{\mathcal{C}}[t^{\prime},(Y^{\prime},W^{\prime}),(\mathcal{A}^{\prime},\mathcal{D}^{\prime}),\mathcal{B}^{\prime}]$

###### Forget Node:

Let $t$ be a forget node such that $t^{\prime}$ be its unique chid. Same as
before, consider the set $\mathcal{C}$ of all the DP-states that are
compatible to the DP-state $[t,(Y,W),(\mathcal{A},\mathcal{D}),\mathcal{B}]$.
Since an optimal solution to $[t,(Y,W),(\mathcal{A},\mathcal{D}),\mathcal{B}]$
is the same as an optimal solution to
$[t^{\prime},(Y^{\prime},W^{\prime}),(\mathcal{A}^{\prime},\mathcal{D}^{\prime}),\mathcal{B}]$,
we can prove in a similar way that

${\texttt{opt}}[t,(Y,W),(\mathcal{A},\mathcal{D}),\mathcal{B}]=\min\limits_{\mathcal{C}}[t^{\prime},(Y^{\prime},W^{\prime}),(\mathcal{A}^{\prime},\mathcal{D}^{\prime}),\mathcal{B}^{\prime}]$

###### Join Node:

Let $t$ be a join node with its two children $t_{1}$ and $t_{2}$. To compute
the value of ${\texttt{opt}}[t,(Y,W),(\mathcal{A},\mathcal{D}),\mathcal{B}]$,
we consider the collection of all DP-states
$[t_{1},(Y_{1},W_{1}),(\mathcal{A}_{1},\mathcal{D}_{1}),\mathcal{B}_{1}]$ and
$[t_{2},(Y_{2},W_{2}),(\mathcal{A}_{2},\mathcal{D}_{2}),\mathcal{B}_{2}]$ such
that the three above mentioned states are compatible to each other. By
arguments similar as before, we can justify that

${\texttt{opt}}[t,(Y,W),(\mathcal{A},\mathcal{D}),\mathcal{B}]$
$=\min_{\mathcal{C}}\bigg{\\{}{\texttt{opt}}[t_{1},(Y_{1},W_{1}),(\mathcal{A}_{1},\mathcal{D}_{1}),\mathcal{B}_{1}]+{\texttt{opt}}[t_{2},(Y_{2},W_{2}),(\mathcal{A}_{2},\mathcal{D}_{2}),\mathcal{B}_{2}]-|Y|\bigg{\\}}$

Finally, by similar arguments as before, we can prove that Test Cover can be
solved in time $2^{2^{\mathcal{O}(\textsf{tw})}}n^{\mathcal{O}(1)}$.

####  7.3.2 Lower Bound

In this subsection, we prove the lower bound mentioned in Theorem 1.4, i.e.,
Test Cover does not admit an algorithm running in time
$2^{2^{o(tw)}}\cdot|V(G)|^{\mathcal{O}(1)}$, unless the ETH fails. We present
a reduction which is a modification of the reduction presented in Subsection
5.2.

##### Reduction

For notational convenience, instead of specify an instance of Test Cover, we
specify the auxiliary graph as mentioned in the definition. The reduction
takes as input an instance $\psi$ of $(3,3)$-SAT with $n$ variables and
outputs an instance $(G,\langle R,B\rangle,k)$ of Test Cover such that
$\textsf{tw}(G)=\mathcal{O}(\log(n))$. Suppose $X=\\{x_{1},\dots,x_{n}\\}$ is
the collection of variables and $C=\\{C_{1},\dots,C_{m}\\}$ is the collection
of clauses in $\psi$. Here, we consider $\langle x_{1},\dots,x_{n}\rangle$ and
$\langle C_{1},\dots,C_{m}\rangle$ be arbitrary but fixed orderings of
variables and clauses in $\psi$. For a particular clause, the first order
specifies the first, second, or third (if it exists) variable in the clause in
a natural way. The second ordering specifies the first/second
positive/negative appearance of variables in $X$ in a natural way. The
reduction constructs a graph $G$ as follows after initialising
$R=B=\emptyset$.

  * •

To construct a variable gadget for $x_{i}$, it adds a blue vertex $\beta_{i}$
to $B$, two red vertices $\alpha^{1}_{i},\alpha^{2}_{i}$ to $R$, and four blue
vertices $x_{i}^{1},\neg x_{i}^{1},x_{i}^{2},\neg x_{i}^{2}$ to $B$. It then
adds the edges as shown in Figure 9. Let $A_{i}$ be the collection of these
seven vertices. Define $X_{i}:=\\{x_{i}^{1},\neg x_{i}^{1},x_{i}^{2},\neg
x_{i}^{2}\\}$.

  * •

To construct a clause gadget for $C_{j}$, the reduction adds three blue
vertices $\\{\gamma_{j}^{1},\gamma_{j}^{2},\gamma_{j}^{3}\\}$ to $B$, three
red vertices $\\{\delta_{j}^{1},\delta_{j}^{2},\delta_{j}^{3}\\}$ to $R$, and
three vertices $c^{1}_{j},c^{2}_{j},c^{3}_{j}$ to $B$. It adds the edges as
shown in Figure 9. Let $B_{j}$ be the collection of these nine vertices.

  * •

Let $p$ be the smallest positive integer such that $4n\leq\binom{2p}{p}$.
Define $\mathcal{F}_{p}$ as the collection of subsets of $[2p]$ that contains
exactly $p$ integers (such a collection $\mathcal{F}_{p}$ is called a _Sperner
family_). Define $\texttt{set-
rep}:\bigcup_{i=1}^{n}X_{i}\mapsto\mathcal{F}_{p}$ as an injective function by
arbitrarily assigning a set in $\mathcal{F}_{p}$ to a vertex $x^{\ell}_{i}$ or
$\neg x^{\ell}_{i}$, for every $i\in[n]$ and $\ell\in[2]$. In other words,
every appearance of a literal is assigned a distinct subset in
$\mathcal{F}_{p}$.

  * •

The reduction adds a _connection portal_ $V$, which is an independent set on
$2p$ red vertices $v_{1},v_{2},\dots,v_{2p}$, to $R$. For every vertex $v_{q}$
in $V$, the reduction adds a pendant blue vertex $u_{q}$ adjacent to the red
vertex $v_{q}$.

  * •

For all vertex $x_{i}^{\ell}\in X$ where $i\in[n]$ and $\ell\in[2]$, the
reduction adds edges $(x^{\ell}_{i},v_{q})$ for every $q\in\texttt{set-
rep}(x^{\ell}_{i})$. Similarly, it adds edges $(\neg x^{\ell}_{i},v_{q})$ for
every $q\in\texttt{set-rep}(\neg x^{\ell}_{i})$.

  * •

For a clause $C_{j}$, suppose variable $x_{i}$ appears positively for the
$\ell^{th}$ time as the $r^{th}$ variable in $C_{j}$. For example, $x_{i}$
appears positively for the second time as the third variable in $C_{j}$. Then,
the reduction adds edges across $B$ and $V$ such that the vertices $c_{j}^{r}$
and $x^{\ell}_{i}$ have the same neighbourhood in $V$, namely, the set
$\\{v_{q}:q\in\texttt{set-rep}(x^{\ell}_{i})\\}$. Similarly, it adds edges for
the negative appearance of the variables.

  * •

The reduction adds an isolated blue vertex $x_{0}$.

Figure 9:  An illustrative example of the graph constructed by the reduction.
Red (squared) nodes denote the tests whereas blue (filled circle) nodes the
elements. For the sake of clarity, we do not explicitly show the pendant blue
vertices adjacent to vertices in $V$. The variable and clause gadgets are on
the left-side and right-side of $V$, respectively. This is an adaptation of
the same example mentioned in Subsection 5.2. The rectangle boundary around
the red vertices denotes a solution.

This concludes the construction of $G$. The reduction sets $k=n+2m+2p$ and
returns $(G,\langle R,B\rangle,k)$ as the reduced instance of Test Cover.

We now provide an overview of the proof of correctness in the reverse
direction. The crux of the correctness is: Without loss of generality, all the
red vertices in the connection portal $V$ are present in any test cover $T$ of
$G$. Consider a blue vertex, say $x^{1}_{i}$, on ‘variable-side’ of $T$ and a
blue vertex, say $c^{1}_{j}$, on ‘clause-side’ of $T$, and suppose they have
same neighbors in the connection portal. Then, at least $x^{1}_{i}$ is
adjacent with red vertices in $T\setminus V$ or $c^{1}_{j}$ is adjacent with
red vertices in $S\setminus V$.

More formally, suppose $T$ is a test cover of $G$ of size $k=n+2m+2p$. As
every vertex in $V$ is present in $T$, we know that $T$ contains exactly one
and exactly 2 vertices from each variable gadget and clause gadget,
respectively. This is ensured by the fact that there is an isolated blue
vertex $x_{0}$, and the blue vertex $\beta_{i}$ is adjacent with only two red
vertices viz $\alpha^{1}_{i}$ and $\alpha^{2}_{i}$. Hence, at least one of
them is in $T$. Similarly, three blue vertices
$\\{\gamma_{j}^{1},\gamma_{j}^{2},\gamma_{j}^{3}\\}$ and their adjacency with
three red vertices in $\\{\delta_{j}^{1},\delta_{j}^{2},\delta_{j}^{3}\\}$,
ensures at least two vertices from the later set should be in $T$. Selecting
$\alpha^{1}_{i}$ corresponds to setting the variable to True and seleting
$\alpha^{2}_{i}$ corresponding to setting the variable to False. Also,
including $\\{\delta_{j}^{2},\delta_{j}^{3}\\}$,
$\\{\delta_{j}^{1},\delta_{j}^{3}\\}$, and
$\\{\delta_{j}^{1},\delta_{j}^{2}\\}$ in $T$, corresponding to selecting the
first, second and the third variable, respectively, to satisfy clause $C_{j}$.
As in Subsection 5.2, the connection portal and its adjacencies to variable
gadgets and clause gadgets ensures that these choices are consistent.

This establishes the correctness of the reduction. The argument regarding the
conditional lower bound is identical as in Subsection 5.2.

###  7.4 Parameterization by the Number of Elements

Red-Blue Locating Set admits a simple
$|R|^{\mathcal{O}(k)}\cdot(|R|+|B|)^{\mathcal{O}(1)}$ algorithm that
enumerates all the possible subsets of $R$ and checks it for feasibility. Our
goal is find an algorithm parameterized by $|B|$. Note that it is safe to
assume $|R|\leq 2^{|B|}$ (since we can remove twin vertices from $R$ and get
an equivalent instance) and $k\leq|B|$ by Bondy’s theorem [8] (which asserts
that Test Cover always has a solution of size at most $|B|-1$). Hence, the
brute-force algorithm mentioned above runs in time
$2^{\mathcal{O}(|B|^{2})}\cdot(|R|+|B|)^{\mathcal{O}(1)}$.

In what follows, our objective is present an improved algorithm, in the spirit
of the known $\mathcal{O}(mn2^{n})$ dynamic programming scheme for Set Cover
on a universe of size $n$ and $m$ sets (see [26, Theorem 3.10]). We next
restate the theorem.

See 1.6

To prove it, it suffices to apply Lemma 6.5. Indeed, we reduce Red-Blue
Locating Set to Annotated Red-Blue Partition Refinement. For this, note that
in a solution of Red-Blue Locating Set, either every vertex of $B$ is
dominated by the solution, or exactly one vertex of $B$ is not dominated by
the solution. Thus, we go through every possible choice of subset
$T_{L}\subseteq B$ with $|T_{L}|\in\\{|B-|-1,|B|\\}$. We let
$C_{0}=\emptyset$, and define the partition $\mathcal{Q}$ defined by taking
all vertices of $R$ as parts of size 1, and the set $B$ as the last part. Now,
it suffices to run the dynamic programming for solving Annotated Red-Blue
Partition Refinement with each fof the $|B|+1$ choices of set $T_{L}$, giving
a running time of
$2^{\mathcal{O}(|B|\log|B|)}\cdot(|R|+|B|)^{\mathcal{O}(1)}$.

##  8 Conclusion

In this article, we presented several results that advances our understanding
of the algorithmic complexity of Locating-Dominating Set and Test Cover.
Moreover, we believe the techniques used in this article can be applied to
other identification problems to obtain relatively rare conditional lower
bounds. The process of establishing such lower bounds boils down to designing
_bit-representation gadget_ and _set-representation gadget_ for the problem in
question.

Apart from the broad question of designing such lower bounds for other
identification problems, we list a few interesting problems left open by our
work. We have the $2^{2^{\mathcal{O}(k)}}$ kernel for Test Cover but the
$2^{o(k)}$ lower bound. It would be interesting to reduce this gap. Another
interesting question is whether our tight double-exponential lower bound for
Locating-Dominating Set parameterized by treewidth/treedepth can be applied to
the feedback vertex set number. We do not know whether our slightly
superexponential algorithm for Locating-Dominating Set parameterized by vertex
cover (and similarly, the algorithm for Test Cover parameterized by $|B|$) is
optimal, or whether there exists a single-exponential algorithm with respect
to vertex cover. Another open question in this direction, is whether this
algorithm, which can be extended to twin-cover, can be generalized even
further to the distance to cluster. The approach from [10, 11] gives only a
double-exponential kernel, and thus, a triple-exponential algorithm. As our
linear kernel for parameter feedback edge set is not explicit, it would be
nice to obtain a concrete kernel. For that, one should find a way to define
the gadgets explicitly. This is easy to do for the five gadgets from
Definition 6.18. However, as the number of possible gadgets from Definition
6.27 is huge, one should probably design a different kernelization algorithm.

## References

  * [1] A. Agrawal, D. Lokshtanov, S. Saurabh, and M. Zehavi.  Split contraction: The untold story.  ACM Trans. Comput. Theory, 11(3):18:1–18:22, 2019.
  * [2] Akanksha Agrawal, Lawqueen Kanesh, Saket Saurabh, and Prafullkumar Tale.  Paths to trees and cacti.  Theor. Comput. Sci., 860:98–116, 2021.  URL: https://doi.org/10.1016/j.tcs.2021.01.033, doi:10.1016/J.TCS.2021.01.033.
  * [3] Gabriela R. Argiroffo, Silvia M. Bianchi, Yanina Lucarini, and Annegret Katrin Wagler.  Linear-time algorithms for three domination-based separation problems in block graphs.  Discret. Appl. Math., 281:6–41, 2020.
  * [4] L. Babai.  On the complexity of canonical labelling of strongly regular graphs.  SIAM J. Comput., 9(1):212–216, 1980.
  * [5] Florian Barbero, Lucas Isenmann, and Jocelyn Thiebaut.  On the distance identifying set meta-problem and applications to the complexity of identifying problems on graphs.  Algorithmica, 82(8):2243–2266, 2020.
  * [6] Manu Basavaraju, Mathew C. Francis, M. S. Ramanujan, and Saket Saurabh.  Partially polynomial kernels for set cover and test cover.  SIAM J. Discret. Math., 30(3):1401–1423, 2016.
  * [7] Piotr Berman, Bhaskar DasGupta, and Ming-Yang Kao.  Tight approximability results for test set problems in bioinformatics.  J. Comput. Syst. Sci., 71(2):145–162, 2005.
  * [8] John A Bondy.  Induced subsets.  Journal of Combinatorial Theory, Series B, 12(2):201–202, 1972\.
  * [9] Koen M. J. De Bontridder, Bjarni V. Halldórsson, Magnús M. Halldórsson, Cor A. J. Hurkens, Jan Karel Lenstra, R. Ravi, and Leen Stougie.  Approximation algorithms for the test cover problem.  Math. Program., 98(1-3):477–491, 2003.
  * [10] Márcia R. Cappelle, Guilherme de C. M. Gomes, and Vinícius Fernandes dos Santos.  Parameterized algorithms for locating-dominating sets.  CoRR, abs/2011.14849, 2020.  URL: https://arxiv.org/abs/2011.14849, arXiv:2011.14849.
  * [11] Márcia R. Cappelle, Guilherme C. M. Gomes, and Vinícius Fernandes dos Santos.  Parameterized algorithms for locating-dominating sets.  In Carlos E. Ferreira, Orlando Lee, and Flávio Keidi Miyazawa, editors, Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2021, Online Event / São Paulo, Brazil, May 2021, volume 195 of Procedia Computer Science, pages 68–76. Elsevier, 2021.
  * [12] Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, and Sébastien Ratel.  Non-clashing teaching maps for balls in graphs.  CoRR, abs/2309.02876, 2023.  URL: https://doi.org/10.48550/arXiv.2309.02876, arXiv:2309.02876, doi:10.48550/ARXIV.2309.02876.
  * [13] L. S. Chandran, D. Issac, and A. Karrenbauer.  On the parameterized complexity of biclique cover and partition.  In J. Guo and D. Hermelin, editors, 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, volume 63 of LIPIcs, pages 11:1–11:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
  * [14] Emmanuel Charbit, Irène Charon, Gérard D. Cohen, Olivier Hudry, and Antoine Lobstein.  Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity.  Advances in Mathematics of Communication, 2(4):403–420, 2008.
  * [15] Irène Charon, Gérard D. Cohen, Olivier Hudry, and Antoine Lobstein.  Discriminating codes in (bipartite) planar graphs.  Eur. J. Comb., 29(5):1353–1364, 2008.
  * [16] Bogdan S. Chlebus and Sinh Hoa Nguyen.  On finding optimal discretizations for two attributes.  In Proceedings of the First International Conference on Rough Sets and Current Trends in Computing, volume 1424, pages 537–544, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg.
  * [17] C. Colbourn, P. J. Slater, and L. K. Stewart.  Locating-dominating sets in series-parallel networks.  Congressus Numerantium, 56:135–162, 1987.
  * [18] David Coudert, Guillaume Ducoffe, and Alexandru Popa.  Fully polynomial FPT algorithms for some classes of bounded clique-width graphs.  ACM Trans. Algorithms, 15(3):33:1–33:57, 2019.  doi:10.1145/3310228.
  * [19] Bruno Courcelle.  The monadic second-order logic of graphs. I. Recognizable sets of finite graphs.  Information and Computation, 85(1):12–75, 1990.
  * [20] Bruno Courcelle, Johann A. Makowsky, and Udi Rotics.  Linear time solvable optimization problems on graphs of bounded clique-width.  Theory Comput. Syst., 33(2):125–150, 2000.
  * [21] Robert Crowston, Gregory Z. Gutin, Mark Jones, Gabriele Muciaccia, and Anders Yeo.  Parameterizations of test cover with bounded test sizes.  Algorithmica, 74(1):367–384, 2016.
  * [22] Robert Crowston, Gregory Z. Gutin, Mark Jones, Saket Saurabh, and Anders Yeo.  Parameterized study of the test cover problem.  In Branislav Rovan, Vladimiro Sassone, and Peter Widmayer, editors, Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings, volume 7464 of Lecture Notes in Computer Science, pages 283–295. Springer, 2012.
  * [23] M. Cygan, M. Pilipczuk, and M. Pilipczuk.  Known algorithms for edge clique cover are probably optimal.  SIAM J. Comput., 45(1):67–83, 2016.
  * [24] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.  doi:10.1007/978-3-319-21275-3.
  * [25] Reinhard Diestel.  Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics.  Springer, 2012.  URL: https://dblp.org/rec/books/daglib/0030488.bib.
  * [26] Fedor V. Fomin and Dieter Kratsch.  Exact Exponential Algorithms.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010\.  doi:10.1007/978-3-642-16533-7.
  * [27] Fedor V Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi.  Kernelization: theory of parameterized preprocessing.  Cambridge University Press, 2019.
  * [28] Florent Foucaud.  Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes.  J. Discrete Algorithms, 31:48–68, 2015.
  * [29] Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale.  Problems in NP can admit double-exponential lower bounds when parameterized by treewidth and vertex cover.  CoRR, abs/2307.08149, 2023.  URL: https://doi.org/10.48550/arXiv.2307.08149, arXiv:2307.08149, doi:10.48550/ARXIV.2307.08149.
  * [30] Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, and Petru Valicov.  Identification, location-domination and metric dimension on interval and permutation graphs. I. bounds.  Theoretical Computer Science, 668:43–58, 2017.
  * [31] Florent Foucaud, George B Mertzios, Reza Naserasr, Aline Parreau, and Petru Valicov.  Identification, location-domination and metric dimension on interval and permutation graphs. II. algorithms and complexity.  Algorithmica, 78(3):914–944, 2017.
  * [32] Robert Ganian.  Twin-cover: Beyond vertex cover in parameterized algorithmics.  In Dániel Marx and Peter Rossmanith, editors, Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6-8, 2011. Revised Selected Papers, volume 7112 of Lecture Notes in Computer Science, pages 259–271. Springer, 2011.  doi:10.1007/978-3-642-28050-4\\_21.
  * [33] M. R. Garey and D. S. Johnson.  Computers and Intractability - A guide to NP-completeness.  W.H. Freeman and Company, 1979.
  * [34] Sylvain Gravier, Ralf Klasing, and Julien Moncel.  Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs.  Algorithmic Oper. Res., 3(1), 2008.  URL: http://journals.hil.unb.ca/index.php/AOR/article/view/2808.
  * [35] Gregory Z. Gutin, Gabriele Muciaccia, and Anders Yeo.  (non-)existence of polynomial kernels for the test cover problem.  Inf. Process. Lett., 113(4):123–126, 2013.
  * [36] Michel Habib, Christophe Paul, and Laurent Viennot.  A synthesis on partition refinement: A useful routine for strings, graphs, boolean matrices and automata.  In Proceedings of the 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS 1998), pages 25–38, Berlin, Heidelberg, 1998\. Springer-Verlag.
  * [37] A. Ian.  Combinatorics of Finite Sets.  Oxford University Press, 1987.
  * [38] Russell Impagliazzo and Ramamohan Paturi.  On the complexity of k-sat.  J. Comput. Syst. Sci., 62(2):367–375, 2001.  URL: https://doi.org/10.1006/jcss.2000.1727, doi:10.1006/JCSS.2000.1727.
  * [39] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which problems have strongly exponential complexity?  J. Comput. Syst. Sci., 63(4):512–530, 2001.  URL: https://doi.org/10.1006/jcss.2001.1774, doi:10.1006/JCSS.2001.1774.
  * [40] Bart M. P. Jansen and Astrid Pieterse.  Sparsification upper and lower bounds for graph problems and not-all-equal SAT.  Algorithmica, 79(1):3–28, 2017.  URL: https://doi.org/10.1007/s00453-016-0189-9, doi:10.1007/S00453-016-0189-9.
  * [41] Leon Kellerhals and Tomohiro Koana.  Parameterized complexity of geodetic set.  J. Graph Algorithms Appl., 26(4):401–419, 2022.
  * [42] T. Kloks.  Treewidth, Computations and Approximations.  Springer, 1994.
  * [43] T. Korhonen.  A single-exponential time 2-approximation algorithm for treewidth.  In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021), pages 184–192, 2022.
  * [44] S. Kratsch, G. Philip, and S. Ray.  Point line cover: The easy kernel is essentially tight.  ACM Trans. Algorithms, 12(3):40:1–40:16, 2016.
  * [45] Michael Lampis.  Algorithmic meta-theorems for restrictions of treewidth.  Algorithmica, 64(1):19–37, 2012.  URL: https://doi.org/10.1007/s00453-011-9554-x, doi:10.1007/S00453-011-9554-X.
  * [46] Daniel Lokshtanov, Dániel Marx, and Saket Saurabh.  Known algorithms on graphs of bounded treewidth are probably optimal.  ACM Trans. Algorithms, 14(2):13:1–13:30, 2018.
  * [47] Bernard M. E. Moret and Henry D. Shapiro.  On minimizing a set of tests.  SIAM Journal on Scientific and Statistical Computing, 6(4):983–1003, 1985.
  * [48] Tobias Müller and Jean-Sébastien Sereni.  Identifying and locating-dominating codes in (random) geometric networks.  Comb. Probab. Comput., 18(6):925–952, 2009.
  * [49] M. Pilipczuk.  Problems parameterized by treewidth tractable in single exponential time: A logical approach.  In Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings, volume 6907 of Lecture Notes in Computer Science, pages 520–531. Springer, 2011.
  * [50] N.S.V. Rao.  Computational complexity issues in operative diagnosis of graph-based systems.  IEEE Transactions on Computers, 42(4):447–457, 1993.
  * [51] Alfred Rényi.  On random generating elements of a finite boolean algebra.  Acta Scientiarum Mathematicarum Szeged, 22:75–81, 1961.
  * [52] I. Sau and U. dos Santos Souza.  Hitting forbidden induced subgraphs on bounded treewidth graphs.  Inf. Comput., 281:104812, 2021.
  * [53] Peter J. Slater.  Domination and location in acyclic graphs.  Networks, 17(1):55–64, 1987.  doi:10.1002/net.3230170105.
  * [54] Peter J. Slater.  Domination and location in acyclic graphs.  Networks, 17(1):55–64, 1987.
  * [55] Peter J. Slater.  Dominating and reference sets in a graph.  Journal of Mathematical and Physical Sciences, 22(4):445–455, 1988\.
  * [56] Jukka Suomela.  Approximability of identifying codes and locating-dominating codes.  Inf. Process. Lett., 103(1):28–33, 2007.  URL: https://doi.org/10.1016/j.ipl.2007.02.001, doi:10.1016/J.IPL.2007.02.001.
  * [57] Craig A. Tovey.  A simplified np-complete satisfiability problem.  Discret. Appl. Math., 8(1):85–89, 1984.  doi:10.1016/0166-218X(84)90081-7.
  * [58] Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith.  Dynamic programming on tree decompositions using generalised fast subset convolution.  In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009\. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 566–577. Springer, 2009.