# Metric Dimension and Geodetic Set Parameterized by Vertex Cover

Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, Prafullkumar Tale

## ► To cite this version:

Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, et al., Metric Dimension and Geodetic Set Parameterized by Vertex Cover. 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025), Mar 2025, Jena, Germany. pp.33, 10.4230/LIPIcs.STACS.2025.33 . hal-04963873

HAL Id: hal-04963873

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

Submitted on 24 Feb 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
# Metric Dimension and Geodetic Set Parameterized by Vertex Cover

Florent Foucaud ⬒ ⬒ ID

Université Clermont Auvergne, CNRS,
Mines Saint-Étienne, Clermont Auvergne INP,
LIMOS, 63000 Clermont-Ferrand, France

Liana Khazaliya ⬒ ⬒ ID

Technische Universität Wien, Austria

Fionn Mc Inerney ⬒ ⬒ ID

Telefónica Scientific Research, Barcelona, Spain

Prafullkumar Tale ⬒ ⬒ ID

Indian Institute of Science Education and Research Pune, India

Esther Galby ⬒ ID

Department of Computer Science and Engineering, Chalmers University of Technology and University of Gothenburg, Sweden

Shaohua Li ⬒ ID

School of Computer Science and Engineering,
Central South University, Changsha, China

Roohani Sharma ⬒ ID

University of Bergen, Norway

## Abstract

For a graph $G$, a subset $S \subseteq V(G)$ is called a *resolving set* of $G$ if, for any two vertices $u, v \in V(G)$, there exists a vertex $w \in S$ such that $d(w, u) \neq d(w, v)$. The METRIC DIMENSION problem takes as input a graph $G$ on $n$ vertices and a positive integer $k$, and asks whether there exists a resolving set of size at most $k$. In another *metric-based graph problem*, GEODETIC SET, the input is a graph $G$ and an integer $k$, and the objective is to determine whether there exists a subset $S \subseteq V(G)$ of size at most $k$ such that, for any vertex $u \in V(G)$, there are two vertices $s_1, s_2 \in S$ such that $u$ lies on a shortest path from $s_1$ to $s_2$.

These two classical problems are known to be intractable with respect to the natural parameter, i.e., the solution size, as well as most structural parameters, including the feedback vertex set number and pathwidth. We observe that both problems admit an FPT algorithm running in $2^{O(vc^2)} \cdot n^{O(1)}$ time, and a kernelization algorithm that outputs a kernel with $2^{O(vc)}$ vertices, where $vc$ is the vertex cover number. We prove that unless the Exponential Time Hypothesis (ETH) fails, METRIC DIMENSION and GEODETIC SET, even on graphs of bounded diameter, do not admit

- an FPT algorithm running in $2^{o(vc^2)} \cdot n^{O(1)}$ time, nor

- a kernelization algorithm that does not increase the solution size and outputs a kernel with $2^{o(vc)}$ vertices.

We only know of one other problem in the literature that admits such a tight algorithmic lower bound with respect to $vc$. Similarly, the list of known problems with exponential lower bounds on the number of *vertices* in kernelized instances is very short.

**2012 ACM Subject Classification** Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** Parameterized Complexity, ETH-based Lower Bounds, Kernelization, Vertex Cover, Metric Dimension, Geodetic Set

**Digital Object Identifier** 10.4230/LIPIcs.STACS.2025.33

Related Version Full Version: https://arxiv.org/abs/2405.01344 [19]

**Funding** Florent Foucaud: ANR project GRALMECO (ANR-21-CE48-0004), 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.

Liana Khazaliya: Vienna Science and Technology Fund (WWTF) [10.47379/ICT22029]; Austrian Science Fund (FWF) [10.55776/Y1329]; European Union's Horizon 2020 COFUND programme [LogiCS@TUWien, grant agreement No. 101034440].

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

© Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale;
licensed under Creative Commons License CC-BY 4.0

42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025).

Editors: Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyễn Kim Thắng;
Article No. 33; pp. 33:1–33:20

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

Leibniz International Proceedings in Informatics
LIPICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

<figure><img src="image_4.png" /></figure>
Shaohua Li: National Natural Science Foundation of China under Grant 62472449.

Fionn Mc Inerney: Smart Networks and Services Joint Undertaking (SNS JU) under the EU's Horizon Europe and innovation programme under Grant Agreement No. 101139067 (ELASTIC).

1 Introduction

In this article, we study two *metric-based* graph problems, one of which is defined through
distances, while the other relies on shortest paths. Metric-based graph problems are ubi-
quitous in computer science; for example, the classical (SINGLE-SOURCE) SHORTEST PATH,
(GRAPHIC) TRAVELING SALESPERSON or STEINER TREE problems fall into this category.
Those are fundamental problems, often stemming from applications in network design, for
which a considerable amount of algorithmic research has been done. Metric-based graph
packing and covering problems, like DISTANCE DOMINATION [29] or SCATTERED SET [30],
have recently gained a lot of attention. Their non-local nature leads to non-trivial algorithmic
properties that differ from most graph problems with a more local nature. We focus here on
the METRIC DIMENSION and GEODETIC SET problems, which arise from network monitoring
and network design, respectively. These two problems have far-reaching applications, as
exemplified by, e.g., the recent work [3] where it was shown that enumerating minimal
solution sets for METRIC DIMENSION and GEODETIC SET in (general) graphs and split
graphs, respectively, is equivalent to the enumeration of minimal transversals in hypergraphs,
whose solvability in total-polynomial time is arguably the most important open problem in
algorithmic enumeration. Formally, these two problems are defined as follows.

METRIC DIMENSION

**Input:** A graph *G* on *n* vertices and a positive integer *k*.

**Question:** Does there exist $S \subseteq V(G)$ such that $|S| \le k$ and, for any pair of vertices $u, v \in V(G)$, there exists a vertex $w \in S$ with $d(w, u) \neq d(w, v)$?

GEODETIC SET

**Input:** A graph *G* on *n* vertices and a positive integer *k*.

**Question:** Does there exist $S \subseteq V(G)$ such that $|S| \le k$ and, for any vertex $u \in V(G)$, there are two vertices $s_1, s_2 \in S$ such that $u$ lies on a shortest path from $s_1$ to $s_2$?

METRIC DIMENSION dates back to the 1970s [26, 38], whereas GEODETIC SET was
introduced in 1993 [25]. The non-local nature of these problems has since posed interesting
algorithmic challenges. METRIC DIMENSION was first shown to be NP-complete in general
graphs in Garey and Johnson's book [22], and this was later extended to many restricted
graph classes (see "Related work" below). GEODETIC SET was proven to be NP-complete
in [25], and later shown to be NP-hard on restricted graph classes as well.

As these two problems are NP-hard even in very restricted cases, it is natural to ask for
ways to confront this hardness. In this direction, the parameterized complexity paradigm
allows for a more refined analysis of a problem's complexity. In this setting, we associate
each instance *I* of a problem with a parameter *ℓ*, and are interested in algorithms running
in *f(ℓ) · |I|<sup>O(1)</sup>* time for some computable function *f*. Parameterized problems that admit
such an algorithm are called fixed-parameter tractable (FPT for short) with respect to the
considered parameter. Under standard complexity assumptions, parameterized problems
that are hard for the complexity class W[1] or W[2] do not admit such algorithms.
This approach, however, had limited success for these two problems. In the seminal paper [28], METRIC DIMENSION was proven to be W[2]-hard parameterized by the solution size $k$, even on subcubic bipartite graphs. Similarly, GEODETIC SET is W[2]-hard parameterized by the solution size [15, 31], even on chordal bipartite graphs. These initial hardness results drove the ensuing meticulous study of the problems under structural parameterizations: we present an overview in the “Related work” below. In this article, we focus on the vertex cover number, denoted by $\mathbf{vc}$, of the input graph and prove the following positive results.

**► Theorem 1.** *METRIC DIMENSION and GEODETIC SET admit*

* FPT algorithms running in $2^{O(\mathbf{vc}^2)} \cdot n^{O(1)}$ time, and

* kernelization algorithms that output kernels with $2^{O(\mathbf{vc})}$ vertices.

The second set of results follows from simple reduction rules, and was also observed in [28] for METRIC DIMENSION. The first set of results builds on the second set by using a simple, but critical observation. For METRIC DIMENSION, this also improves upon the $2^{2^{O(\mathbf{vc})}} \cdot n^{O(1)}$ algorithm mentioned in [28]. However, our main technical contribution is in proving that these results are optimal assuming the Exponential Time Hypothesis (ETH).

**► Theorem 2.** *Unless the ETH fails, METRIC DIMENSION and GEODETIC SET do not admit*

* FPT algorithms running in $2^{o(\mathbf{vc}^2)} \cdot n^{O(1)}$ time, nor

* kernelization algorithms that do not increase the solution size and output kernels with $2^{o(\mathbf{vc})}$ vertices, even on graphs of bounded diameter.

Both these statements constitute a rare set of results. Indeed, we know of only one other problem that admits a lower bound of the form $2^{o(\mathbf{vc}^2)} \cdot n^{O(1)}$ and a matching upper bound [1], whereas such results parameterized by pathwidth are mentioned in [36, 37]. Very recently, the authors in [7] also proved a similar result with respect to solution size. Similarly, the list of known problems with exponential lower bounds on the number of vertices in kernelized instances is very short. To the best of our knowledge, the only known results of this kind (i.e., ETH-based lower bounds on the number of vertices in a kernel) are for EDGE CLIQUE COVER [13], BICLIQUE COVER [9], STEINER TREE [35], STRONG METRIC DIMENSION [20], B-NCTD$^+$ [8], LOCATING DOMINATING SET [7], and TELEPHONE BROADCASTING [39]. For METRIC DIMENSION, the above also improves a result of [24], which states that METRIC DIMENSION parameterized by $k+\mathbf{vc}$ does not admit a polynomial kernel unless the polynomial hierarchy collapses to its third level. Indeed, the result of [24] does not rule out a kernel of super-polynomial or sub-exponential size.

