# Structural Parameterization of Locating-Dominating Set and Test Cover

Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar, Prafullkumar Tale

► To cite this version:

Dipayan Chakraborty, Florent Foucaud, Diptapriyo Majumdar, Prafullkumar Tale. Structural Parameterization of Locating-Dominating Set and Test Cover. Proceedings of the 14th International Conference on Algorithms and Complexity (CIAC 2025), Jun 2025, Rome, Italy. pp.187-204, 10.1007/978-3-031-92932-8_13. hal-05071838

HAL Id: hal-05071838

https://hal.science/hal-05071838v1

Submitted on 21 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Structural Parameterization of
Locating-Dominating Set and Test Cover

Dipayan Chakraborty<sup>1,2,3[0000-0001-7169-7288]</sup>, Florent
Foucaud<sup>1[0000-0001-8198-693X]</sup>, Diptapriyo Majumdar<sup>4[0000-0003-2677-4648]</sup>,
and Prafullkumar Tale<sup>5[0000-0001-9753-0523]</sup>

<sup>1</sup> Université Clermont Auvergne, CNRS, Mines Saint-Étienne, Clermont Auvergne
INP, LIMOS, 63000 Clermont-Ferrand, France
{dipayan.chakraborty,florent.foucaud}@uca.fr

<sup>2</sup> Department of Mathematics and Applied Mathematics, University of
Johannesburg, Auckland Park, 2006, South Africa

<sup>3</sup> Department of Computer Science and Mathematics, Lebanese American University,
Beirut, Lebanon

<sup>4</sup> Indraprastha Institute of Information Technology Delhi, New Delhi, India

diptapriyo@iiitd.ac.in

<sup>5</sup> Indian Institute of Science Education and Research Bhopal, India

prafullkumar@iiserb.ac.in

**Abstract.** We investigate structural parameterizations for two identification problems in graphs and set systems: LOCATING-DOMINATING SET and TEST COVER. In the first problem, an input is a graph $G$ and an integer $k$, and one asks whether there is a subset $S$ of $k$ vertices such that any two distinct vertices not in $S$ are dominated by distinct subsets of $S$. In the second problem, an input is a set of items $U$, a collection of subsets $\mathcal{F}$ of $U$ called tests, and an integer $k$, and one asks whether there is a solution set $S$ of at most $k$ tests such that each pair of items belongs to a distinct subset of tests of $S$.

In a related work [ISAAC 2024], we proved that both problems admit a conditional double-exponential lower bound and a matching algorithm when parameterized by the treewidth of the input graph. We continue this line of investigation and consider parameters larger than treewidth, like vertex cover number and feedback edge set number. We design a nontrivial dynamic programming scheme for TEST COVER in "slightly super-exponential" time $2^{O(|U| \log |U|)} (|U| + |\mathcal{F}|)^{O(1)}$ in the number $|U|$ of items, and also LOCATING-DOMINATING SET in time $2^{O(\mathrm{vc} \log \mathrm{vc})} \cdot n^{O(1)}$, where $\mathrm{vc}$ is the vertex cover number and $n$ the order of the graph. Thus, the known lower bounds with respect to treewidth cannot be extended to the vertex cover number. We also show that when parameterized by the feedback edge set number, LOCATING DOMINATING SET admits a linear kernel, answering an open question from [Cappelle et al., LAGOS 2021]. Finally, we show that neither LOCATING-DOMINATING SET nor TEST COVER is likely to admit a compression algorithm returning an input with a subquadratic number of bits.

**Keywords:** Locating-Dominating Set · Test Cover · Parameterized Complexity · Structural Parameterization.
# 1 Introduction

We study two discrete identification problems, LOCATING-DOMINATING SET and TEST COVER, that are extensively studied since the 1970s. This type of problems, in which one aims at distinguishing all the elements of a discrete structure by a solution set, is popular in both combinatorics [6,26] and algorithms [5,7], and has many natural applications e.g. to network monitoring [25], or machine learning [13]. In a recent paper, Chakraborty et al. [11] revisited the parameterized complexity of LOCATING-DOMINATING SET and TEST COVER when parameterized by the solution size or the treewidth (tw) of the input graph. In the case of TEST COVER, the authors considered the treewidth of the natural auxiliary bipartite graph (which we specify later). They proved that LOCATING-DOMINATING SET and TEST COVER admit an algorithm running in time $2^{2^{O(tw)}} \cdot \text{poly}(n)$, where $n$ is the number of elements/vertices in the system/graph. More interestingly, they proved that these algorithms are tight, i.e., neither problem admits an algorithm running in time $2^{2^{O(tw)}} \cdot \text{poly}(n)$, unless the ETH fails. These results add LOCATING-DOMINATING SET and TEST COVER to the small list of NP-complete problems, recently initiated by Foucaud et al. [19], that admit a conditional double-exponential lower bound when parameterized by the treewidth. We continue this line of research and study the parameterized complexity of these problems for parameters that are larger than the treewidth. Before moving forward, we formally define the two studied problems.

## LOCATING-DOMINATING SET

**Input:** A graph $G$ on $n$ vertices and an integer $k$.

**Question:** Does there exist a locating-dominating set of size $k$ in $G$, that is, a dominating set $S$ of $G$ such that for any two different vertices $u, v \in V(G) \setminus S$, their neighbourhoods in $S$ are different, i.e., $N(u) \cap S \neq N(v) \cap S$?

## 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?

As TEST COVER is defined over set systems, to consider structural graph parameters, we define the auxiliary graph of a set system $(U, \mathcal{F})$ in the natural way: The 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 where $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 refer readers to [11] for a comprehensive overview about the motivations, applicability and known literature regarding the two problems, as we only mention the most relevant results here. LOCATING-DOMINATING SET [14] and TEST COVER [20, Problem SP6] are both NP-complete. They are also trivially FPT for the parameter solution size (see [8,9,16] or the discussion before Theorem 2 and Theorem 3 in [11]). Hence, it becomes interesting to study these
problems under more refined angles, such as kernelization, fine-grained complexity, and alternative parameterizations. Naturally, these lines of research have been pursued in the literature. TEST COVER was studied within the framework of “above/below guarantee” parameterizations in [4,15,16,21] and kernelization in [4,15,21]. These results have shown an intriguing behaviour for TEST COVER, with some nontrivial techniques being developed to solve the problem [4,16]. In the case of LOCATING-DOMINATING SET, fine-grained complexity results regarding the number of vertices and solution size were obtained in [3,8,9], and structural parameterizations of the input graph have been studied in [8,9]. In particular, it was shown there that the problem admits a linear kernel for the parameter max leaf number, however (under standard complexity assumptions) no polynomial kernel exists for the solution size, combined with either the vertex cover number or the distance to clique. They also provide a double-exponential kernel for the parameter distance to cluster.

