11institutetext: Univ. Lyon, Université Lyon 1, CNRS, LIRIS UMR 5205, F-69621,
Lyon, France.

# Metric dimension parameterized by treewidth in chordal graphs††thanks: This
work was supported by ANR project GrR (ANR-18-CE40-0032)

Nicolas Bousquet 11 Quentin Deschamps 11 Aline Parreau 11

###### Abstract

The metric dimension has been introduced independently by Harary, Melter
[HM75] and Slater [Sla75] in 1975 to identify vertices of a graph $G$ using
its distances to a subset of vertices of $G$. A _resolving set_ $X$ of a graph
$G$ is a subset of vertices such that, for every pair $(u,v)$ of vertices of
$G$, there is a vertex $x$ in $X$ such that the distance between $x$ and $u$
and the distance between $x$ and $v$ are distinct. The metric dimension of the
graph is the minimum size of a resolving set. Computing the metric dimension
of a graph is NP-hard even on split graphs and interval graphs.

Bonnet and Purohit [BP21] proved that the metric dimension problem is
W[1]-hard parameterized by treewidth. Li and Pilipczuk strenghtened this
result by showing that it is NP-hard for graphs of treewidth $24$ in [LP22].
In this article, we prove that that metric dimension is FPT parameterized by
treewidth in chordal graphs.

##  1 Introduction

Determining the position of an agent on a network is a central problem. One
way to determine his position is to place sensors on nodes of the network and
the agents try to determine their positions using their positions with respect
to these sensors. More formally, assume that the agent knows the topology of
the graph. Can he, by simply looking at his position with respect to the
sensors determine for sure his position in the network? Conversely, where do
sensors have to be placed to ensure that any agent at any possible position
can easily determine for sure its position? These questions received a
considerable attention in the last decades and have been studied in
combinatorics under different names such as metric dimension, identifying
codes, locating dominating sets…

Let $G=(V,E)$ be a graph and $s,u,v$ be three vertices of $G$. We say that $s$
_resolves_ the pair $(u,v)$ if the distance between $s$ and $u$ is different
from the distance between $s$ and $v$. A _resolving set_ of a graph $G=(V,E)$
is a subset $S$ of vertices of $G$ such that any vertex of $G$ is identified
by its distances to the vertices of the resolving set. In other words, $S$ is
a resolving set if for every pair $(u,v)$ of vertices of $G$, there is a
vertex $s$ of $S$ such that $s$ resolves $(u,v)$. The _metric dimension_ of
$G$, denoted by $\dim(G)$, is the smallest size of a resolving set of $G$.
This notion has been introduced in 1975 by Slater [Sla75] for trees and by
Harary and Melter [HM75] for graphs to simulate the moves of a sonar. The
_metric dimension_ of $G$ is the smallest size of a resolving set of $G$. The
associated decision problem, called the Metric Dimension problem, is defined
as follows: given a graph $G$ and an integer $k$, is the metric dimension of
$G$ is at most $k$?

The Metric Dimension problem is NP-complete [GJ79] even for restricted classes
of graphs like planar graphs [DPSvL12]. Epstein et al. [ELW15] proved that
this problem is NP-complete on split graphs, bipartite and co-bipartite
graphs. The problem also is NP-complete on interval graphs [FMN+17] or sub-
cubic graphs [HN13]. On the positive side, computing the metric dimension is
linear on trees [HM75, Sla75] and polynomial in outer-planar graphs [DPSvL12].

##### Parameterized algorithms.

In this paper, we consider the Metric Dimension problem from a parameterized
point of view. We say a problem $\Pi$ is _fixed parameter tractable_ (FPT) for
a parameter $k$ if any instance of size $n$ and parameter $k$ can be decided
in time $f(k)\cdot n^{O(1)}$. Two types of parameters received a considerable
attention in the litterature: the size of the solution and the ”width” of the
graph (for various widths, the most classical being the treewidth).

Hartung and Nichterlein proved in [HN13] that the Metric Dimension problem is
W[2]-hard parameterized by the size of the solution. Foucaud et al. proved
that it is FPT parameterized by the solution size in interval graphs in
[FMN+17]. This result was extended by Belmonte et al. who proved in [BFGR16]
that Metric Dimension is FPT parameterized by the size of the solution plus
the tree-length of the graph. In particular, it implies that computing the
metric dimension for chordal graph is FPT parameterized by the size of the
solution.

Metric Dimension is FPT paramerized by the modular width [BFGR16]. Using
Courcelle’s theorem, one can also remark that it is FPT paramerized by the
treedepth of the graph as observed in [GHK+22]. Metric dimension has been
proven W[1]-hard parameterized by the treewidth by Bonnet and Purohit in
[BP21]. Li and Pilipczuk strenghtened this result by showing that it is NP-
complete for graphs of treewidth, and even pathwidth, $24$ in [LP22]. While
Metric dimension is polynomial on graphs of treewidth $1$ (forests), its
complexity is unknown for graphs of treewidth $2$ is open (even if it is known
to be polynomial for outerplanar graphs). Our main result is the following:

###### Theorem 1.1

Metric Dimension is FPT parameterized by treewidth on chordal graphs. That is,
Metric Dimension can be decided in time $O(n^{3}+n^{2}\cdot f(\omega))$ on
chordal graphs of clique number $\omega$.

Recall that, on chordal graphs, the treewidth is equal to the size of a
maximum clique minus one. Our proof is based on a dynamic programming
algorithm. One of the main difficulty to compute the metric dimension is that
a pair of vertices might be resolved by a vertex far from them in the graph.
This non-locality, implies that it is not simple to use classical algorithmic
strategies like divide-and-conquer, induction or dynamic programming since a
single edge or vertex modification somewhere in the graph might change the
whole solution111The addition of a single edge in a graph might modify the
metric dimension by $\Omega(n)$, see e.g. [EFKY15]..

The first ingredient of our algorithm consists in proving that, given a
chordal graph, if we are using a clique tree of a desirable form and make some
simple assumptions on the shape of an optimal solution, we can ensure that
resolving a pairs of vertices close to a separator implies that we resolve all
the pairs of vertices in the graph. Using this lemma, we build a dynamic
programming algorithm that computes the minimum size of a resolving set
containing a given vertex in FPT-time parameterized by treewdith.

The special type of clique tree used in the paper, inspired from [Klo94], is
presented in Section 2.1. We then give some properties of resolving sets in
chordal graphs in Section 2.2. These properties will be needed to prove the
correction and the running time of the algorithm. Then, we present the
definition of the extended problem in Section 3.1 and the rules of the dynamic
programming in Section 3.2 where we also prove the correction of the
algorithm. We end by an analysis of the complexity of the algorithm in Section
4.

##### Further work.

The function of the treewidth in our algorithm is probbly not optimal and we
did not try to optimize it to keep the algorithm as simple as possible. A
first natural question is the existence of an algorithm running in time
$2^{\omega}\cdot Poly(n)$ for chordal graphs.

We know that Theorem 1.1 cannot be extended to bounded treewidth graphs since
Metric Dimension is NP-hard on graphs of treewidth at most $24$ [LP22]. One
can nevertheless wonder if our proof technique can be adapted to design
polynomial time algorithms for graphs of treewidth at most $2$ on which the
complexity status of Metric Dimension is still open.

Our proof nevertheless crucially relies on the fact that a separators $X$ of a
chordal graphs is a clique and then the way a vertex in a component of
$G\setminus X$ is interacting with vertices in another component of
$G\setminus X$ is simple. One can wonder if there is a tree decomposition in
$G$ where all the bags have diameter at most $C$, is it true that Metric
Dimension is FPT parameterized by the size of the bags plus $C$. Note that,
since Metric Dimension is NP-complete on chordal graphs, the problem is indeed
hard parameterized by the diameter of the bags only.

##  2 Preliminaries

###  2.1 Clique trees

Unless otherwise stated, all the graphs considered in this paper are
undirected, simple, finite and connected. For standard terminology and
notations on graphs, we refer the reader to [CLZ15]. Let us first define some
notations we use throughout the article.

Let $G=(V,E)$ be a graph where $V$ is the set of vertices of $G$ and $E$ the
set of edges; we let $n=|V|$. For two vertices $x$ and $y$ in $G$, we denote
by $d(x,y)$ the length of a shortest path between $x$ and $y$ and call it
_distance between $x$ and $y$_. For every $x\in V$ and $U\subseteq V$, the
_distance between $x$ and $U$_, denoted by $d(x,U)$, is the minimum distance
between $x$ and a vertex of $U$. Two vertices $x$ and $y$ are _adjacent_ if
$xy\in E$. A _clique_ is a graph where all the pairs of vertices are adjacent.
We denote by $\omega$ the size of a maximum clique. Let $U$ be a set of
vertices of $G$. We denote by $G\setminus U$ the subgraph of $G$ induced by
the set of vertices $V\setminus U$. We say that $U$ is a _separator_ of $G$ if
$G\setminus U$ is not connected. If two vertices $x$ and $y$ of $V\setminus U$
belong to two different connected components in $G^{\prime}$, we say that $U$
_separates_ $x$ and $y$. If the set $U$ induces a clique, we say that $U$ is a
_clique separator_ of $G$.

###### Definition 1

A _tree-decomposition_ of a graph $G$ is a pair $(X,T)$ where $T$ is a tree
and $X=\\{X_{i}|i\in V(T)\\}$ is a collection of subsets (called bags) of
$V(G)$ such that:

  * •

$\bigcup_{i\in V(T)}X_{i}=V(G)$.

  * •

For each edge $xy\in E(G),x,y\in X_{i}$ for some $i\in V(T)$.

  * •

For each $x\in V(G)$, the set $\\{i|x\in X_{i}\\}$ induces a connected sub-
tree of $T$.

Let $G$ be a graph and $(X,T)$ a tree decomposition of $G$. The _width_ of the
tree-decomposition $(X,T)$ is the biggest size of a bag minus one. The
_treewidth_ of $G$ is the smallest width of $(X,T)$ amongst all the tree-
decompositions $(X,T)$ of $G$.

Chordal graphs are graphs with no induced cycle of length at least $4$. A
characterization given by Dirac in [Dir61] ensures chordal graphs are graphs
where minimal vertex separators are cliques. Chordal graphs admit clique trees
which are tree-decompositions such that all the bags are cliques.

Our dynamic programming algorithm is performed in a bottom-up on a clique tree
of the graph with more properties than the ones given by Definition 1. These
properties permits to simplify the analysis of the algorithm. We adapt the
decomposition of [Klo94, Lemma 13.1.2] to get this tree-decomposition.

###### Lemma 2

Let $G=(V,E)$ be a chordal graph. There exists a clique tree $(X,T)$ of $G$
such that, (i) $T$ is a rooted tree that contains at most $4n$ nodes, (ii) for
every bag $i\in V(T)$, the set of vertices $X_{i}$ induces a clique in $G$ and
(iii) $T$ contains four types of nodes which are:

  * •

Leaf nodes which satisfy $|X_{i}|=1$ or,

  * •

Introduce nodes $i$ which have exactly one child $j$, and that child satisfies
$X_{i}=X_{j}\cup\\{v\\}$ for some vertex $v\in V(G)\setminus X_{j}$ or,

  * •

Forget nodes $i$ which have exactly one child $j$, and that child satisfies
$X_{i}=X_{j}\setminus\\{v\\}$ for some vertex $v\in X_{j}$ or,

  * •

Join node $i$ which have exactly two children $i_{1}$ and $i_{2}$ satisfying
$X_{i}=X_{i_{1}}=X_{i_{2}}$.

Moreover, such a clique tree can be found in linear time.

The original proof uses $k$-trees instead of chordal graphs but the proof only
needs that the graph contains a simplicial vertex which holds for chordal
graphs. Let us define now our clique tree in which the root of the tree is
fixed.

###### Lemma 3

Let $G=(V,E)$ be a chordal graph and $r$ a vertex of $G$, then there exists a
clique tree $(X,T)$ such that, $T$ contains at most $7n$ nodes, $T$ is rooted
in a node that contains only the vertex $r$, for every bag $i\in V(T)$, the
set of vertices $X_{i}$ induces a clique in $G$ and $T$ contains four types of
nodes.

  * •

Leaf nodes, $|X_{i}|=1$ which have no child.

  * •

Introduce nodes $i$ which have exactly one child $j$, and that child satisfies
$X_{i}=X_{j}\cup\\{v\\}$ for some vertex $v\in V(G)\setminus X_{j}$.

  * •

Forget nodes $i$ which have exactly one child $j$, and that child satisfies
$X_{i}=X_{j}\setminus\\{v\\}$ for some vertex $v\in X_{j}$.

  * •