Recently, Foucaud et al. [20] proved that, unless the ETH fails, METRIC DIMENSION and GEODETIC SET on graphs of bounded diameter do not admit $2^{2^{o(\mathbf{tv})}} \cdot n^{O(1)}$-time algorithms, thereby establishing one of the first such results for NP-complete problems. Note that $n \succ \mathbf{vc} \succ \mathbf{fvs} \succ \mathbf{tw}$ and $n \succ \mathbf{vc} \succ \mathbf{td} \succ \mathbf{pw} \succ \mathbf{tw}$ in the parameter hierarchy, where $n$ is the order, $\mathbf{fvs}$ is the feedback vertex set number, $\mathbf{td}$ is the treedepth, $\mathbf{pw}$ is the pathwidth, and $\mathbf{tw}$ is the treewidth of the graph. They further proved that their lower bound also holds for $\mathbf{fvs}$ and $\mathbf{td}$ in the case of METRIC DIMENSION, and for $\mathbf{td}$ in the case of GEODETIC SET [20]. A simple brute-force algorithm enumerating all possible candidates runs in $2^{O(n)}$ time for both of these problems. Thus, the next natural question is whether such a lower bound for METRIC DIMENSION and GEODETIC SET can be extended to larger parameters, in particular $\mathbf{vc}$. Our first results answer this question in the negative. Together with the lower bounds with respect to $\mathbf{vc}$, this establishes the boundary between parameters yielding single-exponential and double-exponential running times for METRIC DIMENSION and GEODETIC SET.
33:4 Metric Dimension and Geodetic Set Parameterized by Vertex Cover

Before moving forward, we highlight the parallels and differences between Foucaud et al. [20] and our work. Their aim was to establish double-exponential lower bounds for NP-complete problems, and to do so they focused on the restriction of the problems to graphs of bounded treewidth and diameter. Our objective is to closely examine one of the very few tractable results for METRIC DIMENSION and GEODETIC SET on general graphs by focusing on the vertex cover parameter. While we use some gadgets from [20], overall our reductions significantly differ from the corresponding reductions in that article. Note that we need to “control” the vertex cover number of the reduced graph, whereas the corresponding reductions by Foucaud et al. [20] only need to “control” the treewidth.

**Related Work.** We mention here results concerning structural parameterizations of METRIC DIMENSION and GEODETIC SET, and refer the reader to the full version of [20] for a more comprehensive overview of applications and related work regarding these two problems.

As previously mentioned, METRIC DIMENSION is W[2]-hard parameterized by the solution size $k$, even in subcubic bipartite graphs [28]. Several other parameterizations have been studied for this problem, on which we elaborate next (see also [21, Figure 1]). It was proven that there is an XP algorithm parameterized by the feedback edge set number [18], and FPT algorithms parameterized by the max leaf number [17], the modular-width and the treelength plus the maximum degree [2], the treedepth and the clique-width plus the diameter [23], and the distance to cluster (co-cluster, respectively) [21]. Recently, an FPT algorithm parameterized by the treewidth in chordal graphs was given in [5]. On the negative side, METRIC DIMENSION is W[1]-hard parameterized by the pathwidth even on graphs of constant degree [4], para-NP-hard parameterized by the pathwidth [33], and W[1]-hard parameterized by the combined parameter feedback vertex set number plus pathwidth [21].

The parameterized complexity of GEODETIC SET was first addressed in [31], in which it was observed that the reduction from [15] implies that the problem is W[2]-hard parameterized by the solution size (even for chordal bipartite graphs). This motivated the authors of [31] to investigate structural parameterizations of GEODETIC SET. They proved the problem to be W[1]-hard for the combined parameters solution size, feedback vertex set number, and pathwidth, and FPT for the parameters treedepth, modular-width (more generally, clique-width plus diameter), and feedback edge set number [31]. The problem was also shown to be FPT on chordal graphs when parameterized by the treewidth [6].

2 Preliminaries

For an integer $a$, we let $[a] = \{1, \dots, a\}$.

**Graph theory.** We use standard graph-theoretic notation and refer the reader to [14] for any undefined notation. For an undirected graph $G$, the sets $V(G)$ and $E(G)$ denote its set of vertices and edges, respectively. Two vertices $u, v \in V(G)$ are *adjacent* or *neighbors* if $(u, v) \in E(G)$. The *open neighborhood* of a vertex $u \in V(G)$, denoted by $N(u) := N_G(u)$, is the set of vertices that are neighbors of $u$. The *closed neighborhood* of a vertex $u \in V(G)$ is denoted by $N[u] := N_G[u] := N_G(u) \cup \{u\}$. For any $X \subseteq V(G)$ and $u \in V(G)$, $N_X(u) = N_G(u) \cap X$. Any two vertices $u, v \in V(G)$ are *true twins* if $N[u] = N[v]$, and are *false twins* if $N(u) = N(v)$. For a subset $S$ of $V(G)$, we say that the vertices in $S$ are true (false, respectively) twins if, for any $u, v \in S$, $u$ and $v$ are true (false, respectively) twins. The *distance* between two vertices $u, v \in V(G)$ in $G$, denoted by $d(u, v) := d_G(u, v)$, is the length of a $(u, v)$-shortest path in $G$. For a subset $S$ of $V(G)$, we define $N[S] = \bigcup_{v \in S} N[v]$ and $N(S) = N[S] \setminus S$. For
a graph $G$, a set $X \subseteq V(G)$ is said to be a *vertex cover* if $V(G) \setminus X$ is an independent set. We denote by $\text{vc}(G)$ the size of a minimum vertex cover in $G$. When $G$ is clear from the context, we simply say $\text{vc}$. A vertex is *simplicial* if its neighborhood forms a clique. Observe that any simplicial vertex $v$ does not belong to any shortest path between any pair $x, y$ of vertices (both distinct from $v$). Hence, the following holds.

**► Observation 3 ([10]).** If a graph $G$ contains a simplicial vertex $v$, then $v$ belongs to any geodetic set of $G$. Specifically, every degree-1 vertex belongs to any geodetic set of $G$.

**Metric Dimension.** A subset of vertices $S' \subseteq V(G)$ resolves a pair of vertices $u, v \in V(G)$ if there exists a vertex $w \in S'$ such that $d(w, u) \neq d(w, v)$. A vertex $u \in V(G)$ is distinguished by a subset of vertices $S' \subseteq V(G)$ if, for any $v \in V(G) \setminus \{u\}$, there exists a vertex $w \in S'$ such that $d(w, u) \neq d(w, v)$.

**Parameterized Complexity.** An instance of a parameterized problem $\Pi$ comprises an input $I$, which is an input of the classical instance of the problem, and an integer $\ell$, which is called the parameter. A problem $\Pi$ is said to be *fixed-parameter tractable* or in FPT if given an instance $(I, \ell)$ of $\Pi$, we can decide whether or not $(I, \ell)$ is a YES-instance of $\Pi$ in $f(\ell) \cdot |I|^{O(1)}$ time, for some computable function $f$ whose value depends only on $\ell$.

A *kernelization* algorithm for $\Pi$ is a polynomial-time algorithm that takes as input an instance $(I, \ell)$ of $\Pi$ and returns an *equivalent* instance $(I', \ell')$ of $\Pi$, where $|I'|, \ell' \le f(\ell)$, where $f$ is a function that depends only on $\ell$. If such an algorithm exists for $\Pi$, we say that $\Pi$ admits a kernel of size $f(\ell)$. If $f$ is a polynomial or exponential function of $\ell$, we say that $\Pi$ admits a polynomial or exponential kernel, respectively. If $\Pi$ is a graph problem, then $I$ contains a graph, say $G$, and $I'$ contains a graph, say $G'$. In this case, we say that $\Pi$ admits a kernel with $f(\ell)$ vertices if the number of vertices of $G'$ is at most $f(\ell)$.

It is typical to describe a kernelization algorithm as a series of reduction rules. A *reduction rule* is a polynomial-time algorithm that takes as an input an instance of a problem and outputs another (usually reduced) instance. A reduction rule said to be *applicable* on an instance if the output instance is different from the input instance. A reduction rule is *safe* if the input instance is a YES-instance if and only if the output instance is a YES-instance.

The Exponential Time Hypothesis (ETH) roughly states that $n$-variable 3-SAT cannot be solved in $2^{o(n)}$ time. For more on parameterized complexity and related terminologies, we refer the reader to the recent book by Cygan et al. [12].

**3-Partitioned-3-SAT.** Our lower bound proofs consist of reductions from the 3-PARTITIONED-3-SAT problem. This version of 3-SAT was introduced in [32] and is defined as follows.

**3-PARTITIONED-3-SAT**

**Input:** A formula $\psi$ in 3-CNF form, together with a partition of the set of its variables into three disjoint sets $X^\alpha$, $X^\beta$, $X^\gamma$, with $|X^\alpha| = |X^\beta| = |X^\gamma| = N$, and such that no clause contains more than one variable from each of $X^\alpha$, $X^\beta$, and $X^\gamma$.

**Question:** Determine whether $\psi$ is satisfiable.

**Organization of the paper.** We start with the results for METRIC DIMENSION, which are then followed by those for GEODETIC SET. For each, we first present the algorithms and then the reductions. Since space requirements prohibit us from presenting our reductions in
detail, we give an outline that discusses the main technical ideas behind our reductions for getting the lower-bound results for both METRIC DIMENSION and GEODETIC SET. For the complete formal proofs, we refer the reader to the full version of this paper [19].

3 Metric Dimension: Algorithms for Vertex Cover Parameterization

In this section, we prove Theorem 1 for *METRIC DIMENSION*. The kernelization algorithm exhaustively applies the following reduction rule.

▷ Reduction Rule 1. If there exist three vertices $u, v, x \in I$ such that $u, v, x$ are false twins, then delete $x$ and decrease $k$ by one.

**Proof that Reduction Rule 1 is safe.** Since $u, v, x$ are false twins, $N(u) = N(v) = N(x)$. This implies that, for any vertex $w \in V(G) \setminus \{u, v, x\}$, $d(w, v) = d(w, u) = d(w, x)$. Hence, any resolving set that excludes at least two vertices in $\{u, v, x\}$ cannot resolve all three pairs $\{u, v\}$, $\{u, x\}$, and $\{v, x\}$. As the vertices in $\{u, v, x\}$ are distance-wise indistinguishable from the remaining vertices, we can assume, without loss of generality, that any resolving set contains both $u$ and $x$. Hence, any pair of vertices in $V(G) \setminus \{u, x\}$ that is resolved by $x$ is also resolved by $u$. In other words, if $S$ is a resolving set of $G$, then $S \setminus \{x\}$ is a resolving set of $G - \{x\}$. This implies the correctness of the forward direction. The correctness of the reverse direction trivially follows from the fact that we can add $x$ into a resolving set of $G - \{x\}$ to obtain a resolving set of $G$. ◀