*Our Contributions.* We extend the above results by systematically studying the fine-grained complexity and kernelization of LOCATING-DOMINATING SET and TEST COVER for the parameters number of vertices/elements/tests as well as structural parameters. Our results contribute to the complexity landscape for structural parameterizations of LOCATING-DOMINATING SET started in [8,9]. See Figure 1 for an overview of the known results for (structural) parameterizations of LOCATING-DOMINATING SET, using a Hasse diagram of standard graph parameters. Our first result is an FPT algorithm for LOCATING-DOMINATING SET parameterized by the vertex cover number (vc) of the input graph, and for TEST COVER when parameterized by the number $|U|$ of items.

**Theorem 1.** *LOCATING-DOMINATING SET admits an algorithm running in time $2^{O(\mathrm{vc}\log \mathrm{vc})} \cdot n^{O(1)}$, where $\mathrm{vc}$ is the vertex cover number of the input graph. Also, TEST COVER admits an algorithm running in time $2^{O(|U|\log|U|)} \cdot (|U| + |\mathcal{F}|)^{O(1)}$.*

The above result shows that unlike treewidth, for which we cannot expect a running time of the form $2^{2^{\alpha(\mathrm{tw})}}$ [11], if we choose vc, a parameter larger than treewidth, then we can significantly improve the running time. Moreover, we show that the above result for LOCATING-DOMINATING SET also extends to the parameters distance to clique and twin-cover number. For TEST COVER, the result is reminiscent of the known $O(2^n m n)$ dynamic programming scheme for SET COVER on a universe of size *n* and *m* sets (see [18, Theorem 3.10]), and improves upon the naive $2^{O(|U|^2)} \cdot (|U| + |\mathcal{F}|)^{O(1)}$ brute-force algorithm.

Our next result is a linear vertex kernel when feedback edge set number (fes) is considered as the parameter. It solves an open problem raised in [8,9].

**Theorem 2.** *LOCATING-DOMINATING SET admits a kernel with $O(\mathrm{fes})$ vertices and edges, where $\mathrm{fes}$ is the feedback edge set number of the input graph.*