Join node $i$ which have exactly two children $i_{1}$ and $i_{2}$, and that
children satisfy $X_{i}=X_{i_{1}}=X_{i_{2}}$.

Moreover, such a clique tree can be found in linear time.

###### Proof

By Lemma 2, there exists a clique tree $(T,X)$ that satisfies all the
properties except that the root of $T$ can be any bag.

Let us first modify $(T,X)$ to ensure that the clique tree is rooted on a node
that contains only $\\{r\\}$. If $r$ appears in a bag of a leaf node then it
holds. Otherwise, there exists a forget node $i$ with a child $i^{\prime}$
such that $X_{i}=X_{i^{\prime}}\setminus\\{r\\}$. Let
$X_{i}=\\{v_{1},\ldots,v_{k}\\}$ with $r=v_{1}$. We do the following
modifications on $T$: delete the edge $ii^{\prime}$, add two nodes
$i^{\prime\prime}$ and $i_{k}$ such that $X_{i^{\prime\prime}}={X_{k}}=X_{v}$,
$i^{\prime\prime}$ is a join node with child $i^{\prime}$ and $k$ and $i$ is a
forget node with child $i^{\prime\prime}$. Ultimately, we add the nodes
$i_{k-1}\ldots,i_{1}$ such that for any $1\leq t\leq k-1$,
$X_{i_{t}}=\\{v_{1},\ldots,v_{t}\\}$ and $i_{t}$ is the child of the node
$i_{t+1}$ (which is a forget node). Then, $r$ appears in a bag of a leaf node
by adding at most $n$ nodes in $T$.

Let us now root $T$ on the node whose bag is $\\{r\\}$. We need to check that
the property on nodes are preserved. Note that for every edge, the two bags on
the extremities differ at most on one vertex. If a node has only one child
with the same bag then merge the two nodes. If a node $i$ had two children
with different bags, let $X$ be the bag of $i$, then add a new bag with vertex
set $X$ between $i$ and its child with a different bag. The tree we get after
these modifications satisfies all the properties of the lemma.

All these modifications can be performed in linear time. So find the clique
tree can be performed in time $O(n)$.∎

In the following, a clique tree with the properties of Lemma 3 will be called
a _nice clique tree_ and we will only consider nice clique trees $(X,T)$ of
chordal graphs $G$.

Given a rooted clique tree $(T,X)$ of $G$, for any node $i$ of $T$, we define
the _subgraph of $G$ rooted in $X_{i}$_, denoted by $T(X_{i})$, as the subset
of vertices of $G$ containing in at least one of the bags of the subtree of
$T$ rooted in $i$ (i.e. in the bag of $i$ or one of its descendants).

###  2.2 Clique separators and resolving sets.

In this section, we give some technical lemmas that will permit to bound by
$f(\omega)$ the amount of information we have to remember in the dynamic
programming algorithm.

###### Lemma 4

Let $K$ be a clique separator of $G$ and $G_{1}$ be a connected component of
$G\setminus K$. Let $G_{ext}$ be the subgraph of $G$ induced by the vertices
of $G_{1}\cup K$ and $G_{int}=G\setminus G_{ext}$. Let $x_{1},x_{2}\in
V(G_{int})$ be such that $|d(x_{1},K)-d(x_{2},K)|\geq 2$. Then, every vertex
$s\in V(G_{ext})$ resolves the pair $(x_{1},x_{2})$.

###### Proof

Without loss of generality, assume $d(x_{1},K)+2\leq d(x_{2},K)$. By
triangular inequality and since $K$ is a clique, $d(x_{1},s)\leq
d(x_{1},K)+1+d(K,s)$ and $d(x_{2},s)\geq d(x_{2},K)+d(K,s)$. The sum of these
inequalities gives $d(x_{2},K)+d(x_{1},s)\leq
d(x_{1},K)+1+d(x_{2},s)<d(x_{2},K)+d(x_{2},s)$. Thus, $d(x_{1},s)<d(x_{2},s)$,
meaning that $s$ resolves the pair $(x_{1},x_{2})$.∎

Before proving Lemma 6, let us extract a technical case.

###### Lemma 5

Let $G$ be a chordal graph and $T$ be a nice clique tree of $G$. Let $X$, $Y$
be two bags of $T$ and $x$, $y$ be two vertices in respectively $X$, $Y$ . Let
$Y$ be a bag of $T$ such that $X\cap Y=\emptyset$. Assume $d(x,y)\geq 2$ and
let $z$ be a neighbour of $x$ that appears in the bag the closest to $Y$ in
$T$ amongst the bags on the path between $X$ and $Y$. Then $z$ belongs to a
shortest path between $x$ and $y$.

###### Proof

Let $Z$ be the bag containing $z$ and no other vertices of $N[x]$ with $Z$ on
the path between $X$ and $Y$. If $Z=Y$ then $z$ is a common neighbour of $x$
and $y$ which gives the result since $d(x,y)\geq 2$. Otherwise, consider a
shortest path $x=x_{1},x_{2},\ldots,x_{m}=y$ between $x$ and $y$ and let
$x_{i}$ be the first vertex of this path belonging to $Z$. Such a vertex
exists since $Z$ separates $x$ and $y$. If $x_{i}=z$ then the result holds.
Otherwise by definition of $z$, $x_{i}$ is not adjacent to $x$ and is adjacent
to $z$ because they both belong $Z$. Thus, if we replace the sub-path
$x_{1},\ldots,x_{i}$ by $x,z,x_{i}$, it gives a path from $x$ to $Z$ whose
length is at most the length of the initial path which gives the result.∎

###### Lemma 6

Let $S$ be a subset of vertices of $G$. Let $X$, $Y$ and $Z$ be three bags of
a nice tree-decomposition $T$ of $G$ such that $Z$ is on the path $P$ between
$X$ and $Y$ in $T$. Denote by $P=X_{1},\ldots Z\ldots X_{p}$ the bags of $P$
with $X=X_{1}$ and $Y=X_{p}$. Let $x$ be a vertex of $X$ and $y$ a vertex of
$Y$ with $d(x,Z)\geq 2$ and $d(y,Z)\geq 2$. Assume that any pair of vertices
$(u,v)$ with $u\in\ X_{2}\cup\ldots\cup Z$, $v\in Z\cup\ldots\cup X_{p}$,
$d(u,Z)<d(x,Z)$ and $d(v,Z)<d(y,Z)$ is resolved by $S$. Then the pair $(u,v)$
is resolved by $S$.

###### Proof

Let $i_{1}$ be such that $X_{i_{1}}\cap N[x]\neq\emptyset$ and for every
$j>i_{1}$, $X_{j}\cap N[x]=\emptyset$ and $i_{2}$ be such that $X_{i_{2}}\cap
N[y]\neq\emptyset$ and for $j<i_{2}$, $X_{j}\cap N[y]=\emptyset$. Let
$x^{\prime}$ be the only neighbour of $x$ in $X_{i_{1}}$ and $y^{\prime}$ be
the only neighbour of $y$ in $X_{i_{2}}$, they are unique by definition of
nice tree-decomposition. Note that $d(x,y)\geq 4$ since $d(x,Z)\geq 2$ and
$d(y,Z)\geq 2$. So $N[x]$ is not adjacent to $N[y]$ and then $i_{1}<i_{2}$. By
Lemma 5, $x^{\prime}$ is on a shortest path between $x$ and $Z$ and
$y^{\prime}$ is on a shortest path between $y$ and $Z$. So
$d(x^{\prime},Z)<d(x,Z)$ and $d(y^{\prime},Z)<d(y,Z)$. By hypothesis, there is
a vertex $s\in S$ resolving the pair $(x^{\prime},y^{\prime})$. Let us prove
that $s$ resolves the pair $(x,y)$.

If $s$ is a neighbour of $x$ or $y$ then $s$ resolves the pair $(x,y)$ since
$d(u,v)\geq 4$. So we can assume that $d(s,x)\geq 2$ and $d(s,y)\geq 2$. Let
$X_{s}$ be a bag of $T$ containing $s$ and $X_{s}^{\prime}$ be the closest bag
to $X_{s}$ on $P$ between $X$ and $Y$.

Case 1: $s\in X_{i_{1}}$ and $s\in X_{i_{2}}$. Then, $d(s,x^{\prime})\leq 1$
and $d(s,y^{\prime})\leq 1$. The vertex $s$ resolves the pair
$(x^{\prime},y^{\prime})$ so $d(s,x^{\prime})\neq d(s,y^{\prime})$ so
$s=x^{\prime}$ or $s=y^{\prime}$. Assume by symmetry that $s=x^{\prime}$, then
$d(s,x)=1$ and $d(s,y)\geq 3$ because $d(x,y)\geq 4$. So $s$ resolves the pair
$(x,y)$.

Case 2: $s$ belongs to exactly one of $X_{i_{1}}$ or $X_{i_{2}}$. By symmetry
assume that $s\in X_{i_{1}}$. By Lemma 5, $y^{\prime}$ is on a shortest path
between $y$ and $s$. So $d(s,y)=d(s,y^{\prime})+1$. As $s$ belongs to
$X_{i_{1}}$ then $d(x^{\prime},s)=1$ and $d(x,s)\leq 2$. As
$d(y^{\prime},s)\neq d(x^{\prime},s)$ we have $d(y^{\prime},s)\geq 2$, so
$d(s,y)\geq 3$. Thus $s$ resolves the pair $(x,y)$.

Case 3: $s\notin X_{i_{1}}$ and $s\notin X_{i_{2}}$. First, we consider the
case where $X_{s}^{\prime}$ is between $X_{i_{1}}$ and $X_{i_{2}}$. Then,
$d(s,x)=d(s,x^{\prime})+1$ and $d(s,y)=d(s,y^{\prime})+1$ by Lemma 5 as
$X_{i_{1}}$ separates $x$ and $s$ and $X_{i_{2}}$ separates $x$ and $s$. Thus,
$s$ resolves the pair $(x,y)$.

By symmetry, we can now assume that $X_{s}^{\prime}$ is between $X$ and
$X_{i_{1}}$. Since $i_{1}<i_{2}$, $X_{i_{2}}$ separates $s$ and $y$. So
$d(s,y)=d(s,y^{\prime})+1$ by Lemma 5. To conclude we prove that
$d(s,x^{\prime})<d(s,y^{\prime})$. Let $Q$ be a shortest path between $s$ and
$y$. The bag $X_{i_{1}}$ separates $s$ and $y$ so $Q\cap
X_{i_{1}}\neq\emptyset$. Let $y_{1}\in Q\cap X_{i_{1}}$. By definition of $Q$,
$d(s,y^{\prime})=d(s,y_{1})+d(y_{1},y)$. We know $y_{1}\neq y$ because $y_{1}$
is a neighbour of $x$. So $d(y_{1},y)\neq 0$. We also have
$d(s,x^{\prime})\leq d(s,y_{1})+1$ because $y_{1}\in X_{i_{1}}$. So $y_{1}$ is
a neighbour of $x^{\prime}$. As $d(s,x^{\prime})\neq d(s,y^{\prime})$, this
ensures $d(s,x^{\prime})<d(s,y^{\prime})$. So $s$ resolves the pair $(x,y)$
because $d(s,x)\leq d(s,x^{\prime})+1<d(s,y^{\prime})+1=d(s,y)$.∎

The following corollary is essentially rephrasing Lemma 6 to get the result on
a set of vertices.

###### Corollary 7

Let $G$ be a chordal graph and $S$ be a subset of vertices of $G$. Let $X_{i}$
be a bag of $T$ and let $T_{1}=(X_{1},E_{1})$ and $T_{2}=(X_{2},E_{2})$ be two
connected components of $T\setminus X_{i}$. Assume that any pair of vertices
$(u,v)$ of $(X_{1}\cup X_{i})\times(X_{2}\cup X_{i})$ with $d(u,X_{i})\leq 2$
and $d(v,X_{i})\leq 2$ is resolved by $S$. Then any pair of vertices $(u,v)$
of $(X_{1},X_{2})$ with $|d(u,X_{i})-d(v,X_{i})|\leq 1$ is resolved by $S$.

###### Proof

Assume by contradiction, that there exist some pairs of vertices of
$(T_{1},T_{2})$ with $|d(u,X_{i})-d(v,X_{i})|\leq 1$ which are not resolved by
$S$. Among all these pairs, let $(u,v)$ be one pair minimizing
$q:=d(u,X_{i})+d(v,X_{i})$. If $q\leq 4$ then $d(u,X_{i})\leq 2$ and
$d(v,X_{i})\leq 2$, so the pair $(u,v)$ is resolved by the hypothesis of the
lemma. If $q\geq 5$, then $d(u,X_{i})\geq 2$ and $d(v,X_{i})\geq 2$. By
minimality, we know that all pairs $(u^{\prime},v^{\prime})$ of
$(T_{1},T_{2})$ with $d(u^{\prime},X_{i})<d(u,X_{i})$ and
$d(v^{\prime},X_{i})<d(v,X_{i})$ are resolved by $S$. So, by Lemma 6, the pair
$(u,v)$ is resolved by $S$.∎