**Lemma 4.** *METRIC DIMENSION*, parameterized by the vertex cover number *vc*, admits a polynomial-time kernelization algorithm that returns an instance with $2^{O(vc)}$ vertices.

**Proof.** Given a graph $G$, let $X \subseteq V(G)$ be a minimum vertex cover of $G$. If such a vertex cover is not given, then we can find a 2-factor approximate vertex cover in polynomial time. Let $I := V(G) \setminus X$. By the definition of a vertex cover, the vertices of $I$ are pairwise non-adjacent.

The kernelization algorithm exhaustively applies Reduction Rule 1. Now, consider an instance on which Reduction Rule 1 is not applicable. If the budget is negative, then the algorithm returns a trivial No-instance of constant size. Otherwise, for any $Y \subseteq X$, there are at most two vertices $u, v \in I$ such that $N(u) = N(v) = Y$. This implies that the number of vertices in the reduced instance is at most $|X| + 2 \cdot 2^{|X|} = 2^{vc+1} + vc$. ◀

Next, we present an XP-algorithm parameterized by the vertex cover number. This algorithm, along with the kernelization algorithm above, imply<fnref n="1" /> that METRIC DIMENSION admits an algorithm running in $2^{O(vc^2)} \cdot n^{O(1)}$ time.

**Lemma 5.** *METRIC DIMENSION* admits an algorithm running in $n^{O(vc)}$ time.

**Proof.** The algorithm starts by computing a minimum vertex cover $X$ of $G$ in $2^{O(vc)} \cdot n^{O(1)}$ time using an FPT algorithm for the VERTEX COVER problem, for example the one in [11] or [27]. Let $I := V(G) \setminus X$. Then, in polynomial time, it computes a largest subset $F$ of $I$ such that, for every vertex $u$ in $F$, $I \setminus F$ contains a false twin of $u$. By the arguments in the previous proof, if there are false twins in $I$, say $u, v$, then any resolving set contains at least one of them. Hence, it is safe to assume that any resolving set contains $F$. If $k - |F| < 0$,

<footnote n="1">¹ Note that the application of Reduction Rule 1 does not increase the vertex cover number.</footnote>
then the algorithm returns No. Otherwise, it enumerates every subset of vertices of size at most |X| in $X \cup (I \setminus F)$. If there exists a subset $A \subseteq X \cup (I \setminus F)$ such that $A \cup F$ is a resolving set of $G$ of size at most $k$, then it returns $A \cup F$. Otherwise, it returns No.

In order to prove that the algorithm is correct, we prove that $X \cup F$ is a resolving set of $G$. It is easy to see that, for a pair of distinct vertices $u, v$, if $u \in X \cup F$ and $v \in V(G)$, then the pair is resolved by $u$. It remains to argue that every pair of distinct vertices in $(I \setminus F) \times (I \setminus F)$ is resolved by $X \cup F$. Note that, for any two vertices $u, v \in I \setminus F$, $N(u) \neq N(v)$ as otherwise $u$ can be moved to $F$, contradicting the maximality of $F$. Hence, there is a vertex in $X$ that is adjacent to $u$, but not adjacent to $v$, resolving the pair $(u, v)$. This implies the correctness of the algorithm. The running time of the algorithm easily follows from its description. ◀

# 4 Metric Dimension: Lower Bounds Regarding Vertex Cover

In this section, we prove Theorem 2 for METRIC DIMENSION. The first integral part of our technique is to reduce from a variant of 3-SAT known as 3-PARTITIONED-3-SAT [32]. In this problem, the input is a 3-CNF formula $\psi$, together with a partition of the set of its variables into three disjoint sets $X^\alpha$, $X^\beta$, $X^\gamma$, with $|X^\alpha| = |X^\beta| = |X^\gamma| = N$, and such that no clause contains more than one variable from each of $X^\alpha$, $X^\beta$, and $X^\gamma$. The objective is to determine whether $\psi$ is satisfiable. Unless the ETH fails, 3-PARTITIONED-3-SAT does not admit an algorithm running in $2^{o(N)}$ time [32, Theorem 3]. Our key result is the following.

**▶ Theorem 6.** There is an algorithm that, given an instance $\psi$ of 3-PARTITIONED-3-SAT on $N$ variables, runs in $2^{O(\sqrt{N})}$ time, and constructs an equivalent instance $(G, k)$ of METRIC DIMENSION such that $\text{vc}(G) + k = O(\sqrt{N})$ (and $|V(G)| = 2^{O(\sqrt{N})}$).

The above theorem, along with the arguments that are standard to prove the ETH-based lower bounds, immediately imply the following results.

**▶ Corollary 7.** *Unless the ETH fails, METRIC DIMENSION does not admit an algorithm running in $2^{o(\text{vc}^2)} \cdot n^{O(1)}$ time.*

**▶ Corollary 8.** *Unless the ETH fails, METRIC DIMENSION does not admit a kernelization algorithm that does not increase the solution size $k$ and outputs a kernel with $2^{o(k+\text{vc})}$ vertices.*

**Proof.** Toward a contradiction, assume that such a kernelization algorithm exists. Consider the following algorithm for 3-PARTITIONED-3-SAT. Given a 3-PARTITIONED-3-SAT formula on $N$ variables, it uses Theorem 6 to obtain an equivalent instance of $(G, k)$ such that $\text{vc}(G) + k = O(\sqrt{N})$ and $|V(G)| = 2^{O(\sqrt{N})}$. Then, it uses the assumed kernelization algorithm to construct an equivalent instance $(H, k')$ such that $H$ has $2^{o(\text{vc}(G)+k)}$ vertices and $k' \le k$. Finally, it uses a brute-force algorithm, running in $|V(H)|^{O(k')}$ time, to determine whether the reduced instance, or equivalently the input instance of 3-PARTITIONED-3-SAT, is a YES-instance. The correctness of the algorithm follows from the correctness of the respective algorithms and our assumption. The total running time of the algorithm is $2^{O(\sqrt{N})} + (|V(G)|+k)^{O(1)} + |V(H)|^{O(k')} = 2^{O(\sqrt{N})} + (2^{O(\sqrt{N})})^{O(1)} + (2^{o(\sqrt{N})})^{O(\sqrt{N})} = 2^{o(N)}$. But this contradicts the ETH. ◀

The reduction, presented in Section 4.2, uses tools introduced in the next subsection.
<figure><img src="image_5.png" /><figcaption>■ **Figure 1** Set Identifying Gadget (left). The blue box represents bit-rep($X$). The yellow lines represent that all possible edges exist between bit-rep($X$) $\setminus$ bits($X$) and nullifier($X$), nullifier($X$) and $N(X)$, and $y_\star$ and $X$. Note that $G'$ is not necessarily restricted to the graph induced by the vertices in $X \cup N(X)$. Vertex Selector Gadget (right). For $X \in \{B, A\}$, the blue box represents bit-rep($X$), the blue link represents the connection with respect to the binary representation, and the yellow line represents that nullifier($X$) is adjacent to each vertex in bit-rep($X$) $\setminus$ bits($X$). Dotted lines highlight absent edges.</figcaption></figure>

## 4.1 Preliminary Tools

### 4.1.1 Set Identifying Gadget

We redefine a gadget introduced in [20]. Suppose we are given a graph $G'$ and a subset $X \subseteq V(G')$ of its vertices. Further, suppose that we want to add a vertex set $X^+$ to $G'$ in order to obtain a new graph $G$ such that (1) each vertex in $X \cup X^+$ will be distinguished by vertices in $X^+$ that must be in any resolving set $S$ of $G$, and (2) no vertex in $X^+$ can resolve any pair of vertices in $V(G) \setminus (X \cup X^+)$ that are in the same distance class with respect to $X$.