Our final result is about the incompressibility of both problems.
**Theorem 3.** Neither LOCATING-DOMINATING SET nor TEST COVER admits a polynomial compression of size $O(n^{2-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly, where n denotes the number of vertices and the number of items and tests of the input, respectively.

The reduction used to prove Theorem 3 also provides an alternative proof that LOCATING-DOMINATING SET cannot be solved in time $2^{o(n)}$ (see [3] for an earlier proof), and thus, in time $2^{o(\text{vc})}$ (under the ETH). Hence, the bound of Theorem 1 is optimal up to a logarithmic factor. The reduction used to prove Theorem 3 also yields the following results. First, it proves that LOCATING-DOMINATING SET, parameterized by the vertex cover number of the input graph and the solution size, does not admit a polynomial kernel, unless NP $\subseteq$ coNP/poly. Our reduction is arguably a simpler argument than the one from [8,9] to obtain the latter result. Second, it implies that TEST COVER, parameterized by the number of items $|U|$ and the solution size k, does not admit a polynomial kernel, unless NP $\subseteq$ coNP/poly. Additionally, it also implies that TEST COVER, parameterized by the number $|\mathcal{F}|$ of tests, does not admit a polynomial kernel, unless NP $\subseteq$ coNP/poly. Since we can assume $k \le |\mathcal{F}|$ in any non-trivial instance, this improves upon the result in [21], that states that there is no polynomial kernel for the problem when parameterized by k alone.

*Organization.* We use the LOCATING-DOMINATING SET problem to demonstrate key technical concepts, and explain how to adapt the arguments for TEST COVER. Theorem 1 is addressed in Section 2 and Theorem 2 in Section 3. We present the reduction used to prove Theorem 3 in Section 4. Finally, we conclude the paper with some open problems in Section 5. All details and proofs missing from this article can be found in its full version [10].

## 2 Slightly Super-exponential Algorithm Parameterized by Vertex Cover

We describe an algorithm to prove Theorem 1, for LOCATING-DOMINATING SET, i.e., to prove that it admits an algorithm running in time $2^{O(\text{vc log vc})} \cdot n^{O(1)}$, where vc is the vertex cover number of the input graph. Our algorithm is based on a reduction to a dynamic programming scheme for a generalized partition refinement problem, that can also be used to TEST COVER. We start with the following reduction rule which, using a result from [22], can be shown to be applicable in polynomial time.

**Reduction Rule 4.** Let $(G, k)$ be an instance of LOCATING-DOMINATING SET. If there exist three vertices $u, v, x$ of G such that any two of $u, v, x$ are twins, then delete $x$ from G and decrease $k$ by one.

Our algorithm starts by finding a minimum vertex cover, say $U$, of G by an algorithm in time $1.2528^{\text{vc}} \cdot n^{O(1)}$ [23]. Then, $\text{vc} = |U|$. Let $R = V \setminus U$ be the corresponding independent set in G. The algorithm first applies Reduction
<figure><img src="image_2.png" /><figcaption>Fig. 1: Hasse diagram of graph parameters and associated results for LOCATING-DOMINATING SET. An edge from a lower parameter to a higher parameter indicates that the lower one is upper bounded by a function of the higher one. If the line is dashed, then the bound is exponential; otherwise, it is polynomial. Colors correspond to the known FPT complexity status with respect to the highlighted parameter: the upper half of the box represents the upper bound, and the lower half of the box represents the lower bound. By “single-exponential”, “slightly super-exponential” and “double-exponential”, we mean functions of the form $2^{O(p)}$, $2^{O(p \log p)}$ or $2^{O(p^2)}$, and $2^{2^{O(p)}}$, respectively. The parameters for which the running time is not known to be tight are thus striped. The red circle in the upper-right corner means that LOCATING-DOMINATING SET does not admit a polynomial kernel when parameterized by the marked parameter unless NP ⊆ coNP/poly; the yellow one means that a (tight) quadratic kernel exists, and the green one, that a linear kernel exists. The bold borders highlight parameters that are covered in this paper.</figcaption></figure>

Rule 4 exhaustively to reduce every twin-class to size at most 2. For simplicity, we continue to call the reduced instance of LOCATING-DOMINATING SET as (G, k).

Consider an optimal but hypothetical locating-dominating set L of G. The algorithm constructs a partial solution Y_L and, in subsequent steps, expands it
<figure><img src="image_3.png" /><figcaption>Fig. 2: An instance $(G, k)$ of LOCATING-DOMINATING SET where $U$ is a vertex cover of $G$. The dotted edge denotes that a vertex is adjacent with all the vertices in the set. For the sake of brevity, we do not show all the edges. The vertices in green ellipses are part of solution because of (i) being a part of false-twins, (ii) guessed intersection with $U$, and (iii) the requirement of solution to be a dominating set. Vertices $T_L$ are not dominated by the partial solution $Y_L$. Parts $P_1, P_2, P'_1, P'_2$, and $P''_1$ are parts of partition of $R \cup B$ induced by $Y_L$.</figcaption></figure>

to obtain $L$. The algorithm initializes $Y_L$ as follows: for all pairs $u, v$ of twins in $G$, it adds one of them in $Y_L$. Slater proved that for any set $S$ of vertices of a graph $G$ such that any two vertices in $S$ are twins, any locating-dominating set contains at least $|S| - 1$ vertices of $S$ [28]. Hence, it is safe to assume that all the vertices in $Y_L$ are present in any locating-dominating set. Next, the algorithm guesses the intersection of $L$ with $U$. Formally, it iterates over all the subsets of $U$, and for each such set, say $X_L$, it computes a locating-dominating set of appropriate size that contains all the vertices in $X_L$ and no vertex in $U \setminus X_L$. Consider a subset $X_L$ of $U$ and define $B = U \setminus X_L$ and $R' = R \setminus (N(X_L) \cup Y_L)$. As $L$ is also a dominating set, it is safe to assume that $R' \subseteq L$. The algorithm updates $Y_L$ to include $X_L \cup R'$.

At this stage, $Y_L$ dominates all the vertices in $R$. However, it may not dominate all the vertices in $B$. The remaining (to be chosen) vertices in $L$ are part of $R$ and are responsible for dominating the remaining vertices in $B$ and to locate all the vertices in $R \cup B$. See Figure 2 for an illustration. As the remaining solution, i.e., $L \setminus Y_L$, does not intersect $B$, it is safe to ignore the edges both of whose endpoints are in $B$. The vertices in $Y_L$ induce a partition of the vertices of the remaining graph, according to their neighborhood in $Y_L$. We can redefine the objective of selecting the remaining vertices in a locating-dominating set as to *refine* this partition such that each part contains exactly one vertex. Partition refinement is a classical concept in algorithms, see [22]. However in our case, the partition is not standalone, as it is induced by a solution set. To formalize this intuition, we introduce the following notation.

**Definition 1 (Partition Induced by $C$ and Refinement).** For a subset $C \subseteq V(G)$, define an equivalence relation $\sim_C$ on $V' \subseteq V(G) \setminus C$ as follows: for any pair $u, v \in V'$, $u \sim_C v$ if and only if $N(u) \cap C = N(v) \cap C$. Then, for any set $V \subseteq V(G)$, the partition of $V$ induced by $C$, denoted by $\mathcal{P}(C)$, is defined as: $\mathcal{P}(C) = \{\{c\} | c \in V \cap C\} \cup \{S | S \text{ is an equivalence class of } \sim_C \text{ defined on } V \setminus C\}$.
Moreover, for two partitions $\mathcal{P}$ and $\mathcal{Q}$ of $V$, a refinement of $\mathcal{P}$ by $\mathcal{Q}$, denoted by $\mathcal{P} \cap \mathcal{Q}$, is the partition defined as $\{P \cap Q : P \in \mathcal{P}, Q \in \mathcal{Q}\}$.

Suppose $V = V(G)$ and $\mathcal{P}$ and $\mathcal{Q}$ are two partitions of $V(G)$, then $\mathcal{P} \cap \mathcal{Q}$ is also a partition of $V(G)$. In addition, it can be checked that, if $C_1, C_2 \subseteq V(G)$, then $\mathcal{P}(C_1 \cup C_2) = \mathcal{P}(C_1) \cap \mathcal{P}(C_2)$ on any subset $V \subseteq V(G)$. We say a partition $\mathcal{P}$ is the identity partition if every part of $\mathcal{P}$ is a singleton set. This implies that a set $C \subseteq V(G)$ for any graph $G$ has the property $N(u) \cap C \neq N(v) \cap C$ for all distinct $u, v \in V(G) \setminus C$ if and only if the partition $\mathcal{P}(C)$ of $V(G)$ is the identity partition. With these definitions, we define the following auxiliary problem.

## ANNOTATED RED-BLUE PARTITION REFINEMENT

**Input:** A bipartite graph $G$ with bipartition $\langle R, B \rangle$ of $V(G)$; a partition $\mathcal{Q}$ of $R \cup B$; a collection of forced solution vertices $C_0 \subseteq R$; a collection of vertices $T_L \subseteq B$ that needs to be dominated; and an integer $\lambda$.

**Question:** Does there exist a set $C$ of size at most $\lambda$ such that $C_0 \subseteq C \subseteq R$, $C$ dominates $T_L$, and $\mathcal{Q} \cap \mathcal{P}(C)$ is the identity partition of $R \cup B$?

Suppose there is an algorithm $\mathcal{A}$ that solves ANNOTATED RED-BLUE PARTITION REFINEMENT in time $f(|B|) \cdot (|R| + |B|)^{O(1)}$. Then, there is an algorithm that solves LOCATING-DOMINATING SET in time $2^{O(\text{vc})} \cdot f(\text{vc}) \cdot n^{O(1)}$. Consider the algorithm described so far in this subsection. The algorithm then calls $\mathcal{A}$ as a subroutine with the bipartite graph $\langle R, B \rangle$ obtained from $G$, where $B = U \setminus X_L$ and $R = V \setminus U$ (notice that, since the hypothetical solution $L$ has no vertices from $B$, the edges of $G$ with both endpoints in $B$ are irrelevant to the locating property of $L$). It sets $\mathcal{Q}$ as the partition of $R \cup B$ induced by $Y_L$, $C_0 = Y_L \cap R$, $T_L = B \setminus N[Y_L]$, and $\lambda = k - |X_L|$. Note that $T_L$ is the collection of vertices that are not dominated by the partial solution $Y_L$. The correctness of the algorithm follows from the correctness of $\mathcal{A}$ and the fact that for two sets $C_1, C_2 \subseteq V(G)$, $C_1 \cup C_2$ is a locating-dominating set of $G$ if and only if $C_1 \cup C_2$ is a dominating set and $\mathcal{P}(C_1 \cup C_2) = \mathcal{P}(C_1) \cap \mathcal{P}(C_2)$ is the identity partition of $V(G)$. Hence, it suffices to prove the following lemma.

**Lemma 1.** *There is an algorithm that solves ANNOTATED RED-BLUE PARTITION REFINEMENT in time $2^{O(|B|\log|B|)} \cdot (|R| + |B|)^{O(1)}$.*

The remainder of the section is devoted to prove Lemma 1. We present the algorithm that can roughly be divided into three parts. In the first part, the algorithm processes the partition $\mathcal{Q}$ of $R \cup B$ with the goal of reaching to a refinement of partition $\mathcal{Q}$ such that every part is completely contained either in $R$ or in $B$. Then, we introduce some terms to obtain a 'set-cover' type dynamic programming. We also introduce three conditions that restrict the number of dynamic programming states we need to consider to $2^{O(|B|\log(|B|))} \cdot |R|$. Finally, we state the dynamic programming procedure.

*Pre-processing the Partition.* Consider the partition $\mathcal{P}(C_0)$ of $R \cup B$ induced by $C_0$, and define $\mathcal{P}_0 = \mathcal{Q} \cap \mathcal{P}(C_0)$. We classify the parts in $\mathcal{P}_0$ into three classes depending on whether they intersect with $R$, $B$, or both. Let $P_1, P_2, \dots, P_t$ be an
<figure><img src="image_4.png" /><figcaption>Fig. 3: Instance of the ANNOTATED RED-BLUE PARTITION REFINEMENT. Vertices in green ellipse denote set $C_0$ whereas dotted ellipse denotes vertices in $T_L$, and the partition $\mathcal{Q} = \{P_1, P_2, P'_1, P'_2, P''_1\}$. The vertices of $T_L^\circ$ are in rectangles.</figcaption></figure>

arbitrary but fixed order on the parts of $\mathcal{P}_0$ that are completely in $R$. Similarly, let $P'_1, P'_2, \dots, P'_{t'}$ be an arbitrary but fixed order on the parts that are completely in $B$. Also, let $P''_1, P''_2, \dots, P''_{t''}$ be the collection of parts that intersect $R$ as well as $B$. Formally, we have $P_j \subseteq R$ for any $j \in [t]$, $P'_{j'} \subseteq B$ for any $j' \in [t']$, and $P''_{j''} \cap R \neq \emptyset \neq P''_{j''} \cap B$ for any $j'' \in [t'']$. See Figure 3 for an illustration.