##  3 Algorithm description

In this section, we fix a vertex $v$ of a chordal graph $G$ and consider a
nice clique tree $(T,X)$ rooted in $v$ which exists by Lemma 3. We present an
algorithm computing the smallest size of a resolving set of $G$ containing
$v$.

###  3.1 Generalisation of the problem

The algorithm is a dynamic programming algorithm that works bottom-up from the
leaves of a nice clique tree. Our algorithm computes the solution of a problem
more general than the metric dimension but easiest to manipulate for combining
solutions. Our algorithm consists in a dynamic programming on the clique tree.
In this new problem, we will represent some vertices by vectors of distance.

We define notations to edit vectors.

###### Definition 8

Given a vector $\mathbf{r}$, the notation $\mathbf{r}_{i}$ refers to the
$i$-th coordinate of $\mathbf{r}$.

  * •

Let $\mathbf{r}=(r_{1},\ldots,r_{k})\in\mathbb{N}^{k}$ be a vector of size $k$
and $m\in N$. The vector $\mathbf{r^{\prime}}=\mathbf{r|m}$ is the vector of
size $k+1$ with $r^{\prime}_{i}=r_{i}$ for $1\leq i\leq k$ and
$r^{\prime}_{k+1}=m$.

  * •

Let $\mathbf{r}=(r_{1},\ldots,r_{k})\in\mathbb{N}^{k}$ be a vector of size
$k$. The vector $\mathbf{r^{-}}$ is the vector of size $k-1$ with
$r^{-}_{i}=r_{i}$ for $1\leq i\leq k-1$.

###### Definition 9

Let $i$ be a node of $T$ and let $X_{i}=\\{v_{1},\ldots,v_{k}\\}$ be the bag
of $i$. For a vertex $x$ of $G$, the _distance vector_
$\mathbf{\mathbf{{d_{X_{i}}}(x)}}$ of $x$ to $X_{i}$ is the vector of size $k$
such that, for $1\leq j\leq k$,
$\mathbf{\mathbf{{d_{X_{i}}}(x)}}_{j}=d(x,v_{j})$. We define the set $d_{\leq
2}(X_{i})$ as the set of distance vectors of the vertices of $T(X_{i})$ at
distance at most $2$ of $X_{i}$ in $G$ (i.e. one of the coordinate is at most
$2$).

###### Definition 10

Let $G$ be a graph and $K=\\{v_{1},\ldots,v_{k}\\}$ be a clique of $G$. Let
$x$ be a vertex of $G$. The _trace_ of $x$ on $K$, denoted by
$\mathbf{Tr_{K}}(x)$, is the vector $\mathbf{r}$ of
$\\{0,1\\}^{k}\setminus\\{1,\ldots,1\\}$ such that for every $1\leq i\leq k$,
$d(x,v_{i})=a+\mathbf{r}_{i}$ where $a=d(x,K)$.

Let $S$ be a subset of vertices of $G$. The trace $Tr_{K}(S)$ of $S$ in $K$ is
the set of vectors $\\{\mathbf{Tr_{K}}(x),{x\in S}\\}$.

The trace is well-defined because for a vertex $x$ and a clique $K$, the
distance between $x$ and a vertex of $K$ is either $d(x,K)$ or $d(x,K)+1$.

###### Definition 11

Let $\mathbf{r_{1}},\mathbf{r_{2}}$ and $\mathbf{r_{3}}$ be three vectors of
same size $k$. We say that $\mathbf{r_{3}}$ _resolves_ the pair
$(\mathbf{r_{1}},\mathbf{r_{2}})$ if

$\min_{1\leq i\leq k}\mathbf{(r_{1}+r_{3})}_{i}\neq\min_{1\leq i\leq
k}\mathbf{(r_{2}+r_{3})}_{i}.$

###### Lemma 12

Let $K$ be a clique separator of $G$ and $G_{1}$ be a connected component of
$G\setminus K$. Let $(x,y)$ be a pair of vertices of $G\setminus G_{1}$ and
let $\mathbf{r}$ be a vector of size $|K|$. If $\mathbf{r}$ resolves the pair
$(\mathbf{\mathbf{{d_{K}}(x)}},\mathbf{\mathbf{{d_{K}}(y)}})$, then any vertex
$s\in V(G_{1})$ with $\mathbf{Tr_{K}}(s)=\mathbf{r}$ resolves the pair
$(x,y)$.

###### Proof

Let $s$ be a vertex of $G_{1}$ such that $\mathbf{Tr_{K}}(s)=\mathbf{r}$. The
clique $K$ separates $s$ and $x$ (resp. $y$) so $d(x,s)=\min_{1\leq i\leq
k}(\mathbf{\mathbf{{d_{K}}(x)}}+\mathbf{Tr_{K}}(s))_{i}+d(K,s)$ (resp.
$d(y,s)=\min_{1\leq i\leq
k}(\mathbf{\mathbf{{d_{K}}(y)}}+\mathbf{Tr_{K}}(s))_{i}+d(K,s)$). The vector
$\mathbf{r}$ resolves the pair
$(\mathbf{\mathbf{{d_{K}}(x)}},\mathbf{\mathbf{{d_{K}}(y)}})$. So $d(x,s)\neq
d(y,s)$ and $s$ resolves the pair $(x,y)$.∎

###### Definition 13

Let $K$ be a clique separator of $G$ and $G_{1}$, $G_{2}$ be two (non
necessarily distinct) connected components of $G\setminus K$. Let $M$ be a set
of vectors and let $u\in V(G_{1})\cup K$ and $v\in V(G_{2})\cup K$. If a
vector $\mathbf{r}$ resolves the pair
$(\mathbf{\mathbf{{d_{K}}(x)}},\mathbf{\mathbf{{d_{K}}(y)}})$, we say that
$\mathbf{r}$ _resolves_ the pair $(x,y)$. We say that the pair of vertices
$(u,v)$ _is resolved_ by $M$ if there exists a vector $\mathbf{r}\in M$ that
resolves the pair $(u,v)$.

We can now define the generalised problem our dynamic programming algorithm
actually solves. We call it the extended metric dimension problem (EMD for
short) . We first define the instances of this problem.

###### Definition 14

Let $i$ be a node of $T$. An _instance for a node $i$_ of the EMD problem is a
$5$-uplet $I=(X_{i},S_{I},D_{int}{{(I)}},D_{ext}{{(I)}},D_{pair}{{(I))}}$
composed of the bag $X_{i}$ of $i$, a subset $S_{I}$ of $X_{i}$ and three sets
of vectors satisfying

  * •

$D_{int}{{(I)}}\subseteq\\{0,1\\}^{|X_{i}|}$ and
$D_{ext}{{(I)}}\subseteq\\{0,1\\}^{|X_{i}|}$,

  * •

$D_{pair}{{(I)}}\subseteq[|0,3|]^{|X_{i}|}\times[|0,3|]^{|X_{i}|}$,

  * •

$D_{ext}{{(I)}}\neq\emptyset$ or $S_{I}\neq\emptyset$,

  * •

For each pair of vectors $(\mathbf{r_{1}},\mathbf{r_{2}})\in D_{pair}{{(I)}}$,
there exist two vertices $x\in T(X_{i})$ with
$\mathbf{\mathbf{{d_{X_{i}}}(x)}}=\mathbf{r_{1}}$ and $d(x,X_{i})\leq 2$ and
$y\notin T(X_{i})$ with $\mathbf{\mathbf{{d_{X_{i}}}(y)}}=\mathbf{r_{2}}$ and
$d(y,X_{i})\leq 2$.

###### Definition 15

A set $S\subseteq T(X_{i})$ is a solution for an instance $I$ of the EMD
problem if

  * •

(S1) Every pair of vertices of $T(X_{i})$ is either resolved by a vertex in
$S$ or resolved by a vector of $D_{ext}{{(I)}}$.

  * •

(S2) For each vector $\mathbf{r}\in D_{int}{{(I)}}$ there exists a vertex
$s\in S$ such that $\mathbf{Tr_{X_{i}}}(s)=\mathbf{r}$.

  * •

(S3) For each pair of vector $(\mathbf{r_{1}},\mathbf{r_{2}})\in
D_{pair}{{(I)}}$, for any vertex $x\in T(X_{i})$ with
$\mathbf{\mathbf{{d_{X_{i}}}(x)}}=\mathbf{r_{1}}$ and any vertex $y\notin
T(X_{i})$ with $\mathbf{\mathbf{{d_{X_{i}}}(y)}}=\mathbf{r_{2}}$, if
$d(x,X_{i})\leq 2$ and $d(y,X_{i})\leq 2$ the pair $(x,y)$ is resolved by $S$.

  * •

(S4) $S\cap X_{i}=S_{I}$.

In the rest of the paper, for shortness, we will refer to an instance of the
EMD problem only by an instance.

###### Definition 16

Let $I$ be an instance. We denote by $\dim(I)$ the minimum size of a set
$S\subseteq T(X_{i})$ which is a solution of $I$. If such a set does not exist
we define $\dim(I)=+\infty$. We call this value the _extended metric
dimension_ of $I$.

We now explain the meaning of each element of $I$. Firstly, a solution $S$
must resolve any pair in $T(X_{i})$, possibly with a vector of
$D_{ext}{{(I)}}$ which represents a vertex of $V\setminus T(X_{i})$ in the
resolving set. Secondly, for all $\mathbf{r}$ in $D_{int}{{(I)}}$, we are
forced to select a vertex in $T(X_{i})$ whose trace is $\mathbf{r}$. This will
be useful to combine solutions since it will be a vector of $D_{ext}$ in other
instances. The elements in $D_{pair}{{(I)}}$ will also be useful for
combinations. In some sense $D_{pair}{{(I)}}$ is the additional gain of $S$
compared to the main goal to resolve $T(X_{i})$. The set $S_{I}$ constrains
the intersection between $S$ and $X_{i}$ by forcing a precise subset of
$X_{i}$ to be in $S$.

The following lemma is a consequence of Definition 15. It connects the
definition of the extended metric dimension with the metric dimension.

###### Lemma 17

Let $G$ be a graph, $T$ be a nice tree-decomposition of $G$ and $r$ be the
root of $T$. Let $I_{0}$ be the instance
${(\\{r\\},\\{r\\},\emptyset,\emptyset,\emptyset)}$, then $\dim(I_{0})$ is the
smallest size of a resolving set of $G$ containing $r$.

To ensure that our algorithm works well, we will need to use Lemma 4 in some
subgraphs of $G$. This is possible only if we know that the solution is not
included in the subgraph. This corresponds to the condition
$D_{ext}{{(I)}}\neq\emptyset$ or $S_{I}\neq\emptyset$ and this is why the
algorithm computes the size of a resolving set containing the root of $T$.

###  3.2 Dynamic programming

We explain how we can compute the metric dimension of an instance $I$ given
the metric dimension of the instances on the children of $X_{i}$ in $T$. The
proof is divided according to the different type of nodes.

####  3.2.1 Leaf node

Computing the dimension of an instance for a leaf node can be done easily with
the following lemma.

###### Lemma 18

Let $I$ be an instance for a leaf node $i$ and $v$ be the unique vertex of
$X_{i}$. Then,