The graph induced by the vertices of $X^+$, along with the edges connecting $X^+$ to $G'$, is the Set Identifying Gadget for $X$ [20]. Given a graph $G'$ and a non-empty subset $X \subseteq V(G')$ of its vertices, to construct such a graph $G$, we add vertices and edges to $G'$ as follows:

- The vertex set $X^+$ that we are aiming to add is the union of a set bit-rep and a special vertex denoted by nullifier($X$).

- Let $X = \{x_i \mid i \in [|X|]\}$ and set $q := \lceil \log(|X| + 2) \rceil + 1$. We select this value for $q$ to (1) uniquely represent each integer in $ [|X|] $ by its bit-representation in binary (note that we start from 1 and not 0), (2) ensure that the only vertex whose bit-representation contains all 1's is nullifier($X$), and (3) reserve one spot for an additional vertex $y_\star$.

- For every $i \in [q]$, add three vertices $y_i^a, y_i, y_i^b$, and add the path $(y_i^a, y_i, y_i^b)$.

- Add three vertices $y_\star^a, y_\star, y_\star^b$, and add the path $(y_\star^a, y_\star, y_\star^b)$. Add all the edges to make $\{y_i \mid i \in [q]\} \cup \{y_\star\}$ a clique. Make $y_\star$ adjacent to each vertex $v \in X$. Let bit-rep($X$) := $\{y_i, y_i^a, y_i^b \mid i \in [q]\} \cup \{y_\star, y_\star^a, y_\star^b\}$ and bits($X$) := $\{y_i^a, y_i^b \mid i \in [q]\} \cup \{y_\star^a, y_\star^b\}$.

- For every integer $j \in [|X|]$, let bin($j$) denote the binary representation of $j$ using $q$ bits. Connect $x_j$ with $y_i$ if the $i^{th}$ bit (going from left to right) in bin($j$) is 1.

- Add a vertex, denoted by nullifier($X$), and make it adjacent to every vertex in $\{y_i \mid i \in [q]\} \cup \{y_\star\}$. One can think of nullifier($X$) as the only vertex whose bit-representation contains all 1's.

- For every vertex $u \in V(G) \setminus (X \cup X^+)$ such that $u$ is adjacent to some vertex in $X$, add an edge between $u$ and nullifier($X$). We add this vertex to ensure that vertices in bit-rep($X$) do not resolve any pairs of vertices in $V(G) \setminus (X \cup X^+)$ that are in the same distance class with respect to $X$.

This completes the construction of $G$. See Figure 1 for an illustration.
## 4.1.2 Gadget to Add Critical Pairs

Any resolving set needs to resolve all pairs of vertices in the input graph. As we will see, some pairs are harder to resolve than others.

Suppose that we need to have $m \in \mathbb{N}$ such “hard” pairs in a graph $G$. So, for each $i \in [m]$, we make a pair of vertices $\langle c_i^\circ, c_i^* \rangle$ *critical* as follows. Define $C := \{c_i^\circ, c_i^* | i \in [m]\}$. We then add bit-rep($C$) and nullifier($C$) as mentioned above (taking $C$ as the set $X$), with the edges between $\{c_i^\circ, c_i^*\}$ and bit-rep($C$) defined by $\text{bin}(i)$, i.e., connect both $c_i^\circ$ and $c_i^*$ with the $j$-th vertex of bit-rep($C$) if the $j$-th bit (going from left to right) in $\text{bin}(i)$ is 1. Hence, bit-rep($C$) can resolve any pair of the form $\langle c_i^\circ, c_\ell^* \rangle$, $\langle c_i^\circ, c_\ell^\circ \rangle$, or $\langle c_i^*, c_\ell^* \rangle$ as long as $i \neq \ell$. As before, bit-rep($C$) can also resolve all pairs with one vertex in $C \cup \text{bit-rep}(C) \cup \{\text{nullifier}(C)\}$, but no critical pair of vertices.

## 4.1.3 Vertex Selector Gadgets

Suppose that we are given a collection of sets $A_1, A_2, \dots, A_q$ of vertices in a graph $G$, and we want to ensure that any resolving set of $G$ includes at least one vertex from $A_i$ for every $i \in [q]$. In the following, we construct a gadget that achieves a slightly weaker objective.

- Let $A = \bigcup_{i \in [q]} A_i$. Add a set identifying gadget for $A$ as mentioned in Subsection 4.1.1.

- For every $i \in [q]$, add two vertices $b_i^\circ$ and $b_i^*$. Use the gadget mentioned in Subsection 4.1.2 to make all the pairs of the form $\langle b_i^\circ, b_i^* \rangle$ critical pairs (in the way it was introduced for $\langle c_i^\circ, c_i^* \rangle$).

- For every $a \in A_i$, add an edge $(a, b_i^\circ)$. We highlight that we do not make $a$ adjacent to $b_i^*$ by a dotted line in Figure 1. Also, add the edges $(a, \text{nullifier}(B))$, $(b_i^\circ, \text{nullifier}(A))$, $(b_i^*, \text{nullifier}(A))$, and $(\text{nullifier}(A), \text{nullifier}(B))$.

This completes the construction. Note that the only vertices that can resolve a critical pair $\langle b_i^\circ, b_i^* \rangle$, apart from $b_i^\circ$ and $b_i^*$, are the vertices in $A_i$ (see Figure 1, all other vertices are equidistant from both vertices of the pair). Hence, every resolving set contains at least one vertex in $\{b_i^\circ, b_i^*\} \cup A_i$.

## 4.2 Reduction

Consider an instance $\psi$ of 3-PARTITIONED-3-SAT with $X^\alpha, X^\beta, X^\gamma$ the partition of the variable set, where each part contains $N$ variables. By adding dummy variables in each of these sets, we can assume that $\sqrt{N}$ is an integer. From $\psi$, we construct the graph $G$ as follows. We describe the construction of the part of the graph $G$ that corresponds to $X^\alpha$, with the parts corresponding to $X^\beta$ and $X^\gamma$ being analogous. Rename the variables in $X^\alpha$ to $x_{i,j}^\alpha$ for $i,j \in [\sqrt{N}]$.

- We partition the variables of $X^\alpha$ into buckets $X_1^\alpha, X_2^\alpha, \dots, X_{\sqrt{N}}^\alpha$ such that each bucket contains $\sqrt{N}$ variables. Let $X_i^\alpha = \{x_{i,j}^\alpha | j \in [\sqrt{N}]\}$ for all $i \in [\sqrt{N}]$.

- For every $X_i^\alpha$, we construct a set $A_i^\alpha$ of $2^{\sqrt{N}}$ new vertices, $A_i^\alpha = \{a_{i,\ell}^\alpha | \ell \in [2^{\sqrt{N}}]\}$. Each vertex in $A_i^\alpha$ corresponds to a certain possible assignment of variables in $X_i^\alpha$. Let $A^\alpha$ be the collection of all the vertices added in the above step, that is, $A^\alpha = \{a_{i,\ell}^\alpha \in A_i | i \in [\sqrt{N}] \text{ and } \ell \in [2^{\sqrt{N}}]\}$. We add a set identifying gadget as mentioned in Subsection 4.1.1 in order to resolve every pair of vertices in $A^\alpha$.

- For every $X_i^\alpha$, we construct a pair $\langle b_i^{\alpha,\circ}, b_i^{\alpha,*} \rangle$ of vertices. Then, we add a gadget to make the pairs $\{\langle b_i^{\alpha,\circ}, b_i^{\alpha,*} \rangle | i \in [\sqrt{N}]\}$ critical as mentioned in Subsection 4.1.2. Let $B^\alpha = \{b_i^{\alpha,\circ}, b_i^{\alpha,*} | i \in [\sqrt{N}]\}$ be the collection of vertices in the critical pairs. We add edges in $B^\alpha$ to make it a clique.
- We would like that any resolving set contains at least one vertex in $A_i^\alpha$ for every $i \in [\sqrt{N}]$, but instead we add the construction from Subsection 4.1.3 that achieves the slightly weaker objective as mentioned there. However, for every $A_i^\alpha$, instead of adding two new vertices, we use $\langle b_i^{\alpha, \circ}, b_i^{\alpha, *} \rangle$ as the necessary critical pair. Formally, for every $i \in [\sqrt{N}]$, we make $b_i^{\alpha, \circ}$ adjacent to every vertex in $A_i^\alpha$. We add edges to make nullifier($B^\alpha$) adjacent to every vertex in $A^\alpha$, and nullifier($A^\alpha$) adjacent to every vertex in $B^\alpha$. Recall that there is also the edge (nullifier($B^\alpha$), nullifier($A^\alpha$)).

- For every clause $C_q$ in $\psi$, we have a pair of vertices $\langle c_q^\circ, c_q^* \rangle$. Let $C$ be the collection of vertices in such pairs. We add portals that transmit information from vertices corresponding to assignments, i.e., vertices in $A^\alpha$, to pairs corresponding to clauses. A portal is a clique on $\sqrt{N}$ vertices in the graph $G$. We add three portals, the truth portal (denoted by $T^\alpha$), false portal (denoted by $F^\alpha$), and validation portal (denoted by $V^\alpha$). Let $T^\alpha = \{t_1^\alpha, t_2^\alpha, \dots, t_{\sqrt{N}}^\alpha\}$, $F^\alpha = \{f_1^\alpha, f_2^\alpha, \dots, f_{\sqrt{N}}^\alpha\}$, and $V^\alpha = \{v_1^\alpha, v_2^\alpha, \dots, v_{\sqrt{N}}^\alpha\}$. Moreover, let $P^\alpha = V^\alpha \cup T^\alpha \cup F^\alpha$.

- We add a set identifying gadget for $P^\alpha$ as mentioned in Subsection 4.1.1. We add an edge between nullifier($A^\alpha$) and every vertex of $P^\alpha$; and the edge (nullifier($P^\alpha$), nullifier($A^\alpha$)). However, we note that we do not add edges between nullifier($P^\alpha$) and $A^\alpha$, as can be seen in Figure 2. Lastly, we add edges in $P^\alpha$ to make it a clique.

- We add edges between $A^\alpha$ and the portals as follows. For $i \in [\sqrt{N}]$ and $\ell \in [2^{\sqrt{N}}]$, consider a vertex $a_{i,\ell}^\alpha$ in $A_i^\alpha$. Recall that this vertex corresponds to an assignment $\pi: X_i^\alpha \mapsto \{\text{True}, \text{False}\}$, where $X_i^\alpha$ is the collection of variables $\{x_{i,j}^\alpha \mid j \in [\sqrt{N}]\}$. If $\pi(x_{i,j}^\alpha) = \text{True}$, then we add the edge $(a_{i,\ell}^\alpha, t_j^\alpha)$. Otherwise, $\pi(x_{i,j}^\alpha) = \text{False}$, and we add the edge $(a_{i,\ell}^\alpha, f_j^\alpha)$. We add the edge $(a_{i,\ell}^\alpha, v_i^\alpha)$ for every $\ell \in [2^{\sqrt{N}}]$.

Then, we repeat the above steps to construct $B^\beta, A^\beta, P^\beta, B^\gamma, A^\gamma, P^\gamma$. Now, we are ready to proceed through the final steps to complete the construction.

- For every clause $C_q$ in $\psi$, as it has been already introduced above, we have a pair of vertices $\langle c_q^\circ, c_q^* \rangle$ and $C$ is the collection of vertices in such pairs. Then, we add a gadget as was described in Subsection 4.1.2 to make each pair $\langle c_q^\circ, c_q^* \rangle$ a critical one.

- For each $\delta \in \{\alpha, \beta, \gamma\}$, we add an edge between nullifier($P^\delta$) and every vertex of $C$, and we add the edge (nullifier($P^\delta$), nullifier($C$)). Now, we add edges between $C$ and the portals as follows for each $\delta \in \{\alpha, \beta, \gamma\}$. Consider a clause $C_q$ in $\psi$ and the corresponding critical pair $\langle c_q^\circ, c_q^* \rangle$ in $C$. As $\psi$ is an instance of 3-PARTITIONED-3-SAT, there is at most one variable in $X^\delta$ that appears in $C_q$. If $C_q$ does not contain a variable in $X^\delta$, then we make $c_q^\circ$ and $c_q^*$ adjacent to every vertex in $V^\delta$, and they are not adjacent to any vertex in $T^\delta \cup F^\delta$. Otherwise, suppose that $C_q$ contains the variable $x_{i,j}^\delta$ for some $i,j \in [\sqrt{N}]$. The first subscript decides the edges between $\langle c_q^\circ, c_q^* \rangle$ and the validation portal, whereas the second subscript decides the edges between $\langle c_q^\circ, c_q^* \rangle$ and either the truth portal or false portal in the following sense. We add all edges of the form $(v_{i'}^\delta, c_q^\circ)$ and $(v_{i'}^\delta, c_q^*)$ for every $i' \in [\sqrt{N}]$ such that $i' \neq i$. If $x_{i,j}^\delta$ appears as a positive literal in $C_q$, then we add the edge $(t_j^\delta, c_q^\circ)$. Otherwise, $x_{i,j}^\delta$ appears as a negative literal in $C_q$, and we add the edge $(f_j^\delta, c_q^\circ)$.

This concludes the construction of $G$. The reduction returns $(G, k)$ as an instance of METRIC DIMENSION where

$$k = 3 \cdot \left( \sqrt{N} + (\lceil \log(|B^\alpha|/2 + 2) \rceil + 1) + (\lceil \log(|A^\alpha| + 2) \rceil + 1) + (\lceil \log(|P^\alpha| + 2) \rceil + 1) \right) + \lceil \log(|C|/2 + 2) \rceil + 1.$$
<figure><img src="image_6.png" /><figcaption>■ **Figure 2** Overview of the reduction. Sets in ellipses are independent sets and sets in rectangles are cliques. For $X \in \{B^\alpha, A^\alpha, P^\alpha, C\}$, the blue rectangle attached to it via the blue edge represents bit-rep($X$), and the yellow line between a vertex and bit-rep($X$) indicates that vertex is connected to every vertex in bit-rep($X$) $\setminus$ bits($X$). The remainder of the yellow lines represent that vertex is connected to every vertex in the set the edge goes to. Note the exception of nullifier($P^\alpha$) which is not adjacent to any vertex in $A^\alpha$. Purple lines between two sets denote adjacencies with respect to indexing, i.e., $b_i^{\alpha, \circ}$ is adjacent only with all the vertices in $A_i^\alpha$, and all the vertices in $A_i^\alpha$ are adjacent with $v_i^\alpha$ in validation portal $V^\alpha$. Gray lines also indicate adjacencies with respect to indexing, but in a complementary way. If $C_q$ contains a variable in $B_i^\alpha$, then $c_q^{\circ}$ and $c_q^*$ are adjacent with all vertices $v_j^\alpha \in V^\alpha$ such that $j \neq i$. Green and red lines between the $A^\alpha$ and $T^\alpha$ and $F^\alpha$ roughly transfer, for each $a_{i,\ell}^\alpha \in A^\alpha$, the underlying assignment structure. If the $j^{th}$ variable by $a_{i,\ell}^\alpha$ is assigned to True, then we add the green edge $(a_{i,\ell}^\alpha, t_j^\alpha)$, and otherwise the red edge $(a_{i,\ell}^\alpha, f_j^\alpha)$. Similarly, we add edges for each $c_i^\circ \in C$ depending on the assignment satisfying the variable from the part $X^\delta$ of a clause $c_i$, and in which block $B_j^\delta$ it lies, putting either an edge $(c_i^\circ, t_j^\delta)$ or $(c_i^\circ, f_j^\delta)$ accordingly ($\delta \in \{\alpha, \beta, \gamma\}$).</figcaption></figure>

We give an informal description of the proof of correctness here. See Figure 3. Suppose $\sqrt{N} = 3$ and the vertices in the sets are indexed from top to bottom. For legibility, we omit some edges and only show 4 out of 8 vertices in each $A_i^\alpha$ for $i \in [3]$. We also omit bit-rep and nullifier for these sets. The vertex selection gadget and the budget $k$ ensure that exactly one vertex in $\{b_i^{\alpha, \circ}, b_i^{\alpha, *}\} \cup A_i^\alpha$ is selected for every $i \in [3]$. If a resolving set contains a vertex from $A_i^\alpha$, then it corresponds to selecting an assignment of variables in $X_i^\alpha$. For example, the vertex $a_{2,2}^\alpha$ corresponds to the assignment $\pi: X_2^\alpha \mapsto \{\text{True}, \text{False}\}$. Suppose $X_2^\alpha = \{x_{2,1}^\alpha, x_{2,2}^\alpha, x_{2,3}^\alpha\}$, $\pi(x_{2,1}^\alpha) = \pi(x_{2,3}^\alpha) = \text{True}$, and $\pi(x_{2,2}^\alpha) = \text{False}$. Hence, $a_{2,2}^\alpha$ is adjacent to the first and third vertex in the truth portal $T^\alpha$, whereas it is adjacent with the second vertex in the false portal $F^\alpha$. Suppose the clause $C_q$ contains the variable $x_{2,1}^\alpha$ as a positive literal. Note that $c_q^{\circ}$ and $c_q^*$ are at distance 2 and 3, respectively, from $a_{2,2}^\alpha$. Hence, the vertex $a_{2,2}^\alpha$, corresponding to the assignment $\pi$ that satisfies clause $C_q$, resolves the critical pair $\langle c_q^{\circ}, c_q^* \rangle$. Now, suppose there is another assignment $\sigma: X_3^\alpha \mapsto \{\text{True}, \text{False}\}$ such that $\sigma(x_{3,1}^\alpha) = \sigma(x_{3,3}^\alpha) = \text{True}$ and $\sigma(x_{3,2}^\alpha) = \text{False}$. As $\psi$ is an instance of 3-PARTITIONED-3-SAT and $C_q$ contains a variable in $X_2^\alpha$ ($\subseteq X^\alpha$), $C_q$ does not contain a variable in $X_3^\alpha$ ($\subseteq X^\alpha$). Hence, $\sigma$ does not satisfy $C_q$. Let $a_{3,2}^\alpha$ be the vertex in $X_3^\alpha$ corresponding to $\sigma$. The connections via the validation portal $V^\alpha$ ensure that both $c_q^{\circ}$ and $c_q^*$ are at distance 2 from $a_{3,2}^\alpha$, and hence, $a_{3,2}^\alpha$ cannot resolve the critical pair $\langle c_q^{\circ}, c_q^* \rangle$. Hence, finding a resolving set in $G$ corresponds to finding a satisfying assignment for $\psi$. These intuitions are formalized in the following subsection.
<figure><img src="image_7.png" /><figcaption>Figure 3 An example to illustrate the reduction (bit-rep and nullifier are omitted for the sets).</figcaption></figure>

## 4.3 Correctness of the Reduction

Suppose, given an instance $\psi$ of 3-PARTITIONED-3-SAT, that the reduction of this subsection returns $(G, k)$ as an instance of METRIC DIMENSION. We first prove the following lemma which will be helpful in proving the correctness of the reduction.

**Lemma 9.** For any resolving set $S$ of $G$ and for all $X \in \{C\} \cup \{B^\delta, A^\delta, P^\delta \mid \delta \in \{\alpha, \beta, \gamma\}\}$,

1. $S$ contains at least one vertex from each pair of false twins in $\text{bits}(X)$.

2. Vertices in $\text{bits}(X) \cap S$ resolve any non-critical pair of vertices $\langle u, v \rangle$ when $u \in X \cup X^+$ and $v \in V(G)$.

3. Vertices in $X^+ \cap S$ cannot resolve any critical pair of vertices $\langle b_i^{\delta', \circ}, b_i^{\delta', *} \rangle$ nor $\langle c_q^\circ, c_q^* \rangle$ for all $i \in [\sqrt{N}], \delta' \in \{\alpha, \beta, \gamma\}$, and $q \in [m]$.

### Proof.

1. Let $G$ be a graph. For any false twins $u, v \in V(G)$ and any $w \in V(G) \setminus \{u, v\}$, $d(u, w) = d(v, w)$, and so, for any resolving set $S$ of $G$, $S \cap \{u, v\} \neq \emptyset$. Hence, the statement follows for all $X \in \{C\} \cup \{B^\delta, A^\delta, P^\delta \mid \delta \in \{\alpha, \beta, \gamma\}\}$.

2. For all $X \in \{C\} \cup \{B^\delta, A^\delta, P^\delta \mid \delta \in \{\alpha, \beta, \gamma\}\}$, nullifier($X$) is distinguished by $\text{bits}(X) \cap S$ as it is the only vertex in $G$ at distance 2 from each vertex in $\text{bits}(X)$. We do a case analysis for the remaining non-critical pairs of vertices $\langle u, v \rangle$ assuming that nullifier($X$) $\notin \{u, v\}$ (also, suppose that neither $u$ nor $v$ is in $S$, as otherwise, they are obviously distinguished):
**Case i:** $u, v \in X \cup X^+$.

**Case i(a):** $u, v \in X$ or $u, v \in \text{bit-rep}(X) \setminus \text{bits}(X)$. In the first case, let $j$ be the bit in the binary representation of the subscript of $u$ that is not equal to the $j^{\text{th}}$ bit in the binary representation of the subscript of $v$ (such a $j$ exists since $\langle u, v \rangle$ is not a critical pair). In the second case, without loss of generality, let $u = y_i$ and $v = y_j$. By the first item of the statement of the lemma (1.), without loss of generality, $y_j^a \in S \cap \text{bits}(X)$. Then, in both cases, $d(y_j^a, u) \neq d(y_j^a, v)$.

**Case i(b):** $u \in X$ and $v \in \text{bit-rep}(X)$. Without loss of generality, $y_\star^a \in S \cap \text{bits}(X)$ (by 1.). Then, $d(y_\star^a, u) = 2$ and, for all $v \in \text{bits}(X) \setminus \{y_\star^b\}$, $d(y_\star^a, v) = 3$. Without loss of generality, let $y_i$ be adjacent to $u$ and let $y_i^a \in S \cap \text{bits}(X)$ (by 1.). Then, for $v = y_\star^b$, $3 = d(y_i^a, v) \neq d(y_i^a, u) = 2$. If $v \in \text{bit-rep}(X) \setminus \text{bits}(X)$, then, without loss of generality, $v = y_j$ and $y_j^a \in S \cap \text{bits}(X)$ (by 1.), and $1 = d(y_j^a, v) < d(y_j^a, u)$.

**Case i(c):** $u, v \in \text{bits}(X)$. Without loss of generality, $u = y_i^b$ and $y_i^a \in S$ (by 1.). Then, $2 = d(y_i^a, u) \neq d(y_i^a, v) = 3$.
**Case i(d):** $u \in \text{bits}(X)$ and $v \in \text{bit-rep}(X) \setminus \text{bits}(X)$. Without loss of generality, $v = y_i$ and $y_i^a \in S$ (by 1.). Then, $1 = d(y_i^a, v) < d(y_i^a, u)$.

**Case ii:** $u \in X \cup X^+$ and $v \in V(G) \setminus (X \cup X^+)$. For each $u \in X \cup X^+$, there exists $w \in \text{bits}(X) \cap S$ such that $d(u, w) \le 2$, while, for each $v \in V(G) \setminus (X \cup X^+) \text{ and } w \in \text{bits}(X) \cap S$, we have $d(v, w) \ge 3$.

3. For all $X \in \{B^\delta, A^\delta, P^\delta \mid \delta \in \{\alpha, \beta, \gamma\}\}$, $u \in X^+$, $v \in \{c_q^\circ, c_q^*\}$, and $q \in [m]$, we have that $d(u, v) = d(u, \text{nullifier}(P^\delta)) + 1$. Further, for $X = C$ and all $u \in X^+$ and $q \in [m]$, either $d(u, c_q^\circ) = d(u, c_q^*) = 1$, $d(u, c_q^\circ) = d(u, c_q^*) = 2$, or $d(u, c_q^\circ) = d(u, c_q^*) = 3$ by the construction in Subsection 4.1.2 and since $\text{bit-rep}(X) \setminus \text{bits}(X)$ is a clique. Hence, for all $X \in \{C\} \cup \{B^\delta, A^\delta, P^\delta \mid \delta \in \{\alpha, \beta, \gamma\}\}$, vertices in $X^+ \cap S$ cannot resolve a pair of vertices $\langle c_q^\circ, c_q^* \rangle$ for any $q \in [m]$.

For all $\delta \in \{\alpha, \beta, \gamma\}$, if $v \in B^\delta$, then, for all $X \in \{C\} \cup \{B^{\delta'}, A^{\delta'}, P^{\delta'} \mid \delta' \in \{\alpha, \beta, \gamma\}\}$ such that $\delta \neq \delta'$, and $u \in X^+$, we have that $d(u, v) = d(u, \text{nullifier}(A^\delta)) + 1$. Similarly, for all $\delta \in \{\alpha, \beta, \gamma\}$, if $v \in B^\delta$, then, for all $X \in \{A^\delta, P^\delta\}$ and $u \in X^+$, we have that $d(u, v) = d(u, \text{nullifier}(A^\delta)) + 1$. Lastly, for each $\langle b_i^{\delta, \circ}, b_i^{\delta, *} \rangle$, $\delta \in \{\alpha, \beta, \gamma\}$, and $i \in [\sqrt{N}]$, if $X = B^\delta$, then, for all $u \in X^+$, either $d(u, b_i^{\delta, \circ}) = d(u, b_i^{\delta, *}) = 1$, $d(u, b_i^{\delta, \circ}) = d(u, b_i^{\delta, *}) = 2$, or $d(u, b_i^{\delta, \circ}) = d(u, b_i^{\delta, *}) = 3$ by the construction in Subsection 4.1.2 and since $\text{bit-rep}(X) \setminus \text{bits}(X)$ is a clique. ◀

**Lemma 10.** If $\psi$ is a satisfiable 3-PARTITIONED-3-SAT formula, then $G$ admits a resolving set of size $k$.

**Lemma 11.** If $G$ admits a resolving set of size $k$, then $\psi$ is a satisfiable 3-PARTITIONED-3-SAT formula.

**Proof of Theorem 6.** In Subsection 4.2, we presented a reduction that takes an instance $\psi$ of 3-PARTITIONED-3-SAT and returns an equivalent instance $(G, k)$ of METRIC DIMENSION (by Lemmas 10 and 11) in $2^{O(\sqrt{N})}$ time, where

$$k = 3 \cdot \left( \sqrt{N} + (\lceil \log(|B^\alpha|/2 + 2) \rceil + 1) + (\lceil \log(|A^\alpha| + 2) \rceil + 1) + (\lceil \log(|P^\alpha| + 2) \rceil + 1) \right) + (\lceil \log(|C|/2 + 2) \rceil + 1) = \mathcal{O}(\sqrt{N}).$$

Note that $V(G) = 2^{O(\sqrt{N})}$. Further, note that taking all the vertices in $B^\delta$ and $P^\delta$ for all $\delta \in \{\alpha, \beta, \gamma\}$, and $X^+ \setminus \text{bits}(X)$ for all $X \in \{C\} \cup \{B^\delta, A^\delta, P^\delta \mid \delta \in \{\alpha, \beta, \gamma\}\}$, results in a vertex cover of $G$. Hence,

$$\text{vc}(G) \le 3 \cdot ( (\lceil \log(|B^\alpha|/2 + 2) \rceil + 2) + (\lceil \log(|A^\alpha| + 2) \rceil + 2) + (\lceil \log(|P^\alpha| + 2) \rceil + 2) + 3 \cdot (|B^\alpha| + |P^\alpha|) + (\lceil \log(|C|/2 + 2) \rceil + 2) = \mathcal{O}(\sqrt{N}).$$

$$\text{Thus, } \text{vc}(G) + k = \mathcal{O}(\sqrt{N}). \quad \blacksquare$$

# 5 Geodetic Set: Algorithms for Vertex Cover Parameterization

To prove Theorem 1 for GEODETIC SET, we start with the following fact about false twins.

**Lemma 12.** If a graph $G$ contains a set $T$ of false twins that are not true twins and not simplicial, then any minimum-size geodetic set contains at most four vertices of $T$.

**Proof.** Let $T = \{t_1, \dots, t_h\}$ be a set of false twins in a graph $G$, that are not true twins and not simplicial. Thus, $T$ forms an independent set, and there are two non-adjacent vertices $x, y$ in the neighborhood of the vertices in $T$. Toward a contradiction, assume that $h \ge 5$
and $G$ has a minimum-size geodetic set $S$ that contains at least five vertices of $T$; without loss of generality, assume $\{t_1, \dots, t_5\} \subseteq S$. We claim that $S' = (S \setminus \{t_1, t_2, t_3\}) \cup \{x, y\}$ is still a geodetic set, contradicting the choice of $S$ as a minimum-size geodetic set of $G$.

To see this, notice that any vertex from $V(G) \setminus T$ that is covered by some pair of vertices in $T \cap S$ is also covered by $t_4$ and $t_5$. Similarly, any vertex from $V(G) \setminus T$ covered by some pair $\langle t_i, z \rangle$ in $(S \cap T) \times (S \setminus T)$, is still covered by $t_4$ and $z$. Moreover, $x$ and $y$ cover all vertices of $T$, since they are at distance 2 from each other and all vertices in $T$ are their common neighbors. Thus, $S'$ is a geodetic set, as claimed. ◀

**Lemma 13.** *GEODETIC SET*, parameterized by the vertex cover number $\mathbf{vc}$, admits a polynomial-time kernelization algorithm that returns an instance with $2^{O(\mathbf{vc})}$ vertices.

*Proof.* Given a graph $G$, let $X \subseteq V(G)$ be a minimum-size vertex cover of $G$. If this vertex cover is not given, then we can find a 2-factor approximate vertex cover in polynomial time. Let $I := V(G) \setminus X$; $I$ forms an independent set. The kernelization algorithm exhaustively applies the following reduction rules in a sequential manner.

▷ Reduction Rule 2. If there exist three simplicial vertices in $G$ that are false twins or true twins, then delete one of them from $G$ and decrease $k$ by one.

▷ Reduction Rule 3. If there exist six vertices in $G$ that are false twins but are not true twins nor simplicial, then delete one of them from $G$.

To see that Reduction Rule 2 is correct, assume that $G$ contains three simplicial vertices $u, v, w$ that are twins (false or true). We show that $G$ has a geodetic set of size $k$ if and only if the reduced graph $G'$, obtained from $G$ by deleting $u$, has a geodetic set of size $k-1$. For the forward direction, let $S$ be a geodetic set of $G$ of size $k$. By Observation 3, $S$ contains each of $u, v, w$. Now, let $S' = S \setminus \{u\}$. This set of size $k-1$ is a geodetic set of $G'$. Indeed, any vertex of $G'$ that was covered in $G$ by $u$ and some other vertex $z$ of $S$, is also covered by $v$ and $z$ in $G'$. Conversely, if $G'$ has a geodetic set $S''$ of size $k-1$, then it is clear that $S'' \cup \{u\}$ is a geodetic set of size $k$ in $G$.

For Reduction Rule 3, assume that $G$ contains six false twins (that are not true twins nor simplicial) as the set $T = \{t_1, \dots, t_6\}$, and let $G'$ be the reduced graph obtained from $G$ by deleting $t_1$. We show that $G$ has a geodetic set of size $k$ if and only if $G'$ has a geodetic set of size $k$. For the forward direction, let $S$ be a minimum-size geodetic set of size (at most) $k$ of $G$. By Lemma 12, $S$ contains at most four vertices from $T$; without loss of generality, $t_1$ and $t_2$ do not belong to $S$. Since the distances among all pairs of vertices in $G'$ are the same as in $G$, $S$ is still a geodetic set of $G'$. Conversely, let $S'$ be a minimum-size geodetic set of $G'$ of size (at most) $k$. Again, by Lemma 12, we may assume that one vertex among $t_2, \dots, t_6$ is not in $S'$, say, without loss of generality, that it is $t_2$. Note that $S'$ covers (in $G$) all vertices of $G'$. Thus, $t_2$ is covered by two vertices $x, y$ of $S'$. But then, $t_1$ is also covered by $x$ and $y$, since we can replace $t_2$ by $t_1$ in any shortest path between $x$ and $y$. Hence, $S'$ is also a geodetic set of $G$.

Now, consider an instance on which the reduction rules cannot be applied. If $k < 0$, then we return a trivial No-instance (for example, a single-vertex graph). Otherwise, notice that any set of false twins in $I$ contains at most five vertices. Hence, $G$ has at most $|X| + 5 \cdot 2^{|X|} = 2^{O(\mathbf{vc})}$ vertices. ◀

Next, we present an XP-algorithm parameterized by the vertex cover number. Together with Lemma 13, they imply Theorem 1 for GEODETIC SET.

**Lemma 14.** *GEODETIC SET* admits an algorithm running in $n^{O(\mathbf{vc})}$ time.
**Proof.** The algorithm starts by computing a minimum vertex cover $X$ of $G$ in $2^{O(\mathrm{vc})} \cdot n^{O(1)}$ time using an FPT algorithm for the VERTEX COVER problem, for example the one in [11] or [27]. Let $I := V(G) \setminus X$.

In polynomial time, we compute the set $S$ of simplicial vertices of $G$. By Observation 3, any geodetic set of $G$ contains all simplicial vertices of $G$. Note that $X \cup S$ is a geodetic set of $G$. Indeed, any vertex $v$ from $I$ that is not simplicial has two non-adjacent neighbors $x, y$ in $X$, and thus, $v$ is covered by $x$ and $y$ (which are at distance 2 from each other).

Hence, to enumerate all possible minimum-size geodetic sets, it suffices to enumerate all subsets $S'$ of vertices of size at most $|X|$ in $(X \cup I) \setminus S$, and check whether $S \cup S'$ is a geodetic set. If one such set is indeed a geodetic set and has size at most $k$, we return YES. Otherwise, we return NO. The statement follows. ◀

# 6 Geodetic Set: Lower Bounds Regarding Vertex Cover

In this section, we follow the same template as in Section 4 and first prove the following theorem.

**▶ Theorem 15.** *There is an algorithm that, given an instance $\psi$ of 3-PARTITIONED-3-SAT on $N$ variables, runs in $2^{O(\sqrt{N})}$ time, and constructs an equivalent instance $(G, k)$ of GEODETIC SET such that $\mathrm{vc}(G) + k = O(\sqrt{N})$ (and $|V(G)| = 2^{O(\sqrt{N})}$).*

The proofs of the following two corollaries are analogous to those for METRIC DIMENSION.

**▶ Corollary 16.** *Unless the ETH fails, GEODETIC SET does not admit an algorithm running in $2^{o(\mathrm{vc}^2)} \cdot n^{O(1)}$ time.*

**▶ Corollary 17.** *Unless the ETH fails, GEODETIC SET does not admit a kernelization algorithm that does not increase the solution size $k$ and outputs a kernel with $2^{o(k+\mathrm{vc})}$ vertices.*

## 6.1 Reduction

Consider an instance $\psi$ of 3-PARTITIONED-3-SAT with $X^{\alpha}, X^{\beta}, X^{\gamma}$ the partition of the variable set, where $|X^{\alpha}| = |X^{\beta}| = |X^{\gamma}| = N$. By adding dummy variables in each of these sets, we can assume that $\sqrt{N}$ is an integer. Further, let $C = \{C_1, \dots, C_m\}$ be the set of all the clauses of $\psi$. From $\psi$, we construct the graph $G$ as follows. We describe the construction for the part of the graph $G$ corresponding to $X^{\alpha}$, with the parts corresponding to $X^{\beta}$ and $X^{\gamma}$ being analogous. We rename the variables in $X^{\alpha}$ to $x_{i,j}^{\alpha}$ for $i, j \in [\sqrt{N}]$.

- We partition the variables of $X^{\alpha}$ into buckets $X_1^{\alpha}, X_2^{\alpha}, \dots, X_{\sqrt{N}}^{\alpha}$ such that each bucket contains $\sqrt{N}$ many variables. Let $X_i^{\alpha} = \{x_{i,j}^{\alpha} \mid j \in [\sqrt{N}]\}$ for all $i \in [\sqrt{N}]$.

- For every bucket $X_i^{\alpha}$, we add an independent set $A_i^{\alpha}$ of $2^{\sqrt{N}}$ new vertices, and we add two isolated edges $(a_{i,1}^{\alpha}, b_{i,1}^{\alpha})$ and $(a_{i,2}^{\alpha}, b_{i,2}^{\alpha})$. Let $B^{\alpha} = \{a_{i,j}^{\alpha}, b_{i,j}^{\alpha} \mid i \in [\sqrt{N}], j \in \{1, 2\}\}$. For all $i \in [\sqrt{N}]$ and $u \in A_i^{\alpha}$, we make both $a_{i,1}^{\alpha}$ and $a_{i,2}^{\alpha}$ adjacent to $u$ (see Figure 4). Each vertex in $A_i^{\alpha}$ corresponds to a certain possible assignment of variables in $X_i^{\alpha}$.

- Then, we add three independent sets $T^{\alpha}, F^{\alpha}$, and $V^{\alpha}$ on $\sqrt{N}$ vertices each: $T^{\alpha} = \{t_i^{\alpha} \mid i \in [\sqrt{N}]\}, F^{\alpha} = \{f_i^{\alpha} \mid i \in [\sqrt{N}]\}, \text{ and } V^{\alpha} = \{v_i^{\alpha} \mid i \in [\sqrt{N}]\}$.

- For each $i \in [\sqrt{N}]$, we connect $v_i^{\alpha}$ with all the vertices in $A_i^{\alpha}$.

- For each $i \in [\sqrt{N}]$, we add edges between $A_i^{\alpha}$ and $T^{\alpha}$ and between $A_i^{\alpha}$ and $F^{\alpha}$ as follows. Consider a vertex $w \in A_i^{\alpha}$. Recall that this vertex corresponds to an assignment $\pi: X_i^{\alpha} \mapsto \{\text{True}, \text{False}\}$, where $X_i^{\alpha}$ is the collection of variables $\{x_{i,j}^{\alpha} \mid j \in [\sqrt{N}]\}$. If $\pi(x_{i,j}^{\alpha}) = \text{True}$, then we add the edge $(w, t_j^{\alpha})$, and otherwise, we add the edge $(w, f_i^{\alpha})$.
<figure><img src="image_8.png" /><figcaption>**Figure 4** Overview of the reduction. Sets in ellipses are independent sets, and sets in rectangles are cliques. For each $\delta \in \{\alpha, \beta, \gamma\}$, the sets $V^\delta$ and $U$ almost form a complete bipartite graph, except for the matching (marked by dotted edges) that is excluded. Yellow lines from a vertex to a set denote that this vertex is connected to all the vertices in that set. The green and red lines between the $A_i^\alpha$ and $T^\alpha \cup F^\alpha$ transfer, in some sense, for each $w \in A_i^\alpha$, the underlying assignment structure. If an underlying assignment $w$ sets the $j^{th}$ variable to **True**, then we add the green edge $(w, t_j^\alpha)$, and otherwise, we add the red edge $(w, f_j^\delta)$. For all $q \in [m]$ and $\delta \in \{\alpha, \beta, \gamma\}$, let $x_{i,j}^\delta$ be the variable in $X^\delta$ that is contained in the clause $C_q$ in $\psi$. So, for all $q \in [m]$, if assigning **True** (**False**, respectively) to $x_{i,j}^\delta$ satisfies $C_q$, then we add the edge $(c_q, t_j^\delta)$ ($(c_q, f_j^\delta)$, respectively).</figcaption></figure>

For each $i \in [\sqrt{N}]$, we add a special vertex $g_i^\alpha$ (also referred to as a $g$-vertex later on) that is adjacent to each vertex in $T^\alpha \cup F^\alpha$. Further, $g_i^\alpha$ is also adjacent to both $a_{i,1}^\alpha$ and $a_{i,2}^\alpha$ (see Figure 4).

This finishes the first part of the construction. The second step is to connect the three previously constructed parts for $X^\alpha$, $X^\beta$, and $X^\gamma$.

We introduce a vertex set $U = \{u_i \mid i \in [\sqrt{N}]\}$ that forms a clique. Then, for each $u_i$, we add an edge to a new vertex $u'_i$. Thus, we have a matching $\{(u_i, u'_i) \mid i \in [\sqrt{N}]\}$. Let $U' = \{u'_i \mid i \in [\sqrt{N}]\}$.