Recall that $T_L$ is the collection of vertices in $B$ that are required to be dominated. The algorithm first expands this set so that it is precisely the collection of vertices that need to be dominated by the solution $C$. In other words, at present, the required condition is $T_L \subseteq N(C)$, whereas, after the expansion, the condition is $T_L = N(C)$. Towards this, it first expands $T_L$ to include $N(C_0)$. It then uses the property that the final partition needs to be the identity partition to add some more vertices in $T_L$.

Consider parts $P'_{j'}$ or $P''_{j''}$ of $\mathcal{P}_0$. Suppose that $P'_{j'}$ (respectively, $P''_{j''} \cap B$) contains two vertices that are not dominated by the final solution $C$, then these two vertices would not be separated by it and hence would remain in one part, a contradiction. Therefore, any feasible solution $C$ needs to dominate all vertices but one in $P'_{j'}$ (respectively in $P''_{j''} \cap B$).

- The algorithm modifies $T_L$ to include $N(C_0)$. Then, it iterates over all the subsets $T_L^\circ$ of $B \setminus T_L$ such that for any $j' \in [t']$ and $j'' \in [t'']$, $|P'_{j'} \setminus (T_L^\circ \cup T_L)| \le 1$ and $|(P''_{j''} \cap B) \setminus (T_L^\circ \cup T_L)| \le 1$.

Consider a part $P_j$ of $\mathcal{P}_0$, which is completely contained in $R$. As $R$ is an independent set and the final solution $C$ is not allowed to include any vertex in $B$, for any part $P_j$, there is at most one vertex outside $C$, i.e., $|P_j \setminus C| \le 1$. However, unlike the previous step, the algorithm cannot enumerate all the required subsets of $R$ in the desired time. Nonetheless, it uses this property to safely perform the following sanity checks and modifications.

- Consider parts $P_j$ or $P''_{j''}$ of $\mathcal{P}_0$. Suppose there are two vertices in $P_j$ (respectively $P''_{j''} \cap R$) that are adjacent with some vertices in $B \setminus (T_L^\circ \cup T_L)$. Then, discard this guess of $T_L^\circ$ and move to the next subset.

- Consider parts $P_j$ or $P''_{j''}$ of $\mathcal{P}_0$. Suppose there is a unique vertex, say $r$, in $P_j$ (respectively, in $P''_{j''} \cap R$) that is adjacent with some vertex in $B \setminus (T_L^\circ \cup T_L)$. Then, modify $C_0$ to include all the vertices in $P_j \setminus \{r\}$ or in $(P''_{j''} \cup R) \setminus \{r\}$.

Consider a part $P''_{j''}$ of $\mathcal{P}_0$ and suppose $|(P''_{j''} \cap B) \setminus (T_L^\circ \cup T_L)| = 0$. Alternately, every vertex in $P''_{j''} \cap B$ is adjacent to some vertex in the final solution $C$. As $R$ is an independent set and $C \subseteq R$, this domination condition already refines the partition $P''_{j''}$, i.e. every vertex in $(P''_{j''} \cap B)$ needs to be adjacent with some
vertex in $C$ whereas no vertex in $(P_{j''}'' \cap R)$ can be adjacent with $C$. This justifies
the following modification.