$\dim(I)=\left\\{\begin{array}[]{lll}0&\text{ if
}S_{I}=\emptyset,\;D_{int}{{(I)}}=\emptyset\text{ and
}D_{pair}{{(I)}}=\emptyset\\\ 1&\text{ if }S_{I}=\\{v\\}\text{ and
}D_{int}{{(I)}}\subseteq\\{\mathbf{(0)}\\}\\\ +\infty&\text{
otherwise}\end{array}\right.$

###### Proof

Let $I$ be an instance for $i$. If $S_{I}=\emptyset$, only the set
$S=\emptyset$ can be a solution for $I$. This set is a solution only if
$D_{int}{{(I)}}=\emptyset$ and $D_{pair}{{(I)}}=\emptyset$. If
$S_{I}=\\{v\\}$, only the set $S=\\{v\\}$ can be a solution for $I$. This is a
solution only if $D_{int}{{(I)}}$ is empty or only contains the vector
$\mathbf{Tr_{x_{i}}}(v)$. ∎

In the rest of the section, we treat the three other types of nodes. For each
type of nodes we will proceed as follows: define some conditions on the
instances on children to be compatible with $I$, and prove an equality between
the extended metric dimension on compatible children instances and the
extended metric dimension of the instance of the node.

####  3.2.2 Join node.

Let $I$ be an instance for a join node $i$ and let $i_{1}$ and $i_{2}$ be the
children of $i$.

###### Definition 19

A pair of instances $(I_{1},I_{2})$ for $(i_{1},i_{2})$ is _compatible_ with
$I$ if

  * •

(J1) $S_{I_{1}}=S_{I_{2}}=S_{I}$,

  * •

(J2) $D_{ext}{{(I_{1})}}\subseteq D_{ext}{{(I)}}\cup D_{int}{{(I_{2})}}$ and
$D_{ext}{{(I_{2})}}\subseteq D_{ext}{{(I)}}\cup D_{int}{{(I_{1})}}$,

  * •

(J3) $D_{int}{{(I)}}\subseteq D_{int}{{(I_{1})}}\cup D_{int}{{(I_{2})}}$,

  * •

(J4) Let $C_{1}=\\{(\mathbf{r},\mathbf{t})\in D_{pair}{{(I)}}$ such that
$\mathbf{r}\notin d_{\leq 2}(X_{i_{1}})\\}$ and
$C_{2}=\\{(\mathbf{r},\mathbf{t})\in D_{pair}{{(I)}}$ such that
$\mathbf{r}\notin d_{\leq 2}(X_{i_{2}})\\}$. Let
$D_{1}=\\{(\mathbf{r},\mathbf{t})\in d_{\leq 2}(X_{i_{1}})\times d_{\leq
2}(G\setminus X_{i_{1}})$ such that there exists $\mathbf{u}\in
D_{int}{{(I_{2})}}$ resolving the pair $(\mathbf{r},\mathbf{t})\\}$ and
$D_{2}=\\{(\mathbf{r},\mathbf{t})\in d_{\leq 2}(X_{i_{2}})\times d_{\leq
2}(G\setminus X_{i_{2}}))$ such that there exists $\mathbf{u}\in
D_{int}{{(I_{1})}}$ resolving the pair $(\mathbf{r},\mathbf{t})\\}$

Then $D_{pair}{{(I)}}\subseteq(\mathbf{r},\mathbf{t})\in(C_{1}\cup D_{1}\cup
D_{pair}{{(I_{1})}})\cap(C_{2}\cup D_{2}\cup D_{pair}{{(I_{2})}})$,

  * •

(J5) For all $\mathbf{r_{1}}\in d_{\leq 2}(X_{i_{1}})$, for all
$\mathbf{r_{2}}\in d_{\leq 2}(X_{i_{2}})$, $(\mathbf{r_{1}},\mathbf{r_{2}})\in
D_{pair}{{(I_{1})}}$ or $(\mathbf{r_{2}},\mathbf{r_{1}})\in
D_{pair}{{(I_{2})}}$ or there exists $\mathbf{t}\in D_{ext}{{(I)}}$ such that
$\mathbf{t}$ resolves the pair $(\mathbf{r_{1}},\mathbf{r_{2}})$.

Condition (J4) represents how the pairs of vertices of $V(T(X_{i_{1}}))\times
V(T(X_{i_{2}}))$ can be resolved. A pair $(\mathbf{r},\mathbf{t})$ is in
$(C_{1}\cup D_{1}\cup D_{pair}{{(I_{1})}})$ if all the pairs of vertices
$(x,y)$ with $x\in V(T(X_{i_{1}}))$ and $y\in V(T(X_{i_{2}}))$ are resolved.
If $(\mathbf{r},\mathbf{t})$ is in $C_{1}$, no such pair of vertices exists,
if $(\mathbf{r},\mathbf{t})$ is in $D_{1}$ the pairs of vertices are resolved
by a vertex outside of $V(T(X_{i_{1}}))$ and if $(\mathbf{r},\mathbf{t})$ is
in $D_{pair}{{(I_{1})}}$ the pairs of vertices are resolved by a vertex of
$V(T(X_{i_{1}}))$. So a pair $(\mathbf{r},\mathbf{t})$ is resolved if the pair
is in $(C_{1}\cup D_{1}\cup D_{pair}{{(I_{1})}})$ and in $(C_{2}\cup D_{2}\cup
D_{pair}{{(I_{2})}})$.

Let $\mathcal{F}_{J}(I)$ be the set of pairs of instances compatible with $I$.
We want to prove the following lemma:

###### Lemma 20

Let $I$ be an instance for a join node $i$. Then,

$\dim(I)=\min_{(I_{1},I_{2})\in\mathcal{F}_{J}(I)}(\dim(I_{1})+\dim(I_{2})-|S_{I}|).$

We prove the equality by proving the two inequalities in the next lemmas.

###### Lemma 21

Let $(I_{1},I_{2})$ be a pair of instances for $(i_{1},i_{2})$ compatible with
$I$ with finite values for $\dim(I_{1})$ and $\dim(I_{2})$. Let
$S_{1}\subseteq V(T(X_{i_{1}}))$ be a solution for $I_{1}$ and $S_{2}\subseteq
V(T(X_{i_{2}}))$ be a solution for $I_{2}$. Then $S=S_{1}\cup S_{2}$ is a
solution for $I$. In particular,

$\dim(I)\leq\min_{(I_{1},I_{2})\in\mathcal{F}_{J}(I)}(\dim(I_{1})+\dim(I_{2})-|S_{I}|).$

###### Proof

Let us prove that the conditions of Definition 15 are satisfied.

(S1) Let $(x,y)$ be a pair of vertices of $T(X_{i})$. Assume first that $x\in
V(T(X_{i_{1}}))$ and $y\in V(T(X_{i_{1}}))$. Either $(x,y)$ is resolved by a
vertex of $S_{1}$ and then by a vertex of $S$ or $(x,y)$ is resolved by a
vector $\mathbf{r}\in D_{ext}{{(I_{1})}}$. By condition (J2), $\mathbf{r}\in
D_{ext}{{(I)}}$ or $\mathbf{r}\in D_{int}{{(I_{2})}}$. If $\mathbf{r}\in
D_{ext}{{(I)}}$ then $(x,y)$ is resolved by a vector of $D_{ext}{{(I_{1})}}$.
Otherwise, there exists a vertex $t\in S_{2}$ such that
$\mathbf{Tr_{X_{i_{2}}}}(t)=\mathbf{r}$. So $t\in S$ and $t$ resolves the pair
$(x,y)$. The case $x\in V(T(X_{i_{2}}))$ and $y\in V(T(X_{i_{2}}))$ is
symmetric. So we can assume that $x\in V(T(X_{i_{1}}))$ and $y\in
V(T(X_{i_{2}}))$. If $d(x,X_{i})\leq 2$ and $d(y,X_{i})\leq 2$, the condition
(J5) ensures that the pair $(x,y)$ is resolved by $S$ or by a vector of
$D_{ext}{{(I)}}$. Otherwise, either $|d(x,X_{i})-d(y,X_{i})|\leq 1$ and
$(x,y)$ is resolved by Lemma 7 or $|d(x,X_{i})-d(y,X_{i})|\geq 2$ and $(x,y)$
is resolved by Lemma 4 because $D_{ext}{{(I)}}\neq\emptyset$ or
$S_{I}\neq\emptyset$.

(S2) Let $\mathbf{r}\in D_{int}{{(I)}}$. By compatibility, the condition (J3)
ensures that $\mathbf{r}\in D_{int}{{(I_{1})}}$ or $\mathbf{r}\in
D_{int}{{(I_{2})}}$. As $S=S_{1}\cup S_{2}$, $S$ contains a vertex $s$ such
that $\mathbf{Tr_{X_{i}}}(s)=\mathbf{r}$.

(S3) Let $(\mathbf{r},\mathbf{t})\in D_{pair}{{(I)}}$ and $(x,y)$ with $x\in
V(T(X_{i}))$ such that $\mathbf{\mathbf{{d_{X_{i}}}(x)}}=\mathbf{y}$ and
$y\notin T(X_{i})$ such that $\mathbf{\mathbf{{d_{X_{i}}}(y)}}=\mathbf{t}$.
Without loss of generality assume that $x\in V(T(X_{i_{1}}))$.

By compatibility, $(\mathbf{r},\mathbf{t})\in(C_{1}\cup D_{1}\cup
D_{pair}{{(I_{1})}})\cap(C_{2}\cup D_{2}\cup D_{pair}{{(I_{2})}})$ so in
$C_{1}\cup D_{1}\cup D_{pair}{{(I_{1})}}$. If $(\mathbf{r},\mathbf{t})\in
D_{pair}{{(I)}}_{1}$, then there exists $s\in S_{1}$ that resolves the pair
$(x,y)$ so the pair is resolved by $S$. If $(\mathbf{r},\mathbf{t})\in D_{1}$,
there exists $\mathbf{u}\in D_{int}{{(I_{2})}}$ such that $\mathbf{u}$
resolves the pair $(\mathbf{r},\mathbf{t})$. By compatibility, there exists
$s\in S_{2}$ such that $\mathbf{Tr_{X_{i}}}(s)=\mathbf{u}$. So $s$ resolves
the pair $(x,y)$. And $(\mathbf{r},\mathbf{t})\notin C_{1}$ since $x$ belongs
to $T(X_{i_{1}})$ with vector distance $\mathbf{r}$.

(S4) is clear since $X_{i_{1}}=X_{i_{2}}=X_{i}$.

Thus, $\dim(I)\leq\dim(I_{1})+\dim(I_{2})-|S_{I}|$ is true for any pair of
compatible instances $(I_{1},I_{2})$ so
$\dim(I)\leq\min_{(I_{1},I_{2})\in\mathcal{F}_{J}(I)}(\dim(I_{1})+\dim(I_{2})-|S_{I}|)$.∎

###### Lemma 22

Let $I$ be an instance for a join node $i$ and let $i_{1}$ and $i_{2}$ be the
children of $i$. Then,

$\dim(I)\geq\min_{(I_{1},I_{2})\in\mathcal{F}_{J}(I)}(\dim(I_{1})+\dim(I_{2})-|S_{I}|).$

###### Proof

If $\dim(I)=+\infty$ then the result indeed holds. So assume $\dim(I)$ is
finite. Let $S$ be a solution for $I$ of minimal size. Let $S_{1}=S\cap
T(X_{i_{1}})$ and $S_{2}=S\cap T(X_{i_{2}})$. We define now two instances
$I_{1}$ and $I_{2}$ for $i_{1}$ and $i_{2}$. Let $S_{I_{1}}=S_{I_{2}}=S_{I}$,
$D_{int}{{(I_{1})}}=Tr_{X_{i}}(S_{1})$,
$D_{int}{{(I_{2})}}=Tr_{X_{i}}(S_{2})$, $D_{ext}{{(I_{1})}}=D_{ext}{{(I)}}\cup
D_{int}{{(I_{2})}}$ and $D_{ext}{{(I_{2})}}=D_{ext}{{(I)}}\cup
D_{int}{{(I_{1})}}$. To build the sets $D_{pair}{{(I_{1})}}$ and
$D_{pair}{{(I_{2})}}$ we make the following process that we explain for
$D_{pair}{{(I_{1})}}$. For all pairs of vectors $(\mathbf{r},\mathbf{t})$ of
$(d_{\leq 2}(X_{i_{1}}),d_{\leq 2}(G\setminus X_{i_{1}}))$, consider all the
pairs of vertices $(x,y)$ with $x\in V(T(X_{i_{1}}))$, $y\in V(G\setminus
T(X_{i_{1}}))$, $\mathbf{r}\in d_{\leq 2}(X_{i})$, $\mathbf{t}\in d_{\leq
2}(G\setminus X_{i_{1}}))$, $\mathbf{\mathbf{{d_{X_{i}}}(x)}}=\mathbf{r}$ and
$\mathbf{\mathbf{{d_{X_{i}}}(y)}}=\mathbf{t}$. If all the pairs are resolved
by vertices of $S_{1}$ (that for each pair, there exists a vertex of $S_{1}$
that resolves the pair), then add $(\mathbf{r},\mathbf{t})$ to
$D_{pair}{{(I_{1})}}$.

###### Claim

$(I_{1},I_{2})$ is compatible with $I$.

###### Proof

(J1), (J2) and (J3) are straightforward.

(J4) Let $(\mathbf{r},\mathbf{t})\in D_{pair}{{(I)}}$, we want to prove that
$(\mathbf{r},\mathbf{t})\in(C_{1}\cup D_{1}\cup
D_{pair}{{(I_{1})}})\cap(C_{2}\cup D_{2}\cup D_{pair}{{(I_{2})}})$. We prove
that $(\mathbf{r},\mathbf{t})\in(C_{1}\cup D_{1}\cup D_{pair}{{(I_{1})}})$,
the other part of the proof is symmetrical.