For each $\delta \in \{\alpha, \beta, \gamma\}$, we add edges so that the vertices of $U \cup V^\delta$ almost form a complete bipartite graph, i.e., $E(G)$ contains edges between all pairs $(v, w)$ where $v \in U$ and $w \in V^\delta$, except for the matching $\{(v_i^\delta, u_i) \mid i \in [\sqrt{N}]\}$.

For each $\delta \in \{\alpha, \beta, \gamma\}$ and $i \in [\sqrt{N}]$, we make $g_i^\delta$ adjacent to each vertex in $U$.

For each $C_q \in \mathcal{C}$, we add a new vertex $c_q$. Let $C = \{c_q \mid q \in [m]\}$. Since we are considering an instance of 3-PARTITIONED-3-SAT, for each $\delta \in \{\alpha, \beta, \gamma\}$, there is at most one variable in $C_q$ that lies in $X^\delta$. If there is one, then without loss of generality, let it be $x_{i,j}^\delta$ and do the following. Make $c_q$ adjacent to $u_i$ and if $x_{i,j}^\delta = \text{True}$ ($x_{i,j}^\delta = \text{False}$, respectively) satisfies $C_q$, then $(c_q, t_j^\delta) \in E(G)$ ($(c_q, f_j^\delta) \in E(G)$, respectively).