- For a part $P_{j''}''$ of $\mathcal{P}_0$ such that $|(P_{j''}'' \cap B) \setminus (T_L^\circ \cup T_L)| = 0$, the algorithm modifies the input partition $\mathcal{P}_0$ by removing $P_{j''}''$ and adding two new parts $P_j := P_{j''}'' \cap R$ and $P_{j'}' := P_{j''}'' \cap B$.

Consider a part $P_{j''}''$ of $\mathcal{P}_0$ and suppose $|(P_{j''}'' \cap B) \setminus (T_L^\circ \cup T_L)| = 1$. Let $b$ be the unique vertex in $(P_{j''}'' \cap B) \setminus (T_L^\circ \cup T_L)$. Suppose there is a (unique) vertex, say $r$, in $(P_{j''}'' \cap R)$ that is not part of the final solution $C$. However, this implies that both $b$ and $r$ are in the same part, a contradiction.

- For part $P_{j''}''$ of $\mathcal{P}_0$ such that $|(P_{j''}'' \cap B) \setminus (T_L^\circ \cup T_L)| = 1$, the algorithm includes all the vertices $(P_{j''}'' \cap R)$ into $C_0$ (which, by definition, modifies $\mathcal{P}_0$). Also, it removes $P_{j''}''$ from $\mathcal{P}_0$ and adds $P_{j'}' := P_{j''}'' \cap B$.

These modifications ensure that any part of $\mathcal{P}_0$ is either completely contained
in $R$ or completely contained in $B$.

*Setting up the Dynamic Programming.* Define $\ell = |R \setminus C_0|$ and suppose $\{r_1, r_2, \ldots, r_\ell\}$ be the reordering of vertices in $R \setminus C_0$ such that any part in $P_j$ contains the consecutive elements in the order. Formally, for any $i_1 < i_2 < i_3 \in \{1, 2, \ldots, |R \setminus C_0|\}$ and $j \in \{1, 2, \ldots, t\}$, if $r_{i_1} \in P_j$ and $r_{i_3} \in P_j$, then $r_{i_2} \in P_j$. Define a function $\pi : \{1, 2, \ldots, |R \setminus C_0|\} \to \{1, 2, \ldots, t\}$ such that $\pi(r_i) = j$ if and only if vertex $r_i$ is in part $P_j$.

For the remaining part, the algorithm relies on a ‘set cover’ type dynamic programming.<fnref n="6" /> For every integer $i \in [0, \ell]$, define $R_i = \{r_1, r_2, \ldots, r_i\}$. Then, a ‘set cover’-type dynamic programming tries to find the optimum size of a subset of $R_i$ that dominates all the vertices in $S$, which is a subset of $T_L$. 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_L$, 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. 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$ is not the identity partition, it would imply that there exists a part $P$, say, of $\mathcal{P}$ with $|P| \ge 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. 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'$, $r''$ of $P_{\pi(i)} \cap R_i$ are not picked in $C$, the final solution $C$ cannot induce the identity partition, since $\{r'\}$, $\{r''\} \notin \mathcal{P}(C)$. Thus, since for any $r' \in P_{\pi(i)} \cap R_i \setminus \{r\}$, we have $\{r'\} \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