If $\mathbf{r}\notin d_{\leq 2}(X_{i_{1}})$, then $(\mathbf{r},\mathbf{t})\in
C_{1}$. Otherwise, there exists a vertex $x$ in $T(X_{i_{1}})$ such that
$\mathbf{\mathbf{{d_{X_{i_{1}}}}(x)}}=\mathbf{r}$ and a vertex $y$ in
$G\setminus T(X_{i})$ such that $\mathbf{\mathbf{{d_{X_{i}}}(y)}}=\mathbf{t}$
(because the pair $(\mathbf{r},\mathbf{t})$ belongs to $D_{pair}{{(I)}}$). The
pair $(x,y)$ is resolved by $S$. If there is a vertex $s\in S\cap
T(X_{i_{2}})$ resolving the pair, then $s$ resolves all the pairs with such
distance vector and then $(\mathbf{r},\mathbf{t})\in D_{1}$. Otherwise, for
any pair $(x,y)$ of $T(X_{i_{1}})\times G\setminus T(X_{i})$ with
$\mathbf{\mathbf{{d_{X_{i_{1}}}}(x)}}=\mathbf{r}$ and
$\mathbf{\mathbf{{d_{X_{i}}}(y)}}=\mathbf{t}$, there is a vertex of $S\cap
T(X_{i_{1}})$ that resolves the pair $(x,y)$, so $(\mathbf{r},\mathbf{t})\in
D_{pair}{{(I_{1})}}$.

(J5) Let $\mathbf{r_{1}}\in d_{\leq 2}(X_{i_{1}})$, $\mathbf{r_{2}}\in d_{\leq
2}(X_{i_{2}})$ and two vertices $x\in X_{i_{1}}$ and $y\in X_{i_{2}}$ such
that $\mathbf{\mathbf{{d_{X_{i_{1}}}}(x)}}=\mathbf{r_{1}}$ and
$\mathbf{\mathbf{{d_{X_{i_{2}}}}(y)}}=\mathbf{r_{2}}$. As $S$ is a solution of
$I$, either the pair $(x,y)$ is resolved by a vector $\mathbf{r_{3}}\in
D_{ext}{{(I)}}$, or there exists $s\in S$ resolving $(x,y)$. If $(x,y)$ is
resolved by $s$, assume by contradiction that
$(\mathbf{r_{1}},\mathbf{r_{2}})\not\in D_{pair}{{(I_{1})}}$ and
$(\mathbf{r_{2}},\mathbf{r_{1}})\not\in D_{pair}{{(I_{1})}}$. Then there exist
vertices $x_{1},x_{1}^{\prime}\in V(T(X_{i_{1}}))$ with
$\mathbf{\mathbf{{d_{X_{i_{1}}}}(x_{1})}}=\mathbf{r_{1}}$,
$\mathbf{\mathbf{{d_{X_{i_{2}}}}(x_{1}^{\prime})}}=\mathbf{r_{1}}$ and
$x_{2},x_{2}^{\prime}\in V(T(X_{i_{2}}))$ with
$\mathbf{\mathbf{{d_{X_{i_{2}}}}(x_{2})}}=\mathbf{r_{2}}$ and
$\mathbf{\mathbf{{d_{X_{i_{2}}}}(x_{2}^{\prime})}}=\mathbf{r_{2}}$ such that
the pair $(x_{1},x_{2})$ is not resolved by a vertex of $S_{1}$ and the pair
$(x_{1}^{\prime},x_{2}^{\prime})$ is not resolved by a vertex of $S_{2}$. Let
$s\in S$ resolving the pair $(x_{1},x_{2}^{\prime})$. If $s\in S_{1}$, then
$s$ resolves the pair $(x_{1},x_{2})$ and if $s\in S_{2}$, then $s$ resolves
the pair $(x_{1}^{\prime},x_{2}^{\prime})$, a contradiction. ∎

###### Claim

$S_{1}$ is a solution of $I_{1}$ and $S_{2}$ is a solution of $I_{2}$.

###### Proof

We only prove that $S_{1}$ is a solution of $I_{1}$ as the proof that $S_{2}$
is a solution of $I_{2}$ is similar.

(S1) Let $(x,y)$ be a pair of vertices of $T(X_{i_{1}})$. As $S$ is a solution
of $I$, the pair $(x,y)$ is either resolved by a vertex of $S$ or by a vector
of $D_{ext}{{(I)}}$. If $(x,y)$ is resolved by a vector of $D_{ext}{{(I)}}$,
the pair $(x,y)$ is also resolved by a vector of $D_{ext}{{(I_{1})}}$ since
$D_{ext}{{(I)}}\subseteq D_{ext}{{(I_{1})}}$. Otherwise let $s\in S$ resolving
the pair $(x,y)$. If $s\in T(X_{i_{1}})$ then $(x,y)$ is resolved by a vertex
of $S_{1}$. Otherwise $s\in T(X_{i_{2}})$ and by construction of $I_{1}$,
$D_{ext}{{(I_{1})}}$ contains the vector $\mathbf{Tr_{X_{i}}(s)}$ so $(x,y)$
is resolved by a vector of $D_{ext}{{(I_{1})}}$.

(S2) By definition, $D_{int}{{(I_{1})}}=Tr_{X_{i}}(S_{1})$. Hence, for any
vector $\mathbf{r}\in D_{int}{{(I_{1})}}$, there is a vertex $s\in S_{1}$ with
$\mathbf{Tr_{X_{i}}(s)}=\mathbf{r}$.

(S3) Let $(\mathbf{r},\mathbf{t})\in D_{pair}{{(I_{1})}}$, $x\in T(X_{i_{1}})$
and $y\notin T(X_{i_{1}})$ such that
$\mathbf{\mathbf{{d_{X_{i}}}(x)}}=\mathbf{r}$ and
$\mathbf{\mathbf{{d_{X_{i}}}(y)}}=\mathbf{y}$. By construction of
$D_{pair}{{(I_{1})}}$ there is a vertex $s\in S_{1}$ resolving the pair
$(x,y)$.

(S4) $S_{I_{1}}=S_{I}$ and since $S$ is a solution of $I$, $S_{I}=S\cap
X_{i}$. ∎

Ultimately we get the announced inequality. Since $S$ is a minimal solution
for $I$, we have $\dim(I)=|S|$. The sets $S_{1}$ and $S_{2}$ are solutions for
$S_{1}$ and $S_{2}$ so $\dim(I_{1})\leq|S_{1}|$ and $\dim(I_{2})\leq|S_{2}|$.
Since $|S|=|S_{1}|+|S_{2}|-|S_{I}|$ we get
$\dim(I)\geq\dim(I_{1})+\dim(I_{2})-|S_{I}|$. This inequality is true for a
specific pair of instances so in particular is true for a pair minimising the
amount $\dim(I_{1})+\dim(I_{2})-|S_{I}|$, giving the result. ∎

Lemma 20 is a direct consequence of Lemma 21 and Lemma 22.

####  3.2.3 Introduce node

We now consider an instance $I$ for an introduce node $i$. Let $j$ be the
child of $i$ and $v\in V$ be such that $X_{i}=X_{j}\cup\\{v\\}$. Let
$X_{i}=\\{v_{1},\ldots,v_{k}\\}$ with $v=v_{k}$. The tree $T(X_{i})$ contains
one more vertex than its child. The definition of the compatibility is
slightly different if we consider the same set as a solution (type $1$) or if
we add this vertex to the resolving set (type $2$).

###### Definition 23

An instance $I_{1}$ is compatible with $I$ of type $1$ (resp. $2$) if

  * •

(I1) $S_{I}=S_{I_{1}}$ (resp. $=S_{I_{1}}\cup\\{v\\}$).

  * •

(I2) For all $\mathbf{r}\in D_{ext}{{(I)}}$, $\mathbf{r^{-}}\in
D_{ext}{{(I_{1})}}$ (resp. or $\mathbf{r}=(0,\ldots,0)$).

  * •

(I3) For all $\mathbf{r}\in D_{int}{{(I)}},\mathbf{r}_{k}=1$ and
$\mathbf{r^{-}}\in D_{int}{{(I_{1})}}$ (resp. or $\mathbf{r}=(1,\ldots,1,0)$).

  * •

(I4) For all $(\mathbf{r},\mathbf{t})\in D_{pair}{{(I)}}$,
$(\mathbf{r^{-}},\mathbf{t^{-}})\in D_{pair}{{(I_{1})}}$.

  * •

(I5) If $I_{1}$ is of type $1$, for all $(\mathbf{r},\mathbf{t})$ with
$\mathbf{t}=(0,\ldots,0)$, $(\mathbf{r},\mathbf{t})\in D_{pair}{{(I_{1})}}$.

We want to prove that the following holds:

###### Lemma 24

Let $I$ be an instance for an introduce node $i$. Let $\mathcal{F}_{1}(I)$ be
the set of instances $I_{1}$ for $i_{1}$ compatible with $I$ of type 1 and
$\mathcal{F}_{2}(I)$ be the set of instances $I_{2}$ for $i_{1}$ compatible
with $I$ of type 2. Then,

$\dim(I)=\min\;\\{\min_{I_{1}\in\mathcal{F}_{1}(I)}\;\\{\dim(I_{1})\\};\min_{I_{2}\in\mathcal{F}_{2}(I)}\;\\{\dim(I_{2})+1\\}\\}.$

Let us first prove a technical case.

###### Lemma 25

Let $i$ be an introduce node, $j$ be the child of $i$ and $v\in V$ such that
$X_{i}=X_{j}\cup\\{v\\}$. Let $(x,y)$ be a pair of vertices of $T(X_{j})$. Let
$\mathbf{r}$ be a binary vector of size $|X_{i}|$, then $\mathbf{r}$ resolves
$(x,y)$ if and only if $\mathbf{r^{-}}$ resolves $(x,y)$.

###### Proof

Let $\mathbf{r_{1}}=\mathbf{Tr_{X_{i}}}(x)$ and
$\mathbf{r_{2}}=\mathbf{Tr_{X_{i}}}(y)$. Note that the set
${X_{i}\setminus\\{v\\}}$ separates $v$ from $x$ and $y$ so
$\mathbf{(r_{1})}_{k}=\mathbf{(r_{2})}_{k}=1$.

Assume first that $\mathbf{r}$ resolves $(x,y)$ and by contradiction that
$\mathbf{r^{-}}$ does not resolve $(x,y)$. Since $\mathbf{r}$ resolves
$(x,y)$, $\min_{1\leq l\leq k}\mathbf{(r_{1}+r)}_{\ell}\neq\min_{1\leq\ell\leq
k}\mathbf{(r_{2}+r)}_{\ell}$ and $\min_{1\leq\ell\leq
k-1}\mathbf{(r_{1}+r)}_{\ell}=\min_{1\leq\ell\leq
k-1}\mathbf{(r_{2}+r)}_{\ell}$ by Definition 11. So the minimum change in at
least one case. Assume by symmetry that $\min_{1\leq\ell\leq
k}\mathbf{(r_{1}+r)}_{\ell}\neq\min_{1\leq\ell\leq
k-1}\mathbf{(r_{1}+r)}_{\ell}$. So for $\ell<k$ we have
$\mathbf{(r_{1}+r)}_{\ell}>\mathbf{(r_{1}+r)}_{k}$. Since
$(\mathbf{r_{1})}_{k}=1$, it implies that $d(x,v)<d(x,v_{j})$ for all
$\ell\leq k-1$. A contradiction since $\\{v_{1},\ldots,v_{k-1}\\}$ separates
$x$ from $v$.

Assume now that $\mathbf{r^{-}}$ resolves $(x,y)$ and by contradiction that
$\mathbf{r}$ does not resolve $(x,y)$. Then by symmetry we can assume that
$\min_{1\leq j\leq k}\mathbf{(r_{1}+r)}_{j}\neq\min_{1\leq j\leq
k-1}\mathbf{(r_{1}+r)}_{j}$ meaning $\mathbf{(r_{1}+r)}_{k}<\min_{1\leq j\leq
k-1}\mathbf{(r_{1}+r)}_{j}$. Since $(\mathbf{r_{1})}_{k}=1$,
$\mathbf{(r_{1}+r)}_{k}\geq 1$ and $\mathbf{(r_{1}+r)}_{j}=2$ for $1\leq j\leq
k-1$. So $\mathbf{r_{1}}=(1,\ldots 1)$ which contradicts the fact that
${X_{i}\setminus\\{v\\}}$ separates $v$ from $x$.∎

###### Lemma 26

Let $I_{1}$ be a compatible instance of type $1$ and $S$ be a solution of
$I_{1}$, then $S$ is a solution of $I$.

###### Proof