This concludes the construction of $G$. The reduction returns $(G, k)$ as an instance of GEODETIC SET where $k = 10\sqrt{N}$.
## 6.2 Correctness of the Reduction

Suppose, given an instance $\psi$ of 3-PARTITIONED-3-SAT, that the reduction above returns $(G, k)$ as an instance of GEODETIC SET. We first prove the following lemmas which will be helpful in proving the correctness of the reduction, and note that we use distances between vertices to prove that certain vertices are not contained in shortest paths.

**Lemma 18.** For all $\delta, \delta' \in \{\alpha, \beta, \gamma\}$, the shortest paths between any two vertices in $B^\delta \cup U \cup U'$ do not cover any vertices in $C$ nor $V^{\delta'}$.

**Lemma 19.** For all $i \in [\sqrt{N}]$ and $\delta \in \{\alpha, \beta, \gamma\}$, $v_i^\delta$ can only be covered by a shortest path from a vertex in $A_i^\delta \cup \{v_i^\delta\}$ to another vertex in $G$.

**Lemma 20.** If $G$ admits a geodetic set of size $k$, then $\psi$ is a satisfiable 3-PARTITIONED-3-SAT formula.

**Lemma 21.** If $\psi$ is a satisfiable 3-PARTITIONED-3-SAT formula, then $G$ admits a geodetic set of size $k$.

**Proof of Theorem 15.** In Section 6.1, we presented a reduction that takes an instance $\psi$ of 3-PARTITIONED-3-SAT and returns an equivalent instance $(G, k)$ of GEODETIC SET (by Lemmas 20 and 21) in $2^{O(\sqrt{N})}$ time, where $k = 10\sqrt{N}$. Note that $V(G) = 2^{O(\sqrt{N})}$. Further, note that taking all the vertices in $B^\delta, V^\delta, T^\delta, F^\delta, U, C$, and $g_i^\delta$ for all $i \in [\sqrt{N}]$ and $\delta \in \{\alpha, \beta, \gamma\}$, results in a vertex cover of $G$. Hence,

$$ \mathrm{vc}(G) \le 3 \cdot (|B^\alpha| + |V^\alpha| + |T^\alpha| + |F^\alpha| + \sqrt{N}) + |U| + |C| = \mathcal{O}(\sqrt{N}). $$

$$ \text{Thus, } \mathrm{vc}(G) + k = \mathcal{O}(\sqrt{N}). $$

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

# 7 Conclusion

We have seen that both METRIC DIMENSION and GEODETIC SET have a non-trivial $2^{\Theta(\mathrm{vc}^2)}$ running-time dependency (unless the ETH fails) in the vertex cover number parameterization. Both problems are FPT for related parameters, such as vertex integrity, treedepth, distance to (co-)cluster, distance to cograph, etc., as more generally, they are FPT for cliquewidth plus diameter [23, 31]. For both problems, it was proved that the correct dependency in treedepth (and treewidth plus diameter) is in fact double-exponential [20], a fact that is also true for feedback vertex set plus diameter for METRIC DIMENSION [20]. For distance to (co-)cluster, algorithms with double-exponential dependency were given for METRIC DIMENSION in [21]. For the parameter max leaf number $\ell$, the algorithm for METRIC DIMENSION from [17] uses ILPs, with a dependency of the form $2^{O(\ell^6 \log \ell)}$ (a similar algorithm for GEODETIC SET with dependency $2^{O(f \log f)}$ exists for the feedback edge set number $f$ [31]), which is unknown to be tight. What is the correct dependency for all these parameters? In particular, it seems interesting to determine for which parameter(s) the jump from double-exponential to single-exponential dependency occurs.

For the related problem STRONG METRIC DIMENSION, the correct dependency in the vertex cover number is known to be double-exponential [20]. It would be nice to determine whether similarly intriguing behaviors can be exhibited for related metric-based problems, such as STRONG GEODETIC SET, whose parameterized complexity was recently addressed in [16, 34]. Perhaps our techniques are applicable to such related problems.
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. doi:10.1145/3319909.

2 R. Belmonte, F. V. Fomin, P. A. Golovach, and M. S. Ramanujan. Metric dimension of bounded tree-length graphs. *SIAM J. Discrete Math.*, 31(2):1217–1243, 2017. doi:10.1137/16M1057383.

3 B. Bergougnoux, O. Defrain, and F. Mc Inerney. Enumerating minimal solution sets for metric graph problems. In *Proc. of the 50th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2024)*, volume 14760 of *Lecture Notes in Computer Science*, pages 50–64. Springer, 2024.