<footnote n="6">⁶ See [18, Theorem 3.10] for a simple $O(mn2^n)$ dynamic programming scheme for SET COVER on a universe of size $n$ and $m$ sets.</footnote>
$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. Since any (partial) solution upto $r_i$ does not refine any of the parts $P_{\pi(i)+1}, \dots, P_i$, for every part $P \in \mathcal{P}$ that does not intersect $P_1 \cup P_2 \cup \dots \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 look like, 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 $\text{opt}[i, \mathcal{P}, S]$ equal to 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 $\text{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 $\text{opt}[i, \mathcal{P}, S]$ for all $(i, \mathcal{P}, S) \in \mathcal{X}$ are updated inductively. Then finally, the quantity $\text{opt}[\ell, \mathcal{I}(R \cup B), T]$ gives us the required output of the problem. To start with, we define the quantity $\text{opt}[0, \mathcal{P}_0, N(C_0)] = |C_0|$ and set $\text{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 $\text{opt}[i, \mathcal{P}, S]$ updates by the following dynamic programming formula.

$$ \text{opt}[i, \mathcal{P}, S] = \min \left\{ \begin{array}{l} \text{opt}[i-1, \mathcal{P}, S], \\ 1 + \min_{\substack{\mathcal{P}' \subset \mathcal{P}(r_i)=\mathcal{P}, \\ S' \cup N(r_i)=S}} \text{opt}[i-1, \mathcal{P}', S'] \end{array} \right\} \quad (1) $$

The proof of correctness and running time of formula (1) can be found in the full version [10] of this paper.

### 3 Linear kernel for LOCATING-DOMINATING SET parameterized by Feedback Edge Set Number

We prove Theorem 2. 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 fes*. If a graph $G$ has $n$ vertices, $m$ edges, and $r$ components, then $\text{fes}(G) = m - n + r$ [17]. Our proof is nonconstructive, that is, it shows the *existence* of a large (but constant) number of gadget types with which the kernel can be constructed. For missing parts of the proof, we refer the reader to [10]. We first describe graphs of given feedback edge set number.

**Proposition 1 ([24, Observation 8]).** Any graph $G$ with feedback edge set number $\text{fes}$ is obtained from a multigraph $\tilde{G}$ with at most $2\text{fes} - 2$ vertices and $3\text{fes} - 3$ edges by first subdividing edges of $\tilde{G}$ an arbitrary number of times, and then, repeatedly attaching degree 1 vertices to the graph, and $\tilde{G}$ can be computed from $G$ in $\mathcal{O}(n + \text{fes})$ time.
By Proposition 1, we compute the multigraph $\tilde{G}$ in $O(n + \text{fes})$ time, and we
let $\tilde{V}$ be the set of vertices of $\tilde{G}$. For every edge $v_1v_2$ of $\tilde{G}$, we have either:

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

2. $v_1v_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$ and $c_2$ are the only vertices of $C$ adjacent to $v_1$ and $v_2$, respectively. (Possibly, $v_1 = v_2$ and the edge $v_1v_2$ is a loop of $\tilde{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 $\tilde{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 $\tilde{V}$. As there are at most $\text{fes} - 2$ vertices and $\text{4fes} - 3$ edges.

The kernelization has 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 $\tilde{G}$ described in Proposition 1. Step 2 will deal with the subgraphs that correspond to the edges of $\tilde{G}$.

**Step 1 - Handling the Hanging Trees.** By [27] (also [2]), there is a linear-time dynamic programming algorithm to solve LOCATING-DOMINATING SET on trees. To this end, one can 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\}$;

Consider the lexicographic ordering $A < B < C < D < E$. Then for $X < X'$,
if $L$ is a solution of type $X'$, it is also one of type $X$. For a tree $T$ rooted at $v$
and $X \in \{A, B, C, D, E\}$, let $\text{opt}_X(T, v)$ be the minimum size of a set $L \subseteq V(T)$
of type $X$. Note that $\text{opt}_C(T, v)$ is the location-domination number of $T$.

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

**Lemma 2.** Let $T$ be a tree with vertex $v$, and let $X, X' \in \{A, B, C, D, E\}$ with $X < X'$. We have $\text{opt}_{X'}(T, v) \le \text{opt}_X(T, v) \le \text{opt}_{X'}(T, v) + 1$.

By Lemma 2, for any rooted tree $(T, v)$, the five values $\text{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: \text{opt}_A(T, v) \le \text{opt}_B(T, v) \le \dots \le \text{opt}_E(T, v)$. Hence, for any rooted tree $(T, v)$, there is one value $X \in \{A, B, C, D, E\}$ so that, whenever $X' \le X$, we
<table><caption>Table 1: The five rooted tree gadgets with their values of the five $opt_X$ functions.</caption><thead><tr><th></th><th><i>v</i><sub>A</sub><br>○<br>T<sub>A</sub></th><th><i>v</i><sub>B</sub><br>○○○○<br>T<sub>B</sub></th><th><i>v</i><sub>C</sub><br>○○○○○○<br>T<sub>C</sub></th><th><i>v</i><sub>D</sub><br>○○○<br>T<sub>D</sub></th><th><i>v</i><sub>E</sub><br>○○○○○○○○<br>T<sub>E</sub></th></tr></thead><tbody><tr><th><i>opt</i><sub>A</sub></th><td>0</td><td>1</td><td>2</td><td>1</td><td>3</td></tr><tr><th><i>opt</i><sub>B</sub></th><td>1</td><td>1</td><td>2</td><td>1</td><td>3</td></tr><tr><th><i>opt</i><sub>C</sub></th><td>1</td><td>2</td><td>2</td><td>1</td><td>3</td></tr><tr><th><i>opt</i><sub>D</sub></th><td>1</td><td>2</td><td>3</td><td>1</td><td>3</td></tr><tr><th><i>opt</i><sub>E</sub></th><td>1</td><td>2</td><td>3</td><td>2</td><td>3</td></tr></tbody></table>

have $opt_{X'}(T, v) = opt_X(T, v)$, and whenever $X' > X$, we have $opt_{X'}(T, v) = opt_X(T, v) + 1$. Thus, we can introduce the following definition.

**Definition 2 (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'}(T, v) = k$ whenever $X' \le X$, and $opt_{X'}(T, v) = k + 1$ whenever $X' > X$ (note that $k$ may differ across the trees in $\mathcal{T}_X$).

Note that for trees in $\mathcal{T}_E$, all five types of optimal solutions have the same size. Lemma 2 implies that the set of all possible $(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\}$. Besides, it is not difficult to construct small rooted trees for all the five classes.

**Definition 3 (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 1, and let $k_X = opt_X(T_X, v_X)$.

We are now ready to present our first reduction rule.

**Reduction Rule 5.** Let $(G, k)$ be an instance of LOCATING-DOMINATING SET such that $G$ can be obtained from a graph $G'$ and a tree $T$ by identifying a vertex $v$ of $T$ with a vertex $w$ of $G'$ with $(T, v)$ being in the class $\mathcal{T}_X$, $X \in \{A, B, C, D, E\}$, and $opt_X(T, v) = t$. Then, we remove all vertices of $T \setminus \{v\}$ from $G$ (this results in $G'$), 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''$. The reduced instance is $(G'', k - t + k_X)$.

**Lemma 3.** For an instance $(G, k)$ of LOCATING-DOMINATING SET, Reduction Rule 5 can be applied exhaustively in time $O(n^2)$, and for each application, $(G, k)$ is a YES-instance of LOCATING-DOMINATING SET if and only if $(G'', k - t + k_X)$ is a YES-instance of LOCATING-DOMINATING SET.

**Step 2 – Handling the subgraphs corresponding to edges of $\tilde{G}$**. In the second step of our algorithm, we construct tree gadgets similar to those defined in Step 1, 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$ is 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.

Let $opt_{X,Y}(T, v_1, v_2)$ be the smallest size of a subset $L$ of $T$ of type $(X, Y)$. Again, there is a linear-time dynamic programming algorithm that, for any tree $T$ and vertices $v_1, v_2$, computes $opt_{X,Y}(T, v_1, v_2)$ for all $X, Y \in \{A, B, C, D, E\}$.

**Lemma 4.** Let $T$ be a tree with vertices $v_1, v_2$ of $T$, and let $X, X', Y, Y' \in \{A, B, C, D, E\}$ with $X \le X'$ and $Y \le Y'$. If $X = X'$ and $Y < Y'$ or $X < X'$ and $Y = Y'$, we have $opt_{X,Y}(T, v_1, v_2) \le opt_{X',Y'}(T, v_1, v_2) \le opt_{X,Y}(T, v_1, v_2) + 1$. If $X < X'$ and $Y < Y'$, we have $opt_{X,Y}(T, v_1, v_2) \le opt_{X',Y'}(T, v_1, v_2) \le opt_{X,Y}(T, v_1, v_2) + 2$.

**Definition 4 (Doubly rooted tree classes).** For a function $g : \{A, B, C, D, E\}^2 \to \{0, 1, 2\}$, we define the class $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 \{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)$.

There are at most $3^{25}$ possible classes of triples, since that is the number of possible functions $g$. By Lemma 4, these classes define a partition of all sets of triples $(T, v_1, v_2)$. 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 5 (Doubly-rooted tree gadgets).** For a function $g : \{A, B, C, D, E\}^2 \to \{0, 1, 2\}$, let $(T_g, v_1, v_2)$ be the smallest tree in $T_g$ (if such a tree exists), and let $k_g = opt_{A,A}(T_g, v_1, v_2)$.

The next reduction replaces some triples $(T, v_1, v_2)$ by gadgets in Definition 5.

**Reduction Rule 6.** Let $(G, k)$ be an instance of LOCATING-DOMINATING SET with

- an induced subgraph $G'$ 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 $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' 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'$), we consider $G'$ and a copy of doubly-rooted tree gadget $(T_g, v_X, v_Y)$ and identify $v_X$ with $v_1$ and $v_Y$ with $v_2$, to obtain $G''$. The reduced instance is $(G'', k-t+k_g)$.

**Lemma 5.** For an instance $(G, k)$ of LOCATING-DOMINATING SET, Reduction Rule 6 can be applied to every tree component corresponding to an edge of $\tilde{G}$ in time $O(nfes)$, and $(G, k)$ is a YES-instance of LOCATING-DOMINATING SET if and only if $(G'', k-t+k_g)$ is a YES-instance of LOCATING-DOMINATING SET.

*Completion of the proof.* By Lemmas 3 and 5, we can apply Reduction Rule 5 and Reduction Rule 6 in time $O(n^2+nfes) = O(mn)$. Since $\tilde{G}$ has at most 3fes-2 vertices and 4fes-3 edges, we replaced each vertex of $\tilde{G}$ by a constant-size tree-gadget from Definition 3 and each edge of $\tilde{G}$ by a constant-size doubly-rooted tree gadget from Definition 5, the resulting graph has $O(\text{fes})$ vertices and edges.

# 4 Incompressiblity of LOCATING-DOMINATING SET

In this section, we present the reduction used to prove Thereom 3 which says that LOCATING-DOMINATING SET does not admit a polynomial compression of size $O(n^{2-\epsilon})$ for any $\epsilon > 0$, unless NP $\subseteq$ coNP/poly, where n is the number of vertices of the input graph. The reduction takes as input an instance $(G', \langle R', B' \rangle, k')$ of RED-BLUE DOMINATING SET (a restricted version of DOMINATING SET, which also does not admit a compression with $O(n^{2-\epsilon})$ bits unless NP $\subseteq$ coNP/poly [1]) and constructs an instance $(G, k)$ of LOCATING-DOMINATING SET. Suppose we have $R' = \{r'_1, r'_2, \dots, r'_{|R|}\}$ and $B' = \{b'_1, b'_2, \dots, b'_{|B|}\}$. The reduction constructs graph G in the following steps. See Figure 4 for an illustration.

- It adds sets of vertices R and B to G, where R contains a vertex corresponding to each vertex in $R'$ and B contains two vertices corresponding to each vertex in $B'$. Formally, $R = \{r_i | i \in [|R'|]\}$ and $B = \{b_i^\circ, b_i^* | i \in [|B'|]\}$.

- The reduction adds a *bit representation gadget* to locate set R. Informally, it adds some supplementary vertices such that it is safe to assume these vertices are present in a locating-dominating set, and they locate every vertex in R.

* Set $q := \lceil \log(|R|) \rceil + 1$. Then $q$ allows to uniquely represent each integer in $|R|$ by its bit-representation in binary starting with 1 and not 0.

* For every $i \in [q]$, it adds two vertices $y_{i,1}$ and $y_{i,2}$ and edge $(y_{i,1}, y_{i,2})$.

* For every integer $\ell \in [|R|]$, let $\text{bit}(\ell)$ denote the binary representation of $\ell$ using $q$ bits. It connects $r_\ell \in R$ with $y_{i,1}$ if the $i^{\text{th}}$ bit in $\text{bit}(\ell)$ is 1.

* It adds two vertices $y_{0,1}$ and $y_{0,2}$, and edge $(y_{0,1}, y_{0,2})$, and makes every vertex in R adjacent with $y_{0,1}$.

Let $\text{bit-rep}(R)$ be the collection of the vertices $y_{i,1}$ for all $i \in \{0\} \cup [q]$.

- Similarly, the reduction adds a bit representation gadget to locate set B. However, it adds vertices such that for any pair $b_j^\circ, b_j^*$, the supplementary vertices adjacent to them are identical.
<figure><img src="image_5.png" /><figcaption>Fig. 4: An illustrative example of the graph constructed by the reduction. Adja-
cency to $y_{1,1}$, $y_{2,1}$, $y_{3,1}$ correspond to 1 in the bit representation from left to right
(most significant to least significant) bits. In this example, the bit representation
of $r_1$ is $\langle 1, 0, 0 \rangle$, $r_2$ is $\langle 0, 1, 0 \rangle$, $r_3$ is $\langle 1, 1, 0 \rangle$, etc. For brevity, we only show the
edges incident on $r_3$. The dotted line represents a non-edge. In this example, $r_3'$
is only adjacent to $b_2'$ in $G'$. It is easy to see that $r_3$ can only resolve pair $(b_2^\circ, b_2')$.</figcaption></figure>

* 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})$.

* For every integer $j \in [|B|/2]$, let $\text{bit}(j)$ be the binary representation of $j$ using $p$ bits. Connect $b_j^\circ, b_j^*$ to $B$ with $z_{i,1}$ if the $i^{th}$ bit in $\text{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 $B$ adjacent with $z_{0,1}$.

Let $\text{bit-rep}(B)$ be the collection of the vertices $z_{i,1}$ for all $i \in \{0\} \cup [p]$.

- Finally, for every pair of vertices $r'_i \in R'$ and $b'_j \in B'$,

* if $r'_i$ is not adjacent with $b'_j$, it adds both $(r_i, b_j^\circ)$ and $(r_i, b_j^*)$ to $E(G)$,

* if $r'_i$ is adjacent with $b'_j$ then it adds $(r_i, b_j^\circ)$ only, i.e., it does not add an edge with endpoints $r_i$ and $b_j^*$.

This completes the construction of $G$. The reduction sets $k = k' + |\text{bit-rep}(R)| + |\text{bit-rep}(B)| = k' + [\log(|R|)] + 1 + 1 + [\log(|B|/2)] + 1 + 1$, and returns $(G, k)$ as an instance of LOCATING-DOMINATING SET.

We present an overview of the proof of correctness. Let $(G', \langle R', B' \rangle, k')$ be a YES-instance of RED-BLUE DOMINATING SET and let $S' \subseteq R'$ be a solution. We claim that $S = S^* \cup \text{bit-rep}(R) \cup \text{bit-rep}(B)$ is a locating-dominating set of $G$ with $|S| \le k$, where $S^* = \{r_i : r'_i \in S'\}$. Note that vertices $y_{0,1}$ and $z_{0,1}$ force each pendant vertex adjacent with a vertex in $\text{bit-rep}(R) \cup \text{bit-rep}(B)$ to have a unique neighbour in $S$. Thus, apart from those of the form $(b_j^\circ, b_j^*)$, every other vertex pair is resolved by vertices in $\text{bit-rep}(R) \cup \text{bit-rep}(B)$. By the construction of $G$, a vertex $r_i \in R$ resolves a pair $b_j^\circ, b_j^*$ if and only if $r'_i$ and $b'_j$ are adjacent. This concludes the forward direction of the proof. In the reverse direction, by [12, Lemma 5], consider a locating dominating set $S$ containing $\text{bit-rep}(R) \cup \text{bit-rep}(B)$, as each vertex in it is adjacent to a pendant vertex. We can modify $S$ to another locating-dominating set $S_1$ such that $S_1 \setminus (\text{bit-rep}(R) \cup \text{bit-rep}(B)) \subseteq R$. It can also be verified that $S_1 \setminus (\text{bit-rep}(R) \cup \text{bit-rep}(B))$ is a dominating set of $G'$. This concludes the overview.
# 5 Conclusion

We investigated the structural parameterization of LOCATING-DOMINATING SET and TEST COVER. We presented several results about the algorithmic complexity of these two problems. However, our main technical contribution is an FPT algorithm when parameterized by the vertex cover number, a linear kernel when parameterized by the feedback edge set number, and a non-compressibility result. Our first two results imply that the double-exponential lower bound when parameterized by treewidth in [11] cannot be extended to larger parameters like vertex cover number and feedback edge set number. The reduction used to prove the third result also provides simplified proofs of some known results.

We do not know whether our $2^{O(\mathrm{vc}\log \mathrm{vc})}n^{O(1)}$-time FPT algorithm for LOCATING-DOMINATING SET parameterized by vertex cover (and similarly, the algorithm for TEST COVER parameterized by $|U|$) is optimal, or whether there exist single-exponential algorithms. Another open question in this direction, is whether this algorithm can be generalized to the parameter distance to cluster. As our linear kernel for parameter feedback edge set number is not explicit, it would be nice to obtain a concrete kernel.

**Acknowledgement.** This research was supported by the French government IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25), International Research Center "Innovation Transportation and Production Systems" of the I-SITE CAP 20-25, by the ANR project GRALMECO (ANR-21-CE48-0004). The research of Diptapriyo Majumdar was supported by the Science and Engineering Research Board (SERB) grant SRG/2023/001592 and the research of Prafullkumar Tale by the INSPIRE Faculty Fellowship of DST, India.

# References

1. Agrawal, A., Kanesh, L., Saurabh, S., Tale, P.: Paths to trees and cacti. Theor. Comput. Sci. **860**, 98–116 (2021)

2. Argiroffo, G.R., Bianchi, S.M., Lucarini, Y., Wagler, A.K.: Linear-time algorithms for three domination-based separation problems in block graphs. Discret. Appl. Math. **281**, 6–41 (2020)

3. Barbero, F., Isenmann, L., Thiebaut, J.: On the distance identifying set meta-problem and applications to the complexity of identifying problems on graphs. Algorithmica **82**(8), 2243–2266 (2020)

4. Basavaraju, M., Francis, M.C., Ramanujan, M.S., Saurabh, S.: Partially polynomial kernels for set cover and test cover. SIAM J. Discret. Math. **30**(3), 1401–1423 (2016)

5. Berman, P., DasGupta, B., Kao, M.: Tight approximability results for test set problems in bioinformatics. J. Comput. Syst. Sci. **71**(2), 145–162 (2005)

6. Bondy, J.A.: Induced subsets. Journal of Combinatorial Theory, Series B **12**(2), 201–202 (1972)

7. Bontridder, K.M.J.D., Halldórsson, B.V., Halldórsson, M.M., Hurkens, C.A.J., Lenstra, J.K., Ravi, R., Stougie, L.: Approximation algorithms for the test cover problem. Math. Program. **98**(1-3), 477–491 (2003)

8. Cappelle, M.R., de C. M. Gomes, G., dos Santos, V.F.: Parameterized algorithms for locating-dominating sets. CoRR abs/2011.14849 (2020)
9. Cappelle, M.R., Gomes, G.C.M., dos Santos, V.F.: Parameterized algorithms for locating-dominating sets. In: Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, (LAGOS). Procedia Computer Science, vol. 195, pp. 68-76 (2021)

10. Chakraborty, D., Foucaud, F., Majumdar, D., Tale, P.: Structural parameterization of locating-dominating set and test cover. CoRR abs/2411.17948 (2024)

11. Chakraborty, D., Foucaud, F., Majumdar, D., Tale, P.: Tight (double) exponential bounds for identification problems: Locating-dominating set and test cover. In: 35th International Symposium on Algorithms and Computation, (ISAAC). LIPIcs, vol. 322, pp. 19:1-19:18 (2024)

12. Chakraborty, D., Hakanen, A., Lehtilä, T.: The $n/2$-bound for locating-dominating sets in subcubic graphs. CoRR abs/2406.19278 (2024)

13. Chlebus, B.S., Nguyen, S.H.: On finding optimal discretizations for two attributes. In: Proceedings of the First International Conference on Rough Sets and Current Trends in Computing. vol. 1424, pp. 537-544 (1998)

14. Colbourn, C., Slater, P.J., Stewart, L.K.: Locating-dominating sets in series-parallel networks. Congressus Numerantium 56, 135-162 (1987)

15. Crowston, R., Gutin, G.Z., Jones, M., Muciaoccia, G., Yeo, A.: Parameterizations of test cover with bounded test sizes. Algorithmica 74(1), 367-384 (2016)

16. Crowston, R., Gutin, G.Z., Jones, M., Saurabh, S., Yeo, A.: Parameterized study of the test cover problem. In: Mathematical Foundations of Computer Science 2012 - 37th International Symposium, (MFCS). LNCS, vol. 7464, pp. 283-295 (2012)

17. Diestel, R.: Graph Theory, 4th Edition, Graduate texts in mathematics, vol. 173. Springer (2012)

18. Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series, Springer (2010)

19. Foucaud, F., Galby, E., Khazaliya, L., Li, S., Inerney, F.M., Sharma, R., Tale, P.: Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. In: 51st International Colloquium on Automata, Languages, and Programming, (ICALP). LIPIcs, vol. 297, pp. 66:1-66:19 (2024)

20. Garey, M.R., Johnson, D.S.: Computers and Intractability - A guide to NP-completeness. W.H. Freeman and Company (1979)

21. Gutin, G.Z., Muciaoccia, G., Yeo, A.: (non-)existence of polynomial kernels for the test cover problem. Inf. Process. Lett. 113(4), 123-126 (2013)

22. Habib, M., Paul, C., Viennot, L.: 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). pp. 25-38 (1998)

23. Harris, D.G., Narayanaswamy, N.S.: A faster algorithm for vertex cover parameterized by solution size. In: 41st International Symposium on Theoretical Aspects of Computer Science, (STACS). LIPIcs, vol. 289, pp. 40:1-40:18 (2024)

24. Kellerhals, L., Koana, T.: Parameterized complexity of geodetic set. J. Graph Algorithms Appl. 26(4), 401-419 (2022)

25. Rao, N.: Computational complexity issues in operative diagnosis of graph-based systems. IEEE Transactions on Computers 42(4), 447-457 (1993)

26. Rényi, A.: On random generating elements of a finite boolean algebra. Acta ScIENTIARUM Mathematicarum Szeged 22, 75-81 (1961)

27. Slater, P.J.: Domination and location in acyclic graphs. Networks 17(1), 55-64 (1987)

28. Slater, P.J.: Dominating and reference sets in a graph. Journal of Mathematical and Physical Sciences 22(4), 445-455 (1988)