Let us prove that the conditions of Definition 15 are satisfied.

(S1) Let $(x,y)$ be a pair of vertices of $T(X_{i})$. First assume that $x\neq
v$ and $y\neq v$. If the pair $(x,y)$ is not resolved by a vertex of $S$,
since $S$ is a solution for $I_{1}$, $(x,y)$ is resolved by a vector of
$D_{ext}{{(I)}}$. Let $\mathbf{r}\in D_{ext}{{(I)}}$ resolving the pair
$(x,y)$. As $I_{1}$ is compatible of type $1$, $\mathbf{r^{-}}\in
D_{ext}{{(I_{1})}}$. Then $\mathbf{r^{-}}$ resolves $(x,y)$ by Lemma 25. So we
can assume that $x=v$. The pair $(x,y)$ is also resolved by $S$ since
$(\mathbf{\mathbf{{d_{X_{j}}}(x_{1})}},(0,\ldots,0))\in D_{pair}{{(I_{1})}}$.
As $S$ is a solution for $I_{1}$, there is a vertex $s\in S$ that resolves the
pair $(x,y)$.

(S2) Let $\mathbf{r}\in D_{int}{{(I)}}$. Since $I_{1}$ is compatible with $I$,
there exists $\mathbf{r_{1}}\in D_{int}{{(I_{1})}}$ such that
$\mathbf{r}=\mathbf{r_{1}|1}$. Let $s\in S$ such that
$\mathbf{Tr_{X_{j}}}(s)=\mathbf{r_{1}}$, then
$\mathbf{Tr_{X_{i}}}(s)=\mathbf{r}$. Indeed, the vertex $v$ is not the closest
vertex of $X_{i}$ from $s$. If $s\in X_{j}$, that is clear. Otherwise $X_{j}$
is a separator between $s$ and $v$, so the shortest path between $s$ and $v$
crosses a vertex of $X_{j}$. Thus, $\mathbf{Tr_{X_{i}}}(s)=\mathbf{r_{1}|1}$.

(S3) Let $(\mathbf{r},\mathbf{t})\in D_{pair}{{(I)}}$. Let $x\in V(T(X_{i}))$
such that $\mathbf{\mathbf{{d_{X_{i}}}(x)}}=\mathbf{r}$ and $y\notin T(X_{i})$
such that $\mathbf{\mathbf{{d_{X_{i}}}(y)}}=\mathbf{t}$. Then
$\mathbf{\mathbf{{d_{X_{j}}}(x_{1})}}=\mathbf{r^{-}}$ and
$\mathbf{\mathbf{{d_{X_{j}}}(x_{2})}}=\mathbf{t^{-}}$ so the pair $(x,v)$ is
resolved by $S$ because $(\mathbf{r_{1}^{-}},\mathbf{r_{2}^{-}})$ belongs to
$D_{pair}{{(I_{1})}}$.

(S4) As $S_{I}=S_{I_{1}}$ we have $S\cap X_{i}=S_{I}$.∎

###### Lemma 27

Let $I_{2}$ be a compatible instance of type $2$ and $S$ a solution of
$I_{2}$, then $S^{\prime}=S\cup\\{v\\}$ is a solution of $I$.

###### Proof

Let us prove that the conditions of Definition 15 are satisfied.

(S1) Let $(x,y)$ be a pair of vertices of $T(X_{i})$ with $x\neq v$ and $y\neq
v$. If the pair $(x,y)$ is not resolved by a vertex of $S$, since $S$ is a
solution for $I_{2}$, $(x,y)$ is resolved by a vector $\mathbf{r}\in
D_{ext}{{(I_{2})}}$. By compatibility there exists $\mathbf{r^{\prime}}\in
D_{ext}{{(I)}}$ such that $\mathbf{r^{\prime-}}=\mathbf{r}$. By Lemma 25,
$\mathbf{r^{\prime}}$ resolves the pair $(x,y)$. Ultimately, if $v=x$ or
$v=y$, the pair $(x,y)$ is also resolved by $S^{\prime}$ as $v\in S^{\prime}$.

(S2) Let $\mathbf{r}\in D_{int}{{(I)}}$. If $\mathbf{r}=(1,\ldots,1,0)$, as
$\mathbf{Tr_{X_{i}}}(v)=\mathbf{r}$, there is a vertex in $S^{\prime}$ with
trace $\mathbf{r}$. Otherwise, as $I_{1}$ is compatible, there exists
$\mathbf{r_{1}}\in D_{int}{{(I_{2})}}$ such that
$\mathbf{r}=\mathbf{r_{1}|1}$. Let $s\in S$ such that
$\mathbf{Tr_{X_{j}}}(s)=\mathbf{r_{1}}$, then
$\mathbf{Tr_{X_{i}}}(s)=\mathbf{r}$. Indeed, the vertex $v$ is not the closest
vertex of $X_{i}$ from $s$. If $s\in X_{j}$, that’s clear. Otherwise $X_{j}$
is a separator between $s$ and $v$, so the shortest path between $s$ and $v$
crosses a vertex of $X_{j}$. Thus, $\mathbf{Tr_{X_{i}}}(s)=\mathbf{r_{1}|1}$.

(S3) Let $(\mathbf{r},\mathbf{t})\in D_{pair}{{(I)}}$. Let $x\in V(T(X_{i}))$
such that $\mathbf{\mathbf{{d_{X_{i}}}(x)}}=\mathbf{r}$ and $y\notin T(X_{i})$
such that $\mathbf{\mathbf{{d_{X_{i}}}(y)}}=\mathbf{t}$. Then
$\mathbf{\mathbf{{d_{X_{j}}}(x)}}=\mathbf{r^{-}}$ and
$\mathbf{\mathbf{{d_{X_{j}}}(y)}}=\mathbf{t^{-}}$ so the pair $(x,y)$ is
resolved by $S$ because $(\mathbf{r^{-}},\mathbf{t^{-}})$ belongs to
$D_{pair}{{(I_{1})}}$.

(S4) As $S_{I}=S_{I_{1}}\cup\\{v\\}$ we have $S\cap
X_{i}=S_{I_{1}}\cup\\{v\\}=S_{I}$.∎

###### Lemma 28

Let $I$ be an instance for an introduce node $i$. Let $\mathcal{F}_{1}(I)$ be
the set of instances $I_{1}$ for $i_{1}$ compatible with $I$ of type 1 and
$\mathcal{F}_{2}(I)$ be the set of instances $I_{2}$ for $i_{1}$ compatible
with $I$ of type 2. Then,

$\dim(I)\leq\min\;\\{\min_{I_{1}\in\mathcal{F}_{1}(I)}\;\\{\dim(I_{1})\\},\min_{I_{2}\in\mathcal{F}_{2}(I)}\;\\{\dim(I_{2})+1\\}\\}.$

###### Proof

The proof directly follows from the fact that, for any instance $I_{1}$ for
$j$ compatible with $I$, we can get a solution of $I$ of size $\dim(I_{1})$ if
$I_{1}\in\mathcal{F}_{1}$ by Lemma 26 and of size $\dim(I_{1})+1$ if
$I_{1}\in\mathcal{F}_{2}$ by Lemma 27. ∎

###### Lemma 29

Let $S$ be a solution for $I$ with $v\notin S$. Then there exists
$I_{1}\in\mathcal{F}_{1}$ such that $S$ is a solution of $I_{1}$.

###### Proof

Let $I_{1}$ be the instance defined by $S_{I_{1}}=S_{I}$,
$D_{int}{{(I_{1})}}=(\cup_{\mathbf{r}\in D_{int}{{(I)}}}\mathbf{r^{-}})$,
$D_{ext}{{(I_{1})}}=(\cup_{\mathbf{r}\in D_{ext}{{(I)}}}\mathbf{r^{-}})$ and
$D_{pair}{{(I_{1})}}=\cup_{(\mathbf{r},\mathbf{t})\in
D_{pair}{{(I)}}}(\mathbf{r^{-}},\mathbf{t^{-}}))$. One can easily remark that
$I_{1}$ is compatible with $I$ of type $1$.

We prove that $S$ is a solution of $I_{1}$.

(S1) Let $(x,y)$ be a pair of vertices of $T(X_{j})$. As $S$ is a solution for
$I$, either there exists $s\in S$ that resolves the pair $(x,y)$, or there is
a vector $\mathbf{r}\in D_{ext}{{(I)}}$ that resolves $(x,y)$. In the second
case, by construction of $I_{1}$, the vector $\mathbf{r^{-}}$ belongs to
$D_{ext}{{(I_{1})}}$ and resolves $(x,y)$ by Lemma 25. So the pair $(x,y)$ is
resolved in both cases.

(S2) Let $\mathbf{r}\in D_{int}{{(I_{1})}}$. By construction, there is
$\mathbf{r^{\prime}}\in D_{int}{{(I)}}$ such that
$\mathbf{r^{\prime-}}=\mathbf{r}$. Let $s\in S$ such that
$\mathbf{Tr_{X_{i}}}(s)=\mathbf{r^{\prime}}$, then
$\mathbf{Tr_{X_{j}}}(s)=\mathbf{r}$.

(S3) Let $(\mathbf{r},\mathbf{t})\in D_{pair}{{(I_{1})}}$, $x\in T(X_{i})$
with $\mathbf{\mathbf{{d_{X_{j}}}(x)}}=\mathbf{r}$ and $y\notin T(X_{j})$ with
$\mathbf{\mathbf{{d_{X_{j}}}(y)}}=\mathbf{t}$ with $d(x,X_{j})\leq 2$ and
$d(y,X_{j})\leq 2$. Let $(\mathbf{r^{\prime}},\mathbf{t^{\prime}})\in
D_{pair}{{(I)}}$ such that
$(\mathbf{r},\mathbf{t})=(\mathbf{r^{\prime-}},\mathbf{t^{\prime-}})$. First
$d(x,v)=d(x,X_{j})+1$ because $X_{j}$ separates $x$ and $v$. This is true for
any vertex of $X_{j}$ so the last component of $\mathbf{r^{\prime}}$ is
$d(x,X_{j})+1$. So $\mathbf{\mathbf{{d_{X_{i}}}(x)}}=\mathbf{r^{\prime}}$. If
$\mathbf{\mathbf{{d_{X_{i}}}(y)}}=\mathbf{t^{\prime}}$, then $(x,y)$ is
resolved by a vertex of $s$. Otherwise, as
$(\mathbf{r^{\prime}},\mathbf{t^{\prime}})\in D_{pair}{{(I)}}$, there exist a
vertex $z\notin T(X_{j})$ such that
$\mathbf{\mathbf{{d_{X_{i}}}(z)}}=\mathbf{t^{\prime}}$ and $s$ is $S$ that
resolves the pair $(x,z)$. Then $s$ resolves the pair $(x,y)$ because
$d(s,y)=d(s,z)$.

(S4) We have $S_{I}=S_{I_{1}}$ and $v\notin S_{I}$ so $S\cap X_{j}=S_{I_{1}}$.

Finally, $S$ is a solution of $I_{1}$ so $\dim(I_{1})\leq|S|\leq\dim(I)$. In
particular $\dim(I)\geq\min_{I_{1}\in\mathcal{F}_{1}}\;\\{\dim(I_{1})\\}$. ∎

###### Lemma 30

Let $S$ be a solution for $I$ of minimal size with $v\in S$. Then there exists
$I_{2}\in\mathcal{F}_{2}$ such that $S\setminus\\{v\\}$ is a solution of
$I_{2}$.

###### Proof

Let $I_{2}$ be the instance where $S_{I_{1}}=S_{I}\setminus\\{v\\}$,
$D_{int}{{(I_{2})}}=(\cup_{\mathbf{r}\in D_{int}{{(I)}}}\mathbf{r^{-}})$,
$D_{ext}{{(I_{2})}}=\\{\cup_{\mathbf{r}\in
D_{ext}{{(I)}}}\mathbf{r^{-}}\\}\cup\\{(0,\ldots 0)\\}$ and
$D_{pair}{{(I_{2})}}=\cup_{(\mathbf{r},\mathbf{t})\in
D_{pair}{{(I)}}}(\mathbf{r^{-}},\mathbf{t^{-}})$. One can easily remark that
$I_{2}$ is compatible with $I$ of type $2$.