4 E. Bonnet and N. Purohit. Metric dimension parameterized by treewidth. *Algorithmica*, 83:2606–2633, 2021. doi:10.1007/S00453-021-00808-9.

5 N. Bousquet, Q. Deschamps, and A. Parreau. Metric dimension parameterized by treewidth in chordal graphs. In *Proc. of the 49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023)*, volume 14093 of *Lecture Notes in Computer Science*, pages 130–142. Springer, 2023. doi:10.1007/978-3-031-43380-1_10.

6 D. Chakraborty, S. Das, F. Foucaud, H. Gahlawat, D. Lajou, and B. Roy. Algorithms and complexity for geodetic sets on planar and chordal graphs. In *Proc. of the 31st International Symposium on Algorithms and Computation (ISAAC 2020)*, volume 181 of *LIPIcs*, pages 7:1–7:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.ISAAC.2020.7.

7 D. Chakraborty, F. Foucaud, D. Majumdar, and P. Tale. Tight (double) exponential bounds for identification problems: Locating-dominating set and test cover. In *Proc. of the 35th International Symposium on Algorithms and Computation (ISAAC 2024)*, volume 322 of *LIPIcs*, pages 19:1–19:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.ISAAC.2024.19.

8 J. Chalopin, V. Chepoi, F. Mc Inerney, and S. Ratel. Non-clashing teaching maps for balls in graphs. In *Proc. of the 37th Annual Conference on Learning Theory (COLT 2024)*, volume 247 of *Proceedings of Machine Learning Research*, pages 840–875. PMLR, 2024. URL: https://proceedings.mlr.press/v247/chalopin24a.html.