We prove that $S$ is a solution of $I_{2}$. (S1) Let $(x,y)$ be a pair of
vertices of $T(X_{j})$. As $S$ is a solution for $I$, either there exists
$s\in S$ that resolves the pair $(x,y)$ or there is a vector $\mathbf{r}\in
D_{ext}{{(I)}}$ that resolves $(x,y)$. If $(x,y)$ is resolved by a vertex of
$S\setminus\\{v\\}$, then the pair $(x,y)$ is resolved in $I_{2}$. If $(x,y)$
is resolved by $v$, then the vector $(0,\ldots 0)$ of $D_{ext}{{(I_{2})}}$
resolves the pair. If $(x,y)$ is resolved by a vector $\mathbf{r}$ of
$D_{ext}{{(I)}}$, then by Lemma 25. So $\mathbf{r^{-}}$ resolves the pair
$(x,y)$ and $\mathbf{r^{-}}\in D_{ext}{{(I_{2})}}$ by construction.

(S2) Let $\mathbf{r}\in D_{int}{{(I_{1})}}$. By construction, there is
$\mathbf{r^{\prime}}\in D_{int}{{(I)}}$ such that
$\mathbf{r^{\prime-}}=\mathbf{r}$. Let $s\in S$ such that
$\mathbf{Tr_{X_{i}}}(s)=\mathbf{r^{\prime}}$, then
$\mathbf{Tr_{X_{j}}}(s)=\mathbf{r}$.

(S3) Let $(\mathbf{r},\mathbf{t})\in D_{pair}{{(I_{1})}}$, $x\in T(X_{i})$
with $\mathbf{\mathbf{{d_{X_{j}}}(x)}}=\mathbf{r}$ and $y\notin T(X_{j})$ with
$\mathbf{\mathbf{{d_{X_{j}}}(y)}}=\mathbf{t}$ with $d(x,X_{j})\leq 2$ and
$d(y,X_{j})\leq 2$. Let $(\mathbf{r^{\prime}},\mathbf{t^{\prime}})\in
D_{pair}{{(I)}}$ such that
$(\mathbf{r},\mathbf{t})=(\mathbf{r^{\prime-}},\mathbf{t^{\prime-}})$. First
$d(x,v)=d(x,X_{j})+1$ because $X_{j}$ separates $x$ and $v$. This is true for
any vertex of $X_{j}$ so the last component of $\mathbf{r^{\prime}}$ is
$d(x,X_{j})+1$. So $\mathbf{\mathbf{{d_{X_{i}}}(x)}}=\mathbf{r^{\prime}}$. If
$\mathbf{\mathbf{{d_{X_{i}}}(y)}}=\mathbf{t^{\prime}}$, then $(x,y)$ is
resolved by a vertex of $s$. Otherwise, as
$(\mathbf{r^{\prime}},\mathbf{t})\in D_{pair}{{(I)}}$, there exist a vertex
$z\notin T(X_{j})$ such that
$\mathbf{\mathbf{{d_{X_{i}}}(y)}}=\mathbf{t^{\prime}}$ and $s$ in $S$ that
resolves the pair $(x,z)$. Then $s$ resolves the pair $(x,y)$ because
$d(s,y)=d(s,z)$.

(S4) We have $S_{I}=S_{I_{1}}$ and $v\notin S_{I}$ so $S\cap X_{j}=S_{I_{1}}$.

Finally, $S\setminus\\{v\\}$ is a solution of $I_{2}$, thus
$\dim(I_{2})\leq|S-1|\leq\dim(I)$. In particular
$\dim(I)\geq\min_{I_{2}\in\mathcal{F}_{2}}\;\\{\dim(I_{2})+1\\}$.∎

Lemma 24 is a consequence of Lemmas 28, 29 and 30.

####  3.2.4 Forget node

We now consider an instance $I$ for an forget node $i$. Let $j$ be the child
of $i$ and $v\in V$ be such that $X_{j}=X_{i}\cup\\{v\\}$. Let
$X_{j}=\\{v_{1},\ldots,v_{k}\\}$ with $v=v_{k}$. The trees $T(X_{i})$ and
$T(X_{j})$ contain the same vertices, the definition of compatibility gives
conditions to have the same solution for $I$ and for an instance on the child
node.

We introduce three functions on vectors representing how the trace of a vertex
can be modified when one considers two separators that differ by one vertex.

###### Definition 31

Let $\mathbf{r}$ be any binary vector. We define the functions $f$, $f^{-}$
and $f^{+}$ which return a vector with one more component. The function
$f^{-}$ is defined as $\mathbf{f^{-}(r)}=\mathbf{r|\min(r_{i})}$ if
$\mathbf{r}$ is not constant and $\mathbf{f^{-}(r)}=\mathbf{r|(r_{1}-1)}$ if
$\mathbf{r}$ is constant. We define $f^{+}$ as
$\mathbf{f^{+}(r)}=\mathbf{r|\max(r_{i})}$ is $\mathbf{r}$ is not constant and
$\mathbf{f^{+}(r)}=\mathbf{r|(r_{1}+1)}$ if $\mathbf{r}$ is constant. We
define $f$ as $\mathbf{f(r)}=\mathbf{r|\min(r_{i})}$ is $\mathbf{r}$ is not
constant and $\mathbf{f(r)}=\mathbf{r|r_{1}}$ if $\mathbf{r}$ is constant.

The function $f$ is introduced only to deal with the case of constant vector.
These functions are defined to deal with the following case. Let $X_{i}$ and
$X_{j}$ be two bags such that $X_{i}=X_{j}\setminus\\{v\\}$ for some vertex
$v$. Let $x$ be any vertex, then $\mathbf{\mathbf{{d_{X_{j}}}(x)}}$ is equal
to $\mathbf{f(\mathbf{\mathbf{{d_{X_{i}}}(x)}})}$,
$\mathbf{f^{+}(\mathbf{\mathbf{{d_{X_{i}}}(x)}})}$ or
$\mathbf{f^{-}(\mathbf{\mathbf{{d_{X_{i}}}(x)}})}$. Moreover, if $X_{i}$
separates $x$ and $v$,
$\mathbf{\mathbf{{d_{X_{j}}}(x)}}=\mathbf{f^{+}(\mathbf{\mathbf{{d_{X_{i}}}(x)}})}$.

###### Definition 32

Let $I$ be an instance for a forget node $i$ and let $j$ be the child of $i$
and $v\in V$ such that $X_{i}=X_{j}\setminus\\{v\\}$. Let
$X_{j}=\\{v_{1},\ldots,v_{k}\\}$ with $v=v_{k}$. An instance $I_{1}$ for $j$
is compatible with $I$ if

  * •

(F1) $S_{I}=S_{I_{1}}\setminus\\{v\\}$.

  * •

(F2) For all $\mathbf{r}\in D_{ext}{{(I)}}$, $\mathbf{r|1}\in
D_{ext}{{(I_{1})}}$.

  * •

(F3) For all $\mathbf{r}\in D_{int}{{(I)}}$, $\mathbf{r|0}\in
D_{int}{{(I_{1})}}$ or $\mathbf{r|1}\in D_{int}{{(I_{1})}}$.

  * •