9 L. S. Chandran, D. Issac, and A. Karrenbauer. On the parameterized complexity of biclique cover and partition. In *Proc. of the 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. doi:10.4230/LIPICS.IPEC.2016.11.

10 G. Chartrand, F. Harary, and P. Zhang. On the geodetic number of a graph. *Networks*, 39(1):1–6, 2002. doi:10.1002/NET.10007.

11 J. Chen, I. A. Kanj, and W. Jia. Vertex cover: Further observations and further improvements. *J. Algorithms*, 41(2):280–301, 2001. doi:10.1006/JAGM.2001.1186.

12 M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. *Parameterized Algorithms*. Springer, 2015.

13 M. Cygan, M. Pilipczuk, and M. Pilipczuk. Known algorithms for edge clique cover are probably optimal. *SIAM J. Comput.*, 45(1):67–83, 2016. doi:10.1137/130947076.

14 R. Diestel. *Graph Theory, 6th Edition*, volume 173 of *Graduate texts in mathematics*. Springer, 2024.

15 M. C. Dourado, F. Protti, D. Rautenbach, and J. L. Szwarcfiter. Some remarks on the geodetic number of a graph. *Discrete Mathematics*, 310(4):832–837, 2010. doi:10.1016/J.DISC.2009.09.018.

16 M. Dumas, F. Foucaud, A. Perez, and I. Todinca. On graphs coverable by $k$ shortest paths. *SIAM J. Discrete Math.*, 38(2):1840–1862, 2024. doi:10.1137/23M1564511.

17 D. Eppstein. Metric dimension parameterized by max leaf number. *Journal of Graph Algorithms and Applications*, 19(1):313–323, 2015. doi:10.7155/JGAA.00360.

18 L. Epstein, A. Levin, and G. J. Woeginger. The (weighted) metric dimension of graphs: Hard and easy cases. *Algorithmica*, 72(4):1130–1171, 2015. doi:10.1007/S00453-014-9896-2.
19 F. Foucaud, E. Galby, L. Khazaliya, S. Li, F. Mc Inerney, R. Sharma, and P. Tale. Metric dimension and geodetic set parameterized by vertex cover. CoRR, abs/2405.01344, 2024. doi:10.48550/arXiv.2405.01344.

20 F. Foucaud, E. Galby, L. Khazaliya, S. Li, F. Mc Inerney, R. Sharma, and P. Tale. Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. In Proc. of the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of LIPIcs, pages 66:1–66:19. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.ICALP.2024.66.

21 E. Galby, L. Khazaliya, F. Mc Inerney, R. Sharma, and P. Tale. Metric dimension parameterized by feedback vertex set and other structural parameters. SIAM J. Discrete Math., 37(4):2241–2264, 2023. doi:10.1137/22M1510911.

22 M. R. Garey and D. S. Johnson. *Computers and Intractability - A guide to NP-completeness*. W.H. Freeman and Company, 1979.

23 T. Gima, T. Hanaka, M. Kiyomi, Y. Kobayashi, and Y. Otachi. Exploring the gap between treedepth and vertex cover through vertex integrity. *Theoretical Comp. Sci.*, 918:60–76, 2022. doi:10.1016/J.TCS.2022.03.021.

24 G. Z. Gutin, M. S. Ramanujan, F. Reidl, and M. Wahlström. Alternative parameterizations of metric dimension. *Theoretical Comp. Sci.*, 806:133–143, 2020. doi:10.1016/J.TCS.2019.01.028.

25 F. Harary, E. Loukakis, and C. Tsouros. The geodetic number of a graph. *Mathematical and Computer Modelling*, 17(11):89–95, 1993.

26 F. Harary and R. A. Melter. On the metric dimension of a graph. *Ars Comb.*, 2:191–195, 1976.

27 D. G. Harris and N. S. Narayanaswamy. A faster algorithm for vertex cover parameterized by solution size. In Proc. of the 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), volume 289 of LIPIcs, pages 40:1–40:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.STACS.2024.40.

28 S. Hartung and A. Nichterlein. On the parameterized and approximation hardness of metric dimension. In Proc. of the 28th Conference on Computational Complexity, CCC 2013, pages 266–276. IEEE Computer Society, 2013. doi:10.1109/CCC.2013.36.

29 L. Jaffke, O.-J. Kwon, T. J. F. Strømme, and J. A. Telle. Mim-width III. Graph powers and generalized distance domination problems. *Theoretical Comp. Sci.*, 796:216–236, 2019. doi:10.1016/J.TCS.2019.09.012.

30 I. Katsikarelis, M. Lampis, and V. Th. Paschos. Structurally parameterized d-scattered set. *Discrete Applied Mathematics*, 308:168–186, 2022. doi:10.1016/J.DAM.2020.03.052.

31 L. Kellerhals and T. Koana. Parameterized complexity of geodetic set. *Journal of Graph Algorithms and Applications*, 26(4):401–419, 2022. doi:10.7155/JGAA.00601.

32 M. Lampis, N. Melissinos, and M. Vasilakis. Parameterized max min feedback vertex set. In Proc. of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), volume 272 of LIPIcs, pages 62:1–62:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPICS.MFCS.2023.62.

33 S. Li and M. Pilipczuk. Hardness of metric dimension in graphs of constant treewidth. *Algorithmica*, 84(11):3110–3155, 2022. doi:10.1007/S00453-022-01005-Y.

34 C. V. G. C. Lima, V. F. dos Santos, J. H. G. Sousa, and S. A. Urrutia. On the computational complexity of the strong geodetic recognition problem. *RAIRO Oper. Res.*, 58(5):3755–3770, 2024. doi:10.1051/RO/2024120.

35 D. Marx, M. Pilipczuk, and M. Pilipczuk. On subexponential parameterized algorithms for steiner tree and directed subset TSP on planar graphs. In Proc. of the 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2018), pages 474–484, 2018.

36 M. Pilipczuk. Problems parameterized by treewidth tractable in single exponential time: A logical approach. In Proc. of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS 2011), volume 6907 of Lecture Notes in Computer Science, pages 520–531. Springer, 2011. doi:10.1007/978-3-642-22993-0_47.
37 I. Sau and U. dos Santos Souza. Hitting forbidden induced subgraphs on bounded treewidth graphs. *Inf. Comput.*, 281:104812, 2021. doi:10.1016/J.IC.2021.104812.

38 P. J. Slater. Leaves of trees. In *Proc. of the 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing*, pages 549–559. Congressus Numerantium, No. XIV. Util. Math., 1975.

39 P. Tale. Double exponential lower bound for telephone broadcast. CoRR, abs/2403.03501, 2024. doi:10.48550/arXiv.2403.03501.