(F4) $\forall(\mathbf{r},\mathbf{t})\in D_{pair}{{(I)}}$, if there exist two
vertices $x\in T(X_{i})$ with
$\mathbf{\mathbf{{d_{X_{j}}}(x)}}=\mathbf{f^{-}(r)}$ (resp. $\mathbf{f(r})$,
$(\mathbf{f^{+}(r)}$) and $y\notin T(X_{i})$ with
$\mathbf{\mathbf{{d_{X_{j}}}(y)}}=\mathbf{f^{+}(t)}$ with $d(x,X_{j})\leq 2$
and $d(y,X_{j})\leq 2$ then $(\mathbf{f^{-}(r)},\mathbf{f^{+}(t)})$ (resp.
$(\mathbf{f(r}),\mathbf{f^{+}(t)})$, $(\mathbf{f^{+}(r)},\mathbf{f^{+}(t)})$)
belongs to $D_{pair}{{(I_{1})}}$.

###### Lemma 33

Let $I$ be an instance for a forget node $i$. Let $\mathcal{F}_{F}(I)$ be the
set of instances $I_{1}$ for $j$ compatible with $I$. Then,

$\dim(I)=\min_{I_{1}\in\mathcal{F}_{F}(I)}\;\\{\dim(I_{1})\\}.$

The end of this section is devoted to prove Lemma 33 by proving both
inequalities in a similar way than for join and introduce nodes.

We prove a technical lemma similar to Lemma 25 with a similar proof.

###### Lemma 34

Let $i$ be a forget node, $j$ be the child of $i$ and $v\in V$ such that
$X_{i}=X_{j}\setminus\\{v\\}$. Let $(x,y)$ be a pair of vertices of
$T(X_{j})$. Let $\mathbf{r}$ be a binary vector of size $k$ with
$\mathbf{r}_{k}=1$. Then $\mathbf{r}$ resolves $(x,y)$ if and only if
$\mathbf{r^{-}}$ resolves $(x,y)$.

###### Proof

Let $\mathbf{t_{1}}=\mathbf{Tr_{X_{i}}}(x)$ and
$\mathbf{t_{2}}=\mathbf{Tr_{X_{i}}}(y)$. Assume $\mathbf{r}$ resolves $(x,y)$
and by contradiction that $\mathbf{r^{-}}$ does not resolve $(x,y)$. As
$\mathbf{r}$ resolves $(x,y)$ we have by Definition 11, $\min_{1\leq l\leq
k}\mathbf{(t_{1}+r)}_{l}\neq\min_{1\leq l\leq k}\mathbf{(t_{2}+r)}_{l}$ and
$\min_{1\leq l\leq k-1}\mathbf{(t_{1}+r)}_{l}\neq\min_{1\leq l\leq
k-1}\mathbf{(t_{2}+r)}_{l}$. So the minimum change in at least one case,
assume by symmetry that $\min_{1\leq l\leq
k}\mathbf{(t_{1}+r)}_{l}\neq\min_{1\leq i\leq k-1}\mathbf{(t_{1}+r)}_{l}$.
Thus, for $l<k$, we have $\mathbf{(t_{1}+r)}_{l}>\mathbf{(t_{1}+r)}_{k}$. We
know $\mathbf{r}_{k}=1$, so, for $l<k$, we have $\mathbf{(t_{1}+r)}_{l}>1$.
That gives $\mathbf{r}=(1,\ldots,1)$ which contradicts the fact that ${X_{j}}$
separates $v$ from $x_{1}$, one vertex of $X_{j}$ is strictly closer to $x$
than $v$. Assume $\mathbf{r^{-}}$ resolves $(x,y)$ and by contradiction that
$\mathbf{r}$ does not resolve $(x,y)$. Then, by symmetry we can assume that
$\min_{1\leq l\leq k}\mathbf{(t_{1}+r)}_{l}\neq\min_{1\leq l\leq
k-1}\mathbf{(t_{1}+r)}_{l}$, meaning $\mathbf{(t_{1}+r)}_{k}<\min_{1\leq l\leq
k-1}\mathbf{(t_{1}+r)}_{l}$. We know $\mathbf{r}_{k}=1$ so
$\mathbf{(t_{1}+r)}_{k}\geq 1$ and $\mathbf{(t_{1}+r)}_{l}=2$ for $1\leq l\leq
k-1$. So $\mathbf{r}=(1,\ldots 1)$ which contradicts the fact that ${X_{j}}$
separates $v$ from $s$.∎

###### Lemma 35

Let $I_{1}\in\mathcal{F}_{F}(I)$ and $S$ be a solution for $I_{1}$, then $S$
is a solution for $I$.

###### Proof

Let us prove that the conditions of Definition 15 are satisfied.

(S1) Let $(x,y)$ be a pair of vertices of $T(X_{i})$. As $T(X_{i})=T(X_{j})$,
the pair is resolved by a vertex of $S$ or by a vector $\mathbf{r}$ of
$D_{ext}{{(I_{1})}}$. If $(x,y)$ is resolved by $\mathbf{r}\in
D_{ext}{{(I_{1})}}$ then by Lemma 34, $\mathbf{r^{-}}$ resolves the pair
$(x,y)$ and $\mathbf{r^{-}}\in D_{ext}{{(I)}}$ by compatibility.

(S2) Let $\mathbf{r}\in D_{int}{{(I)}}$. By compatibility, $\mathbf{r|0}\in
D_{int}{{(I_{1})}}$ or $\mathbf{r|1}\in D_{int}{{(I_{1})}}$. Let $s\in S$ such
that $\mathbf{Tr_{X_{i}}}(s)\in\\{\mathbf{r|0},\mathbf{r|1}\\}$, then
$\mathbf{Tr_{X_{j}}}(s)=\mathbf{r}$.

(S3) Let $(\mathbf{r},\mathbf{t})\in D_{pair}{{(I)}}$, $x\in V(T(X_{i}))$ and
$y\notin T(X_{i})$ such that $\mathbf{\mathbf{{d_{X_{i}}}(x)}}=\mathbf{r}$ and
$\mathbf{\mathbf{{d_{X_{i}}}(y)}}=\mathbf{t}$. Assume also $d(x,X_{i})\leq 2$
and $d(y,X_{i})\leq 2$. The set $X_{j}$ separates $v$ and $y$ so
$\mathbf{\mathbf{{d_{X_{j}}}(y)}}=f^{+}(t)$. As
$\mathbf{\mathbf{{d_{X_{j}}}(x)}}$ is equal either to $\mathbf{f^{-}(r)}$,
$\mathbf{f(r)}$ or to $\mathbf{f^{+}(r)}$, the pair $(x,y)$ is resolved by a
vertex of $S$.

(S4) is clear.∎

###### Lemma 36

Let $S$ be a solution for $I$ of minimal size. Then there exists $I_{1}$
compatible with $I$ such that $S$ is a solution of $I_{1}$.

###### Proof

Let $S$ be an solution for $I$ of minimal size. Let $I_{1}$ be the following
instance: $S_{I_{1}}=S\cap X_{j}$,
$D_{int}{{(I_{1})}}=\\{\mathbf{Tr_{X_{j}}}(s),s\in
S\\},D_{ext}{{(I_{1})}}=\\{\mathbf{r}|1,\mathbf{r}\in
D_{ext}{{(I)}}\\},D_{pair}{{(I_{1})}}=\\{(\mathbf{f^{-}(r)},\mathbf{f^{+}(t)}),(\mathbf{r},\mathbf{t})\in
D_{pair}{{(I)}}\\}\cup\\{(\mathbf{f(r)},\mathbf{f^{+}(t)}),(\mathbf{r},\mathbf{t})\in
D_{pair}{{(I)}}\\}\cup\\{(\mathbf{f^{+}(r)},\mathbf{f^{+}(t)})(\mathbf{r},\mathbf{t})\in
D_{pair}{{(I)}}\\}$. We first check the compatibility.

(F1), (F2) and (F4) are straightforward.

(F3) Let $\mathbf{r}\in D_{int}{{(I)}}$ and $s\in S$ such that
$\mathbf{Tr_{X_{i}}}(s)=\mathbf{r}$. By construction,
$\mathbf{r^{\prime}}=\mathbf{Tr_{X_{j}}}(s)$ belongs to $D_{int}{{(I_{1})}}$
and $\mathbf{r^{\prime}}=\mathbf{r^{-}}$ so $\mathbf{r|0}\in
D_{int}{{(I_{1})}}$ or $\mathbf{r|1}\in D_{int}{{(I_{1})}}$.

We prove now $S$ is a solution for $I_{1}$.

(S1) Let $(x,y)$ be a pair of vertices of $T(X_{j})$. As $T(X_{i})=T(X_{j})$,
the pair is resolved by a vertex of $S$ or by a vector $\mathbf{r}$ of
$D_{ext}{{(I)}}$. If $(x,y)$ is resolved by $\mathbf{r}\in D_{ext}{{(I)}}$
then by Lemma 34, $\mathbf{r|1}$ resolves the pair $(x,y)$ and
$\mathbf{r|1}\in D_{ext}{{(I_{1})}}$ by construction.

(S2) Let $\mathbf{r}\in D_{int}{{(I_{1})}}$. By construction there is $s\in S$
such that $\mathbf{Tr_{X_{j}}}(s)=\mathbf{r}$.

(S3) Let $(\mathbf{r},\mathbf{t})\in D_{pair}{{(I_{1})}}$, $x\in V(T(X_{j}))$
and $y\notin T(X_{j})$ such that $\mathbf{\mathbf{{d_{X_{j}}}(x)}}=\mathbf{r}$
and $\mathbf{\mathbf{{d_{X_{j}}}(y)}}=\mathbf{t}$. Assume also $d(x,X_{i})\leq
2$ and $d(y,X_{i})\leq 2$. Then $\mathbf{Tr_{X_{j}}}(y)=f^{+}(\mathbf{t})$ and
$\mathbf{Tr_{X_{j}}}(x)\in\\{\mathbf{f^{-}(r)},\mathbf{f(r)},\mathbf{f^{+}(r)}\\}$.
Since $S$ is a solution of $I$, the pair $(x,y)$ is resolved by a vertex of
$S$.

(S4) is clear.∎

Lemma 33 is a consequence of Lemmas 35 and 36.

###  3.3 Algorithm

Given as input a nice clique tree, the algorithm computes the extended metric
dimension of all the possible instances bottom up from the leaves. The
algorithm computes the values for leaves using Lemma 18, for join nodes using
Lemma 20, for introduce nodes using Lemma 24 and forget nodes using Lemma 33.
The correction of the algorithm is straightforward by these lemmas.

We denote this algorithm by $IMD$ in the following which takes as input a nice
clique tree $T$ and outputs the minimal size of a resolving set of $G$
containing the root of $T$.

##  4 Proof of Theorem 1.1

Let us finally explain how we can compute the metric dimension of $G$.

###### Lemma 37

The metric dimension of $G$ is $\min_{v\in G}\\{IMD(T(v))\\}$ where $T(v)$ is
a nice clique tree of $G$ rooted in $v$.

###### Proof

For any input, $IMD(T(v))$ outputs the size of a resolving set of $G$. So,
$\min_{v\in G}\\{IMD(T(v))\\}\geq\dim(G)$. Let $S$ be a minimum resolving set
of $G$ and let $v\in S$. By Lemma 17, $IMD(T(v))$ outputs the minimum size of
a resolving set containing $v$ so $\min_{v\in G}\\{IMD(T(v))\\}\leq\dim(G)$
which complete the proof. ∎

In particular, $n$ executions of the $IMD$ algorithm with different inputs are
enough to compute the metric dimension. Lemma 3 ensures that we can find for
any vertex $v$ of $G$ a nice clique tree in linear time, the last part is to
compute the complexity of the $IMD$ algorithm.

To get the announced complexity, we add a first step to the $IMD$ algorithm:
for each bag $X$, we compute $d_{\leq 2}(X)\cap T(X)$ and $d_{\leq
2}(X)\cap(G\setminus T(X))$. This computation can be done in $O(n^{2})$ times
(recall that $T$ has a linear number of bag by Lemma 3). Note also that the
size of $d_{\leq 2}(X)\cap T(X)$ and $d_{\leq 2}(X)\cap(G\setminus T(X))$
depends only of $|X_{i}|$.

To compute the complexity, we need to compute the number of instances and the
time to solve an instance. For simplicity we let $\alpha(k):=2^{k}\cdot
2^{2^{k}}\cdot 2^{2^{k}}\cdot 2^{4^{2k}}$.

###### Lemma 38

Let $I$ be any instance for a node $i$ and assume $\dim(I^{\prime})$ is known
for every instance $I^{\prime}$ compatible with $I$ for every child of $i$ .
Then $\dim(I)$ can be computed in time $O(f(|X_{i}|))$ for a computable
function $f$.

###### Proof

If $i$ is a leaf node then $\dim(I)$ can be computed in constant time by Lemma
18. Otherwise, let us prove that one can compute for all the instances on the
child nodes (at most two child nodes) all the compatible instances. Given a
$5$-uplet $(X_{i},S_{I},D_{int}{{(I)}},D_{ext}{{(I)}},D_{pair}{{(I)}})$,
checked if it is an instance according to Definition 15 can be done in time
$O(|I|\cdot g(|X_{i}|))$ where $g$ gives the size of $d_{\leq 2}(X_{i})\cap
T(X_{i})$ plus the size $d_{\leq 2}(X_{i})\cap(G\setminus T(X_{i}))$. The
number of such $5$-uplet
$(X_{i},S_{I},D_{int}{{(I)}},D_{ext}{{(I)}},D_{pair}{{(I)}})$ is bounded by
$\alpha(|X_{i}|)$. Thus, identifying the instances among all the $5$-uplet ca
be done in time depending only of $|X_{i}|$.

Checking the compatibility can be done in a time that only depends on
$|X_{i}|$. Condition (J5) can be checked in time $O(|X_{i}|^{2}\cdot|I|)$ to
check for each pair of vectors if a vector of $D_{ext}{{(I)}}$ resolves it.
Condition (I5) can be checked in time $O(|X_{i}|)$ and condition (F4) in time
$O(|X_{i}|^{2})$. The other compatibility conditions can be checked in time
$O(|I|)$ and by Definition 15, $|I|$ is bounded by a function of $|X_{i}|$.
Then, computing the minimum using the formulas of Lemmas 20, 24 and 33 can be
done in time $O(\alpha(X_{i}))$. Ultimately the computation of $\dim(I)$ is
done in time bounded by a function of $X_{i}$. ∎

###### Corollary 39

The algorithm for $IMD$ runs in time $O(n(T)^{2}+n(T)\cdot f(\omega))$ where
$n(T)$ is the number of vertices of the input tree $T$ and $f=O(k^{2}\cdot
2^{O(4^{2^{k}})})$ is a function that only depends on the size of a maximum
clique $\omega$.

###### Proof

By definition of the treewidth, for any bag $X$ of $T$, $|X|\leq\omega$. The
first step of computation to get $d_{\leq 2}(X_{i})\cap T(X_{i})$ and $d_{\leq
2}(X_{i})\cap(G\setminus T(X_{i}))$ takes time $O(n^{2})$. Then, the number of
instances to compute for each vertex of $T$ is bounded by $\alpha(\omega)$ and
each instance $I$ can be computed in time bounded $O(\omega^{2}\cdot|I|)$ by
Lemma 38. ∎

We now have all the ingredients to prove Theorem 1.1:

###### Proof

For each vertex $v$ of $G$, one can compute a nice clique tree of size at most
$7n$ according to Lemma 3. Given this clique tree, the $IMD$ algorithm outputs
the size of a smallest resolving set containing $v$ by Lemma 17 in time
$O(n(T)^{2}+n(T)\cdot f(\omega))$ for a computable function $f$ according to
Corollary 39. Repeat this for all vertices of $G$ permits to compute the
metric dimension of $G$ by Lemma 37 in time $O(n^{3}+n^{2}\cdot f(\omega))$.∎

## References

  * [BFGR16] Rémy Belmonte, Fedor V. Fomin, Petr A. Golovach, and M. S. Ramanujan.  Metric dimension of bounded tree-length graphs.  CoRR, abs/1602.02610, 2016.
  * [BP21] Édouard Bonnet and Nidhi Purohit.  Metric dimension parameterized by treewidth.  Algorithmica, 83(8):2606–2633, 2021.
  * [CLZ15] Gary Chartrand, Linda Lesniak, and Ping Zhang.  Graphs and Digraphs.  Chapman and Hall/CRC, 6th edition, 2015.
  * [Dir61] Gabriel Andrew Dirac.  On rigid circuit graphs.  In Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, volume 25, pages 71–76. Springer, 1961.
  * [DPSvL12] Josep Díaz, Olli Pottonen, Maria Serna, and Erik Jan van Leeuwen.  On the complexity of metric dimension.  In Leah Epstein and Paolo Ferragina, editors, Algorithms – ESA 2012, 2012.
  * [EFKY15] Linda Eroh, Paul Feit, Cong X Kang, and Eunjeong Yi.  The effect of vertex or edge deletion on the metric dimension of graphs.  J. Comb, 6(4):433–444, 2015.
  * [ELW15] Leah Epstein, Asaf Levin, and Gerhard J Woeginger.  The (weighted) metric dimension of graphs: hard and easy cases.  Algorithmica, 72(4):1130–1171, 2015.
  * [FMN+17] Florent Foucaud, George B Mertzios, Reza Naserasr, Aline Parreau, and Petru Valicov.  Identification, location-domination and metric dimension on interval and permutation graphs. ii. algorithms and complexity.  Algorithmica, 78(3):914–944, 2017.
  * [GHK+22] Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, and Yota Otachi.  Exploring the gap between treedepth and vertex cover through vertex integrity.  Theoretical Computer Science, 918:60–76, 2022.
  * [GJ79] Garey and Johnson.  A Guide to the Theory of NP-completeness.  Journal of algorithms, 1979.
  * [HM75] Frank. Harary and Robert. A. Melter.  On the metric dimension of a graph.  Ars Combinatoria, 2:191-195, 1975.
  * [HN13] Sepp Hartung and André Nichterlein.  On the parameterized and approximation hardness of metric dimension.  In 2013 IEEE Conference on Computational Complexity, pages 266–276. IEEE, 2013.
  * [Klo94] Ton Kloks.  Treewidth: computations and approximations.  Springer, 1994.
  * [LP22] Shaohua Li and Marcin Pilipczuk.  Hardness of metric dimension in graphs of constant treewidth.  Algorithmica, 84(11):3110–3155, 2022.
  * [Sla75] Peter J. Slater.  Leaves of trees.  Congressus Numerantium, 14, 1975.