# On Finding the Best and Worst Orientations for the Metric Dimension

Julio Araujo, Julien Bensmail, Victor Campos, Frédéric Havet, Ana Karolinna

Maia de Oliveira, Nicolas Nisse, Ana Silva

► To cite this version:

Julio Araujo, Julien Bensmail, Victor Campos, Frédéric Havet, Ana Karolinna Maia de Oliveira, et al.. On Finding the Best and Worst Orientations for the Metric Dimension. Algorithmica, 2023, 85 (10), pp.2962-3002. 10.1007/s00453-023-01132-0. hal-04271379

HAL Id: hal-04271379

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

Submitted on 6 Nov 2023

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 CC BY 4.0 - Attribution - International License
# On finding the best and worst orientations for the metric dimension*

Julio Araujo¹,³, Julien Bensmail², Victor Campos¹, Frédéric Havet², A. Karolinna Maia¹,³, Nicolas Nisse (nicolas.nisse@inria.fr)*, and Ana Silva¹

¹Universidade Federal do Ceará, Fortaleza, Brazil

²Université Côte d'Azur, CNRS, Inria, I3S, France

³LIRMM, CNRS, Université de Montpellier, Montpellier, France

November 6, 2023

## Abstract

The (directed) metric dimension of a digraph $D$, denoted by $\overrightarrow{\text{BOMD}}(D)$, is the size of a smallest subset $S$ of vertices such that every two vertices of $D$ are distinguished via their distances from the vertices in $S$.

In this paper, we investigate the graph parameters BOMD($G$) and WOMD($G$) which are respectively the smallest and largest metric dimension over all orientations of $G$. We show that those parameters are related to several classical notions of graph theory and investigate the complexity of determining those parameters. We show that $\text{BOMD}(G) = 1$ if and only if $G$ is hypotraceable (that is has a path spanning all vertices but one), and deduce that deciding whether $\text{BOMD}(G) \le k$ is NP-complete for every positive integer $k$. We also show that $\text{WOMD}(G) \ge \alpha(G) - 1$, where $\alpha(G)$ is the stability number of $G$. We then deduce that for every fixed positive integer $k$, we can decide in polynomial time whether $\text{WOMD}(G) \le k$.

The most significant results deal with oriented forests. We provide a linear-time algorithm to compute the metric dimension of an oriented forest and a linear-time algorithm that, given a forest $F$, computes an orientation $D^-$ with smallest metric dimension (i.e. such that $\overrightarrow{\text{BOMD}}(D^-) = \text{BOMD}(F)$) and an orientation $D^+$ with largest metric dimension (i.e. such that $\overrightarrow{\text{BOMD}}(D^+) = \text{WOMD}(F)$).

**Keywords:** metric dimension; resolving sets; undirected graphs; digraphs.

## 1 Introduction

Let $G$ be an undirected connected graph. The distance $\text{dist}_G(u, v)$ (or simply $\text{dist}(u, v)$) when no ambiguity is possible) between two vertices $u$ and $v$ of $G$ is the length of a shortest path joining $u$ and $v$. A vertex $w$ is said to resolve (or distinguish) $u$ and $v$ if $\text{dist}(u, w) \neq \text{dist}(v, w)$. Note that $w$ resolves $u$ and $v$ as soon as $u = w$ or $v = w$. A set $R \subseteq V(G)$ of vertices is called resolving if for every two distinct vertices $u, v$ of $G$, there is a vertex $w \in R$ that resolves them. Note that $R$ may be empty. The metric dimension $\text{MD}(G)$ of $G$ is the size of its smallest resolving sets. Since the vertex set of any graph is obviously a resolving set, the metric dimension parameter is well defined for every graph. These notions were first introduced and studied by Harary and Melter [13] and Slater [19], in particular because of numerous real-life applications.

Distances can also be measured in digraphs, and it thus makes sense extending the notions of resolving sets and metric dimension to the directed context. Recall that, in a digraph $D$, for any two vertices $u$ and $v$, the distance $\text{dist}_D(u, v)$ (or simply $\text{dist}(u, v)$) from $u$ to $v$, is the length of a shortest directed path from $u$ to $v$. In particular, it is possible that $\text{dist}(u, v) \neq \text{dist}(v, u)$.

<footnote>*This work is funded by the STIC-AmSud project GALOP and the french Agence Nationale de la Recherche under contract Digraphs ANR-19-CE48-0013-01. Corresponding author: Nicolas Nisse nicolas.nisse@inria.fr</footnote>
Also, in case there is no directed path from $u$ to $v$, the distance from $u$ to $v$ is not finite, in which case we set $\text{dist}(u, v) = +\infty$. As in the undirected context, we say that $u$ and $v$ are resolved or distinguished by a vertex $w$ if $\text{dist}(w, u) \neq \text{dist}(w, v)$. An important point to raise is that, throughout this work, we consider the infinite distance as a particular distance value, that can be used to distinguish vertices. In particular, we assume that $w$ distinguishes $u$ and $v$ whenever $\text{dist}(w, u) = +\infty$ and $\text{dist}(w, v) \neq +\infty$ (since $v$ can be reached from $w$ but $u$ cannot, it is certified by $w$ that $u$ and $v$ are different vertices). Following the same reasoning, $w$ does not distinguish $u$ and $v$ when $\text{dist}(w, u) = \text{dist}(w, v) = +\infty$. Again, a resolving set $R \subseteq V(D)$ is a set of vertices such that every two distinct vertices $u$ and $v$ of $D$ are distinguished by a vertex in $R$. The metric dimension $\overrightarrow{\text{MD}}(D)$ of $D$ is the size of a smallest resolving set of $D$. As in the undirected context, the vertex set of any digraph is a resolving set; thus, $\overrightarrow{\text{MD}}(D)$ is defined for every digraph $D$.

The first study of the metric dimension of digraphs may be attributed to Chartrand, Rains, and Zhang [6], who opened the way for several further investigations on the topic [9, 10, 15, 16, 17]. It is however important to emphasize that their definitions of resolving sets and metric dimension of digraphs differ from ours because they do not consider the infinite distance as valid. This imposes all vertices to be reachable from every vertex of the resolving set. In particular, in contrast to ours, their notion of metric dimension is not defined for many digraphs.

Recall that an *orientation* $D$ of an undirected graph $G$ is obtained by assigning to every edge $uv$ of $G$ one direction, either from $u$ to $v$ or from $v$ to $u$. An *oriented graph* is an orientation of some undirected simple graph; in particular, oriented graphs and digraphs differ in that the former cannot have directed cycles of length 2.

Most of the results we present concern the study of the maximum and/or the minimum value of the metric dimension among all possible orientations of a given simple graph. However, before turning to the main topic of this paper, we first consider, in Section 2, the complexity of the following problem.

**Directed Metric Dimension (DMD)**

**Input:** A digraph $D$, and an integer $k$.

**Question:** Do we have $\overrightarrow{\text{MD}}(D) \le k$?

The undirected analogue of DMD, *Undirected Metric Dimension (UMD, for short)*, is well known to be NP-complete, even when restricted to particular graph instances, such as planar graphs [8] and graphs of diameter 2 [12]. Replacing every edge $uv$ of a given undirected graph $G$ by two symmetric arcs $uv$ and $vu$, results in a digraph $D$ in which the distances between the vertices are the same as the ones in $G$. Noticing this operation, several authors [1, 17] established the computational hardness of DMD. Using slight modifications of this operation, it is proved in [17] that DMD remains NP-complete when restricted to strongly-connected oriented graphs. A natural question is on the behaviour of DMD for other classes of digraphs. We show in Subsection 2.2 that DMD can be solved in polynomial time in oriented forests, and in Subsection 2.3 that DMD is NP-hard in bipartite acyclic digraphs.

We then consider, through Sections 3 to 5, the following questions: For a given undirected graph $G$, what are, with respect to the metric dimension, its best (resp. worst) orientations? By that, we mean the orientations of $G$ for which the size of a smallest resolving set is the smallest (resp. largest) among all possible orientations of $G$. More precisely, we consider the two associated parameters

$$ \text{BOMD}(G) = \min \{ \overrightarrow{\text{MD}}(D) : D \text{ is an orientation of } G \} $$

and

$$ \text{WOMD}(G) = \max \{ \overrightarrow{\text{MD}}(D) : D \text{ is an orientation of } G \}. $$

To the best of our knowledge, the metric dimension of particular orientations of graphs was first studied by Chartrand, Rains, and Zhang in [6], who notably considered the existence of orientations with given metric dimension (following their conventions). Recently, Bensmail, Mc Inerney, and Nisse [2] considered the maximum size of a smallest resolving set over all strongly-connected orientations of a graph (of some particular families). In this paper, we study the parameters BOMD and WOMD with a special emphasis on forests.
In Section 3, we consider several aspects related to the parameter BOMD. We first show that for a graph G and any fixed positive integer k, it is NP-complete to decide whether BOMD(G) ≤ k. Next, in Theorem 3.7, we show that we always have BOMD(G) ≤ pc(G), where pc(G) (the path cover number of G) is the minimum number of vertex-disjoint paths whose union contains all vertices of G. We also show that this bound can be very loose in the sense that for every positive integer k, there are graphs G such that BOMD(G) = 2 and pc(G) = k. In Subsection 3.3, we then establish the following bounds for every tree T:

$$ \lf(T) - \text{hb}(T) - 1 \leq \text{BOMD}(T) \leq \lf(T) - 1, $$

where $\lf(T)$ is the number of leaves (vertices of degree 1) in T, and $\text{hb}(T)$ is the number of vertices of degree at least 3 that are connected to a leaf via a path whose internal vertices have degree 2. We also show that those bounds are tight.

We then turn our attention to the parameter WOMD in Section 4. We first show that, for every graph G, we always have WOMD(G) ≥ α(G) − 1, where α(G) is the size of a largest stable set in G, and WOMD(G) ≥ ⌊ ω(G) 2 ⌋, where ω(G) is the size of a largest clique in G. Using Ramsey’s Theorem, we deduce that WOMD(G) goes to infinity with the order of G: for every k, there is a constant Ck such that if |V(G)| ≥ Ck then WOMD(G) ≥ k. This implies that either WOMD(G) ≥ k trivially holds, or |V(G)| < Ck and again we can check WOMD(G) ≥ k in constant time (function of k). Next, in Subsection 4.2, we consider forests and show that WOMD(F) ∈ {α(F) − 1, α(F)} for every forest F. Hence, there are two kinds of forests F with respect to WOMD: (α − 1)-forests F for which WOMD(F) = α(F) − 1, and α-forests F for which WOMD(F) = α(F). This suggests that it could be possible to characterise the α-forests (and thus the (α − 1)-forests). To do so, it suffices to characterise the α-trees (i.e. trees T such that WOMD(T) = α(T)). Indeed, as observed in Proposition 4.14, a forest is an α-forest if, and only if, it is the disjoint union of α-trees. We show that all stars are α-trees, and that a path of order n is an (α − 1)-tree if, and only if, n ≡ 1 mod 4. We also give constructions to build α-trees (resp. (α − 1)-trees) from smaller ones.

In Section 5, we give a dynamic-programming algorithm that, given a forest F, computes BOMD(F) and WOMD(F) in linear time. Regarding our investigations in Subsection 4.2, a con- sequence is that there is an efficient algorithmic way to recognize α-forests from (α − 1)-forests.

We conclude this work in Section 6, by raising directions for further work on the topic.

# 2 Metric dimension of oriented graphs

## 2.1 Terminology, notation, and preliminary results

The *trivial digraph* is the digraph with one vertex and no arcs.

For any digraph D, we denote its vertex set by V(D), and its arc set by A(D). Let v be a vertex of D. The *out-neighbourhood* of v in D, denoted by $N_D^+(v)$ or simply $N^+(v)$ when D is clear from the context, is the set of *out-neighbours* of v: $N^+(v) = \{w \in V(D) | vw \in A(D)\}$. Similarly, the *in-neighbourhood* of v in D, denoted by $N_D^-(v)$ or simply $N^-(v)$, is the set of *in-neighbours* of v: $N^-(v) = \{w \in V(D) | wv \in A(D)\}$. A vertex v ∈ V(D) is a *source* (resp., a *sink*) if $N^-(v) = \emptyset$ (resp., if $N^+(v) = \emptyset$). We denote by S(D) the set of *sources* of D. The *maximum degree* of D is the maximum degree of its underlying undirected graph.

A digraph is *strongly connected* (or *strong*, for short) if $\text{dist}(u, v)$ and $\text{dist}(v, u)$ are finite for every two vertices u, v, i.e. there exist directed paths in both directions between any two vertices. A digraph is *connected* if its underlying graph is connected. The *connected components* of a digraph are its maximal connected subdigraphs with respect to inclusion. Hence, the connected components of a digraph correspond to the connected components of its underlying graph.

For a subset $R \subseteq V(D)$ of vertices of D, an *infinite vertex* v (with respect to R) is a vertex v / ∈ R for which, for every u ∈ R, we have $\text{dist}(u, v) = +\infty$. For a graph or digraph, a resolving set is called *minimum* if it has minimum size (which is the value of the metric dimension).

The following proposition is immediate from the definition and we often use it without any reference.
**Proposition 2.1.** Let $G$ be a graph or a digraph, and let $R$ be a resolving set of $G$. Then every $R'$ such that $R \subseteq R' \subseteq V(G)$ is also a resolving set of $G$.

**Proposition 2.2.** Let $D$ be a digraph, and let $R \subseteq V(D)$ be a resolving set of $D$. Then, with respect to $R$, there is at most one infinite vertex, and, if any, it must be a source.

*Proof.* If $D$ has two distinct infinite vertices $u, v$ with respect to $R$, then $u$ and $v$ cannot be distinguished, contradicting that $R$ is resolving. Furthermore, if $u$ is the only infinite vertex with respect to $R$, then it must be a source, as otherwise there would be a directed path from a vertex $w \in V(D)$ to $u$. If $w \in R$, this contradicts that $u$ is infinite. Otherwise, since $u$ is the single infinite vertex, there must be a directed path from a vertex of $R$ to $w$ and so, there is a directed path from a vertex of $R$ to $u$, contradicting that $u$ is infinite. □

By Proposition 2.2, there are two kinds of resolving sets: the strong ones with no infinite vertex and the weak ones with one infinite vertex. For a digraph $D$, the strong metric dimension of $D$, denoted by $\overrightarrow{MD}^*(D)$, is the minimum size of a strong resolving set of $D$. Proposition 2.2 implies that the metric dimension and the strong metric dimension are strongly related.

**Corollary 2.3.** $\overrightarrow{MD}(D) \le \overrightarrow{MD}^*(D) \le \overrightarrow{MD}(D) + 1$ for all digraphs $D$.

*Proof.* $\overrightarrow{MD}(D) \le \overrightarrow{MD}^*(D)$ directly follows from the definitions. Let $R$ be a minimum resolving set. If it is strong, then $\overrightarrow{MD}^*(D) = \overrightarrow{MD}(D)$. If it is weak, then, by Proposition 2.2, there is a unique infinite vertex $w$ with respect to $R$. Then $R \cup \{w\}$ is a strong resolving set of $D$. Thus $\overrightarrow{MD}^*(D) \le \overrightarrow{MD}(D) + 1$. □

The empty set is a resolving set of the trivial digraph $D_1$, and $V(D_1)$ is its unique strong resolving set. Thus $\overrightarrow{MD}^*(D_1) = \overrightarrow{MD}(D_1) + 1$. It is easy to construct other digraphs $D$ such that $\overrightarrow{MD}^*(D) = \overrightarrow{MD}(D) + 1$. For instance, any digraph $D$ having a source that is universal, i.e. that is adjacent to all other vertices, satisfies this equality (for a proof, see Lemma 2.9). On the other hand, if $D$ is a non-trivial strong digraph, then every resolving set of $D$ is a strong resolving set of $D$, and so $\overrightarrow{MD}(D) = \overrightarrow{MD}^*(D)$. Thus, both bounds of Corollary 2.3 can be attained.

Another consequence of Proposition 2.2 is the following. Recall that, for a given digraph $D$, we denote by $S(D)$ its set of sources.

**Proposition 2.4.** If $D$ is a digraph and $R$ is a resolving set of $D$, then $|R \cap S(D)| \ge |S(D)| - 1$. If $R$ is strong, then $S(D) \subseteq R$. Hence $\overrightarrow{MD}^*(D) \ge |S(D)|$ and $\overrightarrow{MD}(D) \ge |S(D)| - 1$.

*Proof.* Let $R$ be a resolving set of $D$. Observe that, for any $s \in S(D)$ and $v \in V(D) \setminus \{s\}$, we have $\text{dist}(v, s) = +\infty$. Hence, if a source $s$ is not in $R$, then $s$ is an infinite vertex.

Therefore, as $R$ has at most one infinite vertex (by Proposition 2.2), $|R \cap S(D)| \ge |S(D)| - 1$. Moreover, if $R$ is strong, then it has no infinite vertex and thus $S(D) \subseteq R$. □

In the next result, we note that the (strong) metric dimension of a digraph can, essentially, be deduced from the (strong) metric dimension of its connected components.

**Proposition 2.5.** Let $C_1, \dots, C_p$ be the connected components of a digraph $D$. Then,

$$ (i) \quad \overrightarrow{MD}^*(D) = \sum_{i=1}^{p} \overrightarrow{MD}^*(C_i). $$

$$ (ii) \quad \overrightarrow{MD}(D) = \left( \sum_{i=1}^{p} \overrightarrow{MD}^*(C_i) \right) - \max_{i \in \{1, \dots, p\}} \left\{ \overrightarrow{MD}^*(C_i) - \overrightarrow{MD}(C_i) \right\}. $$

*Proof.* One clearly sees that $R$ is a strong resolving set of $D$ if, and only if, for all $i \in \{1, \dots, p\}$, $R \cap V(C_i)$ is a strong resolving set of $C_i$. This gives (i).

Similarly, $R$ is a resolving set of $D$ if, and only if, there exists $j \in \{1, \dots, p\}$ such that $R \cap V(C_j)$ is a resolving set of $C_j$, and $R \cap V(C_i)$ is a strong resolving set of $C_i$ for all $i \in \{1, \dots, p\} \setminus \{j\}$. This implies (ii). □
Let A and B be two digraphs. We denote by $A \to B$ the digraph obtained from the disjoint union of A and B by adding all arcs from A to B. The following proposition follows directly from the definitions.

**Proposition 2.6.** Let A and B be two digraphs and $D = A \to B$.

(a) $\text{dist}_D(a, b) = 1$ and $\text{dist}_D(b, a) = +\infty$ for all $a \in V(A)$, $b \in V(B)$;

(b) $\text{dist}_D(a_1, a_2) = \text{dist}_A(a_1, a_2)$ for all $a_1, a_2 \in V(A)$;

(c) $\text{dist}_D(b_1, b_2) = \text{dist}_B(b_1, b_2)$ for all $b_1, b_2 \in V(B)$.

**Lemma 2.7.** Let A and B be two digraphs, and let $R_A$ be a resolving set of A and $R_B$ be a strong resolving set of B. Then $R_A \cup R_B$ is a resolving set of $A \to B$. Moreover, if $R_A$ is a strong resolving set of A, then $R_A \cup R_B$ is a strong resolving set of $A \to B$.

*Proof.* Set $D = A \to B$, and let $x$ and $y$ be two vertices of $V(D)$.

* If $x, y \in V(A)$, there is a vertex $w$ of $R_A$ such that $\text{dist}_A(w, x) \neq \text{dist}_A(w, y)$. Thus by Proposition 2.6 (b), $\text{dist}_D(w, x) \neq \text{dist}_D(w, y)$.

* If $x, y \in V(B)$, there is a vertex $w$ of $R_B$ such that $\text{dist}_B(w, x) \neq \text{dist}_B(w, y)$. Thus by Proposition 2.6 (c), $\text{dist}_D(w, x) \neq \text{dist}_D(w, y)$.

* If one of $x$ and $y$ is in $V(A)$ and the other is in $V(B)$, say, w.l.o.g., $x \in V(A)$ and $y \in V(B)$, then there is a vertex $w \in R_B$ such that $\text{dist}_D(w, y) \neq +\infty$ because $R_B$ is a strong resolving set. By Proposition 2.6 (a), we have $\text{dist}_D(w, x) = +\infty \neq \text{dist}_D(w, y)$.

In all cases, $x$ and $y$ are distinguished by a vertex of $R_A \cup R_B$, so $R_A \cup R_B$ is a resolving set of $D$. Also, if $R_A$ does not have an infinite vertex, then so does $R_A \cup R_B$, which means the latter is a strong resolving set too. □

**Lemma 2.8.** Let A and B be two digraphs, and R be a resolving set of $D = A \to B$. Then $R \cap V(A)$ (resp. $R \cap V(B)$) is a resolving set of A (resp. B). Moreover if R is a strong resolving set of D, then $R \cap V(A)$ is a strong resolving set of A.

*Proof.* Let $a_1, a_2$ be two vertices of A. They are distinguished by a vertex $w \in R$. Moreover, by Proposition 2.6 (a), $w \notin V(B)$, so $w \in R \cap V(A)$. Now, by Proposition 2.6 (b), $w$ distinguishes $a_1$ and $a_2$ in A. Hence $R \cap V(A)$ is a resolving set of A.

Similarly, using Proposition 2.6 (a) and (c), one proves that $R \cap V(B)$ is a resolving set of B.

Assume that R is a strong resolving set of D. For every vertex $a \in V(A)$, there is a vertex $w$ in R such that $\text{dist}_D(w, a) < +\infty$. By Proposition 2.6 (a), $w \in V(A)$. Moreover, by Proposition 2.6 (b), $\text{dist}_A(w, a) = \text{dist}_D(w, a) < +\infty$. Hence $R \cap V(A)$ is a strong resolving set of R. □

The fact that $\overrightarrow{MD}^*(B) = \overrightarrow{MD}(B)$ when B is a non-trivial strongly connected digraph, Lemmas 2.7 and 2.8, and Proposition 2.2, immediately imply the following lemma, that will be used in the proof of Theorem 4.5.

**Lemma 2.9.** Let A be a digraph and B be a non-trivial strongly connected digraph.

$$ \overrightarrow{MD}^*(A \to B) = \overrightarrow{MD}^*(A) + \overrightarrow{MD}^*(B); $$

$$ \overrightarrow{MD}(A \to B) = \overrightarrow{MD}(A) + \overrightarrow{MD}(B). $$

*Proof.* Let $R_A$ and $R_B$ be strong resolving sets of A and B of size $\overrightarrow{MD}^*(A)$ and $\overrightarrow{MD}^*(B)$ respectively. By Lemma 2.7, $R_A \cup R_B$ is a strong resolving set of $A \to B$, and so $\overrightarrow{MD}^*(A \to B) \leq \overrightarrow{MD}^*(A) + \overrightarrow{MD}^*(B)$. Let R be a strong resolving set of $A \to B$ of size $\overrightarrow{MD}^*(A \to B)$. By Lemma 2.8, $\overrightarrow{MD}^*(A \to B) = |R| = |R \cap A| + |R \cap B| \geq \overrightarrow{MD}^*(A) + \overrightarrow{MD}^*(B)$. Since B is non-trivial and strongly connected, $\overrightarrow{MD}^*(B) = \overrightarrow{MD}^*(B)$ and the first equality holds.

Let R be a resolving set of $A \to B$ of size $\overrightarrow{MD}(A \to B)$. By Lemma 2.8, $\overrightarrow{MD}(A \to B) = |R| = |R \cap A| + |R \cap B| \geq \overrightarrow{MD}(A) + \overrightarrow{MD}(B)$. Moreover, Lemma 2.7 implies that $\overrightarrow{MD}^*(B) + \overrightarrow{MD}(A) \leq \overrightarrow{MD}(A \to B)$. Since B is non-trivial and strongly connected, $\overrightarrow{MD}(B) = \overrightarrow{MD}^*(B)$ and the second equality holds. □
Finally, let us present a necessary condition for a subset of vertices to be a strong resolving set of a digraph $D$. We need to introduce some definitions.

Recall that $S(D)$ denotes the set of sources of $D$. Let $\mathcal{T}(D)$ be the partition of $V(D)$ such that, for every source $s \in S(D)$, there is one part $\{s\}$, and any two vertices $u$ and $v$ (not in $S(D)$) are in the same part if, and only if, $N^-(u) = N^-(v) \neq \emptyset$. Let $\mathcal{T}_1(D)$ be the family of singletons of $\mathcal{T}(D)$ (in particular, every $\{s\}$ for $s \in S(D)$ is an element of $\mathcal{T}_1(D)$), and $\mathcal{T}_2(D)$ be the family of non-singletons of $\mathcal{T}(D)$. A set $U \subseteq V(D)$ is *adequate in D* if $S(D) \subseteq U$ and $|U \cap T| \ge |T| - 1$ for all $T \in \mathcal{T}_2(D)$.

**Lemma 2.10.** Let $D$ be a digraph. If $R$ is a strong resolving set of $D$, then $R$ is adequate in $D$.

*Proof.* Let $R$ be a strong resolving set of $D$. By Proposition 2.4, we have $S(D) \subseteq R$.

Consider now a set $T \in \mathcal{T}_2(D)$. Assume for a contradiction that two distinct vertices of $T$, say $u$ and $v$, do not belong to $R$. Let $N = N^-(u) = N^-(v)$. Let $x$ be a vertex of $R$ that distinguishes $u$ and $v$. W.l.o.g., $\text{dist}(x, u) < +\infty$. Let $P$ be a shortest path from $x$ to $u$. Let us denote by $y$ the penultimate vertex of $P$. Necessarily, $y \in N$, and $P - u$ is a shortest path from $x$ to $N$. Thus $\text{dist}(x, v) = \text{dist}(x, y) + 1 = \text{dist}(x, u)$. This contradicts the fact that $x$ distinguishes $u$ and $v$. Therefore $|R \cap T| \ge |T| - 1$. Hence $R$ is adequate. $\square$

Note that in a digraph $D$ with no in-twins (i.e. two vertices with the same in-neighbourhood), $\mathcal{T}(D)$ is made of singletons. Hence, every set containing $S(D)$ is adequate. In particular, if $D$ is also strongly connected, then every set is adequate. Thereby, being adequate is not a sufficient condition for a set to be a strong resolving set.

## 2.2 Oriented forests

In this section, we characterise (strong) resolving sets of a given oriented forest $D$. These results imply linear-time algorithms to compute $\overrightarrow{\mathcal{M}\mathcal{D}}^*(D)$ and $\overrightarrow{\mathcal{M}\mathcal{D}}(D)$ when $D$ is an oriented forest.

We first prove that the necessary condition for being a resolving set given by Lemma 2.10, namely being adequate, is also sufficient when the digraph is an oriented forest.

**Theorem 2.11.** Let $D$ be an oriented forest. A set of vertices $R$ is a strong resolving set of $D$ if, and only if, $R$ is adequate in $D$.

*Proof.* By Lemma 2.10, every strong resolving set is adequate. We shall prove the converse.

Assume that $R$ is an adequate set in $D$.

Note that since $D$ has no cycles in its underlying graph, if two vertices have the same in-neighbourhood, then this in-neighbourhood must be composed of at most one vertex.

Let $u, v$ be distinct vertices. Let $S_u$ (resp. $S_v$) be the set of sources from which $u$ (resp. $v$) can be reached. If $S_u \neq S_v$, then there is a source $s$ such that $\text{dist}(s, u) < +\infty = \text{dist}(s, v)$ or $\text{dist}(s, v) < +\infty = \text{dist}(s, u)$. Hence, $s$ distinguishes $u$ and $v$. Since $R$ is adequate, $s \in R$, so $R$ distinguishes $u$ and $v$.

Assume now that $S_u = S_v$. Let $r$ be a vertex in $S_u$, and let $P_u$ (resp. $P_v$) be the directed path from $r$ to $u$ (resp. $v$). Since $D$ is an oriented forest, $\text{dist}(r, u)$ (resp. $\text{dist}(r, v)$) is the length of $P_u$ (resp. $P_v$). If $P_u$ and $P_v$ have different lengths, then $r$ (which is in $R$) distinguishes $u$ and $v$.

Assume now that $P_u$ and $P_v$ have the same length. Since $D$ is an oriented forest, $P_u \cap P_v$ is a directed path with source vertex $r$. Let $w$ be the terminal vertex of $P_u \cap P_v$. Let $x$ be the out-neighbour of $w$ in $P_u$ and $y$ be the out-neighbour of $w$ in $P_v$. Since $S_u = S_v$, we have $N^-(x) = N^-(y) = \{w\}$. Indeed, if $x$ (resp. $y$) had an in-neighbour $z$ different from $w$, then any source from which $z$ is reachable would be in $S_u \setminus S_v$ (resp. $S_v \setminus S_u$). Hence $x$ and $y$ are in a same set $T$ of $\mathcal{T}_2(D)$. Now, because $R$ is adequate, $|R \cap T| \ge |T| - 1$, so $R$ contains a vertex $p$ in $\{x, y\}$. Exactly one vertex of $\{u, v\}$ is reachable from $p$, so it distinguishes $u$ and $v$.

Hence, $R$ distinguishes any pair of distinct vertices, that is $R$ is a resolving set, and because $S(D) \subseteq R$, every vertex is reachable from $R$, so $R$ is a strong resolving set. $\square$

**Corollary 2.12.** If $D$ is an oriented forest, then

$$ \overrightarrow{\mathcal{M}\mathcal{D}}^*(D) = |S(D)| + \sum_{T \in \mathcal{T}_2(D)} (|T| - 1) = |S(D)| + |V(D)| - |\mathcal{T}(D)|. $$
*Proof.* By Theorem 2.11, $\overrightarrow{MD}^*(D)$ is the minimum cardinality of an adequate set. By definition of adequate sets, this is $|S(D)| + \sum_{T \in \mathcal{T}_2(D)} (|T| - 1)$. Since $|T| - 1 = 0$ for every $T \in \mathcal{T}_1(D)$, we get

$$ 
\begin{aligned}
\overrightarrow{MD}^*(D) &= |S(D)| + \sum_{T \in \mathcal{T}_2(D)} (|T| - 1) + \sum_{T \in \mathcal{T}_1(D)} (|T| - 1) \\
&= |S(D)| + \sum_{T \in \mathcal{T}(D)} (|T| - 1) \\
&= |S(D)| + |V(D)| - |\mathcal{T}(D)|.
\end{aligned}
$$

□

**Corollary 2.13.** A minimum strong resolving set of a given oriented forest can be found in linear time.

*Proof.* Let $D$ be an oriented forest. To find a minimum strong resolving set $R$ of $D$, one just needs to compute $\mathcal{T}(D)$, which can be done in linear time. Then we put all sources in $R$, and for each $T \in \mathcal{T}_2(D)$ we put all but one vertex of $T$ in $R$. This results in an adequate set (and so in a strong resolving set) of minimum size. □

After studying strong resolving sets of a given oriented forest, let us now focus on resolving sets in general (i.e. not necessarily strong). Corollaries 2.3 and 2.12 directly imply the following.

**Corollary 2.14.** If $D$ is an oriented forest, then

$$ |S(D)| + |V(D)| - |\mathcal{T}(D)| - 1 \le \overrightarrow{MD}(D) \le |S(D)| + |V(D)| - |\mathcal{T}(D)| = \overrightarrow{MD}^*(D). $$

A source $s$ in an oriented forest is *removable* if every out-neighbour $v$ of $s$ has at least two in-neighbours, and, in case $v$ has exactly two in-neighbours, say $N^-(v) = \{s, w\}$, then $w$ has no out-neighbour of in-degree 1.

**Corollary 2.15.** Let $D$ be an oriented forest. Then, $\overrightarrow{MD}(D) = \overrightarrow{MD}^*(D) - 1$ if, and only if, $D$ has a removable source $s$, in which case any strong resolving set of $D - s$ is a weak resolving set of $D$.

*Proof.* If $\overrightarrow{MD}(D) = \overrightarrow{MD}^*(D) - 1$, then there is a resolving set $R$ of $D$ of size $\overrightarrow{MD}^*(D) - 1$. Necessarily, $R$ is a weak resolving set and then it has an infinite vertex $s$ which, by Proposition 2.2, must be a source. It is then clear that $R$ is a strong resolving set of $D - s$ of size $\overrightarrow{MD}^*(D) - 1$. But, if $R'$ is a strong resolving set of $D - s$, then $R' \cup \{s\}$ is a strong resolving set of $D$. Thus $\overrightarrow{MD}^*(D - s) \ge \overrightarrow{MD}^*(D) - 1$. Hence $R$ is a minimum strong resolving set of $D - s$ and $\overrightarrow{MD}^*(D - s) = \overrightarrow{MD}^*(D) - 1$. Hence, by Corollary 2.12,

$$ |S(D - s)| + |V(D - s)| - |\mathcal{T}(D - s)| = |S(D)| + |V(D)| - |\mathcal{T}(D)| - 1. $$

Since $|V(D - s)| = |V(D)| - 1$, we get

$$ |S(D - s)| - |\mathcal{T}(D - s)| = |S(D)| - |\mathcal{T}(D)|. $$

Let $U$ be the set of vertices $v$ such that $N_D^-(v) = \{s\}$. We have $S(D - s) = (S(D) \setminus \{s\}) \cup U$. Thus $|S(D - s)| = |S(D)| - 1 + |U|$, and hence

$$ |\mathcal{T}(D - s)| = |\mathcal{T}(D)| + |U| - 1. \qquad (1) $$

Observe that every set of $\mathcal{T}(D)$ except $U$ and $\{s\}$ is a subset of a set of $\mathcal{T}(D - s)$. Moreover $\{s\}$ is not in $\mathcal{T}(D - s)$ and the vertices of $U$ are in at most $|U|$ sets of $\mathcal{T}(D - s) \setminus \mathcal{T}(D)$. If $U$ is not empty, then $|\mathcal{T}(D - s)| \le |\mathcal{T}(D)| + |U| - 2$, a contradiction to Equation (1). Therefore $U$ is empty and $|\mathcal{T}(D - s)| = |\mathcal{T}(D)| - 1$. Consequently, the parts of $\mathcal{T}(D - s)$ and $\mathcal{T}(D)$ are the same, except for $\{s\}$ which is in $\mathcal{T}(D)$ and not in $\mathcal{T}(D - s)$.

Now consider an out-neighbour $v$ of $s$. It has in-degree at least 2 in $D$ (since $U$ is empty). So $\{v\}$ is a part of $\mathcal{T}(D)$ and so also a part in $\mathcal{T}(D - s)$. Thus, if $N_D^-(v) = \{s, w\}$, then $w$ has
<figure><img src="image_2.png" /><figcaption>Figure 1: Gadgets used in the proof of Theorem 2.17.</figcaption></figure>

no out-neighbour $z$ of in-degree 1, for otherwise $z$ and $v$ would be in the same part of $\mathcal{T}(D-s)$.
Consequently, $s$ is a removable source.

Reciprocally, assume that $s$ is a removable source of $D$. Let $R$ be a minimum strong resolving set of $D$. By Theorem 2.11, $R$ is adequate in $D$. Now since $s$ is removable, one easily checks that $\mathcal{T}(D-s) = \mathcal{T}(D) \setminus \{\{s\}\}$. Thus $R \setminus \{s\}$ is adequate in $D-s$, and so, by Theorem 2.11, $R \setminus \{s\}$ is a strong resolving set of $D-s$. Hence, $R \setminus \{s\}$ is a resolving set of $D$, and $\overrightarrow{\mathrm{MD}}(D) = \overrightarrow{\mathrm{MD}}^*(D)-1$. $\square$

Because we can check in linear time whether $D$ has a removable source, we get:

**Corollary 2.16.** A minimum resolving set of a given oriented forest $D$ can be found in linear time.

## 2.3 NP-hardness of DMD in bipartite acyclic digraphs

The next natural case to investigate after that of oriented trees would be that of acyclic digraphs or oriented bipartite graphs. In the next result, we prove that DMD remains NP-complete for such instances. The result actually also holds for the restriction of the problem to strong resolving sets.

**Theorem 2.17.** *Given a digraph $D$ and a positive integer $k$, deciding either $\overrightarrow{\mathrm{MD}}^*(D) \le k$ or $\overrightarrow{\mathrm{MD}}(D) \le k$ is NP-complete, even if $D$ is a bipartite acyclic digraph with maximum degree 10 and the diameter of the underlying undirected graph is 4.*

*Proof.* First note that given a subset $S \subseteq V(D)$, one may check in polynomial time whether $|S| \le k$ and $S$ is a (strong) resolving set of $D$. Thus, DMD belongs to NP. We prove its NP-hardness by reducing the 3-SAT problem in which every variable appears in at most four clauses (which is indeed NP-hard, see [20]). Let $\{x_1, \dots, x_n\}$ be the set of variables and $\{C_1, \dots, C_m\}$ be the set of clauses of a given instance $\mathcal{F}$ of 3-SAT. We build a bipartite acyclic digraph $D(\mathcal{F})$ with maximum degree 10 and the diameter of the underlying undirected graph is 4 such that $\mathcal{F}$ is satisfiable if, and only if, $\overrightarrow{\mathrm{MD}}(D(\mathcal{F})) \le 2n+m$ (we discuss the result for the strong metric dimension at the end of the proof).

Variable gadgets and clause gadgets can be seen in Figure 1. For each variable $x_i$ we add in $D(\mathcal{F})$ five vertices $u_i, v_i, w_i, \ell_i$ and the arcs $u_i v_i, v_i w_i, w_i \ell_i$ and $w_i \overline{\ell_i}$. Similarly, for each clause $C_j$ we add in $D(\mathcal{F})$ four vertices $a_j, b_j, c_j$ and $c_j^*$ and the arcs $a_j b_j, b_j c_j$ and $b_j c_j^*$. For each $i \in \{1, \dots, n\}$ and $j \in \{1, \dots, m\}$, if one of the literals of $x_i$ appears in $C_j$, then we add in $D(\mathcal{F})$ the arcs $v_i c_j$ and $v_i c_j^*$. Moreover, if $x_i$ appears positively in $C_j$, then we add the arc $\ell_i c_j$; and if $x_i$ appears negatively in $C_j$, then we add the arc $\overline{\ell_i c_j}$. Note that the following sets form a bipartition of $V(D(\mathcal{F}))$: $\{u_i, w_i \mid i \in \{1, \dots, n\}\} \cup \{a_i, c_i, c_i^* \mid i \in \{1, \dots, m\}\}$, together with $\{v_i, \ell_i, \overline{\ell_i} \mid i \in \{1, \dots, n\}\} \cup \\{b_i \mid i \in \{1, \dots, m\}\}$.

Clearly, the reduction is achieved in polynomial time. Note also that, in $D(\mathcal{F})$, all arcs go from the variable gadgets to the clause gadgets and therefore the digraph is acyclic and the diameter of its underlying undirected graph is 4. Finally, observe that we have maximum degree at most 10, since each variable occurs at most three times. It remains to prove equivalence.

The following result on the resolving sets of $D(\mathcal{F})$ is the key to our proof.

**Claim 2.18.** For every $i \in \{1, \dots, n\}$ and every $j \in \{1, \dots, m\}$, every resolving set of $D(\mathcal{F})$ must include at least one vertex in each of the subsets $\{u_i, v_i\}$, $\{a_j, b_j\}$ and $\{\ell_i, \overline{\ell_i}\}$.
Proof of the claim. Note that if, for some $i \in \{1, \dots, n\}$, $u_i$ and $v_i$ do not belong to any resolving set, then they are indistinguishable as there is no directed path from a vertex in $V(D(\mathcal{F})) \setminus \{u_i, v_i\}$ to $u_i$ nor to $v_i$. The argument is similar concerning $\{a_i, b_j\}$. Finally, note that $\ell_i$ and $\bar{\ell}_i$ have the same in-neighbourhood $\{w_i\}$ and thus one of them must belong to any resolving set as well. ◇

By Claim 2.18, we get that every resolving set of $D(\mathcal{F})$ has size at least $2n + m$. We prove below that equality holds if, and only if, $\mathcal{F}$ is satisfiable.

* Suppose that $\mathcal{F}$ is satisfiable and consider a truth assignment that satisfies $\mathcal{F}$. Let $R \subseteq V(D(\mathcal{F}))$ be such that

$$R = \{u_i, a_j \mid i \in \{1, \dots, n\}, j \in \{1, \dots, m\}\} \cup \{\ell_i \mid x_i \text{ is true}\} \cup \{\bar{\ell}_i \mid x_i \text{ is false}\}.$$

We claim that $R$ is a resolving set of $D(\mathcal{F})$. For every $i \in \{1, \dots, n\}$, note that the vertices $u_i$ and $v_i$ are distinguished from themselves and from the others by $u_i$. The same holds for $a_j$ and $b_j$, for every $j \in \{1, \dots, m\}$. Moreover, due to $a_j$, the only vertex that possibly may not be distinguished from $c_j$ is $c_j^*$, as they are the only vertices at distance 2 from $a_j$. Since $\mathcal{F}$ is satisfied, a literal $x_i$ ($\bar{x}_i$) belonging to $C_j$ is true (resp., false) and, then, the vertex $\ell_i$ (resp. $\bar{\ell}_i$) belongs to $R$ and distinguishes $c_j$ and $c_j^*$. Finally, note that the vertices $v_i$, $w_i$ and the vertex in $\{\ell_i, \bar{\ell}_i\} \setminus R$ are distinguished by $u_i$ and the vertex in $\{\ell_i, \bar{\ell}_i\} \cap R$, for every $i \in \{1, \dots, n\}$.

* Suppose now that $R$ is a resolving set of $D(\mathcal{F})$ such that $|R| \le 2n + m$. By Claim 2.18, for every $i, j$ exactly one vertex in each of the subsets $\{u_i, v_i\}$, $\{a_j, b_j\}$ and $\{\ell_i, \bar{\ell}_i\}$ must belong to $R$ (and because $|R| \le 2n + m$, no other vertices belong to $R$). By the previous arguments, note that, due to the vertex in $\{a_j, b_j\} \cap R$, the only vertex that, possibly, cannot be distinguished from $c_j$ is $c_j^*$. Due to the arcs from $v_i$ to $c_j$ and $c_j^*$ for every variable $x_i$ having a literal in $C_j$, the vertex in $\{u_i, v_i\} \cap R$ does not distinguish $c_j$ from $c_j^*$. Since $R$ is a resolving set of $D(\mathcal{F})$, then $c_j$ and $c_j^*$ are resolved by some vertex in $\{\ell_i, \bar{\ell}_i\} \cap R$, for some variable $x_i$ having a literal in $C_j$. Thus, note that we can define a truth assignment to $\mathcal{F}$ that satisfies it by considering $x_i$ to be true if, and only if, $\ell_i \in R$.

To see that the reduction above also holds for the strong metric dimension, just note that the $u_i$'s and the $a_j$'s are sources, and that they must thus belong to every strong resolving set of $D(\mathcal{F})$. This yields a straight refinement of Claim 2.18. From here, it is easy to see that the equivalence between $F$ and $D(\mathcal{F})$ holds by the very same arguments as above. □

# 3 Best orientations of undirected graphs

In this section, we consider the problem that, given an undirected graph $G$, aims at finding an orientation $D$ of it that minimises $\overrightarrow{MD}(D)$ or $\overrightarrow{MD}^*(D)$. Precisely, let

$$\text{BOMD}(G) = \min \{ \overrightarrow{MD}(D) : D \text{ is an orientation of } G \},$$

and

$$\text{BOMD}^*(G) = \min \{ \overrightarrow{MD}^*(D) : D \text{ is an orientation of } G \}.$$

We start by basic remarks leading to the fact that computing both parameters is NP-hard. Then, we establish some relationship with path covers of graphs. Lastly, we focus on trees and forests.

## 3.1 Generalities on BOMD and BOMD*

First note that, by Corollary 2.3, for any graph $G$:

$$\text{BOMD}(G) \le \text{BOMD}^*(G) \le \text{BOMD}(G) + 1. \qquad (2)$$

**Lemma 3.1.** Let $G$ be a graph and $x$ be a vertex of $G$. Then $\text{BOMD}(G) \le \text{BOMD}^*(G - x)$.
Proof. Let $D$ be an orientation of $G-x$ such that $\overrightarrow{MD}^*(D) = \text{BOMD}^*(G-x)$. Any strong resolving set of $D$ is a resolving set of the orientation $x \to D$ of $G$ (obtained from $D$ by making $x$ a source). Hence $\text{BOMD}(G) \le \text{BOMD}^*(G-x)$. $\square$

**Corollary 3.2.** Let $G$ be a graph on at least two vertices. Then,

$$ \text{BOMD}(G) = \min \left\{ \text{BOMD}^*(G), \min\{\text{BOMD}^*(G-x) \mid x \in V(G)\} \right\}. $$

Proof. By definition, we have $\text{BOMD}(G) \le \text{BOMD}^*(G)$ and Lemma 3.1 implies $\text{BOMD}(G) \le \min\{\text{BOMD}^*(G-x) \mid x \in V(G)\}$.

Now consider an orientation $D$ of $G$ having a resolving set $R$ of size $\text{BOMD}(G)$. If $R$ is a strong resolving set, then $\text{BOMD}(G) = \text{BOMD}^*(G)$. If not, then, by Proposition 2.2, $R$ has a unique infinite vertex $y$ which is a source. For any $u, v \in V(G) \setminus \{y\}$, there is no $(u, v)$-path containing $y$. Hence $R$ is a strong resolving set of $G-y$, and so $\text{BOMD}(G) \ge \text{BOMD}^*(G-y) \ge \min\{\text{BOMD}^*(G-x) \mid x \in V(G)\}$. $\square$

Proposition 2.5 directly implies the following.

**Lemma 3.3.** Let $H_1, \dots, H_p$ be the connected components of a graph $G$. Then,

$$ (i) \quad \text{BOMD}^*(G) = \sum_{i=1}^{p} \text{BOMD}^*(H_i). $$

$$ (ii) \quad \text{BOMD}(G) = \sum_{i=1}^{p} \text{BOMD}^*(H_i) - \max\{\text{BOMD}^*(H_i) - \text{BOMD}(H_i) \mid i \in \{1, \dots, p\}\}. $$

Recall that a graph is *traceable* if it has a hamiltonian path.

**Proposition 3.4.** Let $G$ be a graph. Then, $\text{BOMD}^*(G) = 1$ if, and only if, $G$ is traceable.

*Proof.* Let $G$ be a graph on $n$ vertices.

Assume first that $G$ has a hamiltonian path $P = (v_0, \dots, v_{n-1})$. Let $D$ be the orientation of $G$ such that $v_iv_{i+1} \in A(D)$ for all $i \in \{0, \dots, n-2\}$ and $v_jv_i \in A(D)$ for all edges $v_iv_j \in E(G)$ such that $j \ge i+2$. Clearly, $\text{dist}_D(v_0, v_i) = i$ for every $i \in \{0, \dots, n-2\}$, so $\{v_0\}$ is a strong resolving set of $D$. Thus $\text{BOMD}^*(G) = 1$.

Reciprocally, assume $\text{BOMD}^*(G) = 1$. Let $D$ be an orientation of $G$ having a strong resolving set of size 1, say $\{v_0\}$. All vertices are distinguished by their distance from $v_0$. Since only the $n$ values of $\{0, \dots, n-1\}$ are possible for the distances, we can label the vertices $v_0, \dots, v_{n-1}$ such that $\text{dist}_D(v_0, v_i) = i$ for all $0 \le i \in n-2$. Then necessarily $(v_0, \dots, v_{n-1})$ is a directed hamiltonian path in $D$ and so also a hamiltonian path in $G$. $\square$

A graph $G$ is *hypotraceable* if there is a vertex $x$ such that $G-x$ is traceable (see e.g. [4]).
Corollary 3.2 and Proposition 3.4 immediately imply the following.

**Corollary 3.5.** Let $G$ be a graph. $\text{BOMD}(G) = 1$ if, and only if, $G$ is hypotraceable.

**Corollary 3.6.** Let $k$ be a positive integer.

(i) Deciding whether a given graph $G$ satisfies $\text{BOMD}^*(G) \le k$ is NP-complete.

(ii) Deciding whether a given graph $G$ satisfies $\text{BOMD}(G) \le k$ is NP-complete.

*Proof.* Both problems are clearly in NP.

Let $G$ be an instance of the Hamiltonian Path problem which is a well-known NP-complete problem. For any non-negative integer $k$, let $G_k$ be the disjoint union of $G$ with $k-1$ copies of $K_1$ (the graph with a single vertex). Since $\text{BOMD}(K_1) = 0$ and $\text{BOMD}^*(K_1) = 1$, Lemma 3.3 implies that $\text{BOMD}^*(G_k) = k-1 + \text{BOMD}^*(G)$ and $\text{BOMD}(G_{k+1}) = k-1 + \text{BOMD}^*(G)$. Thus, by Proposition 3.4, $\text{BOMD}^*(G_k) = k$ (resp., $\text{BOMD}(G_{k+1}) = k$) if and only if $G$ is traceable. Hence, both problems are NP-complete. $\square$
## 3.2 Relation with path covers of graphs

A *path cover* of a graph $G$ is a set of vertex-disjoint paths whose union contains all the vertices of $G$. The *path cover number* of $G$, denoted by $\text{pc}(G)$, is the minimum number of paths in a path cover of $G$. A *minimum path cover* of $G$ is a path cover of size $\text{pc}(G)$. The *Path Cover* problem consists of finding a minimum path cover of a given graph. It is evident that the *Path Cover* problem for general graphs is NP-complete since finding a path cover consisting of a single path, corresponds directly to the *Hamiltonian Path* problem. Polynomial-time algorithms to solve the *Path Cover* problem are known for a few special classes of graphs (see [14] for a list).

**Theorem 3.7.** BOMD($G$) $\le$ BOMD$^*(G)$ $\le$ pc($G$) for all graphs $G$.

*Proof.* Let $G$ be a graph, and let $\{P_1, \dots, P_k\}$ be a path cover of $G$. Set $P_i = (v_i^1, \dots, v_i^{p_i})$. Let us orient the edges of $G$ as follows. Let $xy$ be an edge.

* If $x \in V(P_i)$ and $y \in V(P_j)$ with $i < j$, then orient the edge from $y$ to $x$.

* If $x = v_i^j$ and $y = v_i^l$ with $j < l$, then orient the edge from $x$ to $y$ if $l = j + 1$, and from $y$ to $x$ otherwise.

Let us prove that $R = \{v_i^1 \mid i \in \{1, \dots, k\}\}$ is a strong resolving set of the resulting orientation $D$ of $G$.

Let $x$ and $y$ be two vertices of $G$. If $x \in V(P_i)$ and $y \in V(P_j)$ with $i < j$, then $\text{dist}_D(v_i^1, x) < +\infty$ and $\text{dist}_D(v_i^1, y) = +\infty$, and if $x = v_i^j$ and $y = v_i^l$ with $j \ne l$, then $\text{dist}_D(v_i^1, x) = j - 1 \ne l - 1 = \text{dist}_D(v_i^1, y)$. In both cases, $R$ distinguishes $x$ and $y$. So $R$ is a resolving set. Moreover it is strong because every vertex in $V(P_i)$ is reachable from $v_i^1$. $\square$

As we present next, the bound of Theorem 3.7 can be loose even for trees. The *complete binary tree* $B_n$ of height $n$ can be defined inductively as follows. $B_0$ is the tree with one vertex which is its *root*. For every positive integer $n \ge 1$, the complete binary tree $B_n$ of height $n$ is obtained from two copies $L$ and $R$ of $B_{n-1}$ by adding a vertex and joining it to the two roots of $L$ and $R$. The newly-added vertex is the *root* of $B_n$. We denote by $L_i$ the set of vertices of $B_n$ at distance exactly $i$ from the root. Note that $|L_i| = 2^i$.

**Proposition 3.8.** Let $p$ be a non-negative integer. Then,

$$ (i) \text{ BOMD}^*(B_{2p+1}) \le 2^{2p} \text{ and } \text{pc}(B_{2p+1}) = \frac{2^{2p+2}-1}{3}. $$

$$ (ii) \text{ BOMD}^*(B_{2p}) \le 2^{2p-1} \text{ and } \text{pc}(B_{2p}) = \frac{2^{2p+1}+5/2}{3}. $$

*Proof.* For each vertex $x$ of $L_{n-1}$ in $B_n$, let $\ell_x$ and $r_x$ be its two adjacent leaves.

Let $D$ be the orientation of $B_n$ in which all the edges are oriented from the leaves towards the root, except for the edges $x\ell_x$, for each $x \in L_{n-1}$, which are oriented from $x$ to $\ell_x$. Set $R = \{r_x \mid x \in L_{n-1}\}$. One easily checks that $R$ is a strong resolving set of $D$. Hence BOMD$^*(B_n) \le 2^{n-1}$.

Assume that $\mathcal{P} = \{P_1, \dots, P_q\}$ is a minimum path cover of $B_n$ (that is, $q = \text{pc}(B_n)$). For each $x \in L_{n-1}$, let $P_x = (\ell_x, x, r_x)$. We may assume that $\mathcal{P}$ is a path cover that maximises the number of paths taken from $\{P_x \mid x \in L_{n-1}\}$. Then $\mathcal{P}$ contains all $P_x$, for otherwise one of the paths of $\mathcal{P}$ is restricted to a unique vertex $\ell_x$ or $r_x$. W.l.o.g., we may assume that $P_q = (\ell_q)$ and $P_{q-1}$ contains $r_x$. Let $P_i$ be the path containing $x$. We have $i = q - 1$, for otherwise $P_{q-1} = (r_x)$ and the path cover obtained from $\mathcal{P}$ by replacing $P_i$, $P_{q-1}$, and $P_q$ by $P_i - x$ and $P_x$ contradicts the minimality of $\mathcal{P}$. But then the path cover obtained from $\mathcal{C}$ by replacing $P_{q-1}$ and $P_q$ by $P_{q-1} - x$ and $P_x$ is minimum and has more $P_x$ than $\mathcal{P}$, a contradiction. Therefore, $\mathcal{P}$ contains all $P_x$, and so $\mathcal{P} \setminus \{P_x \mid x \in L_{n-1}\}$ is a path cover of $T - (L_n \cup L_{n-1})$ which is isomorphic to $B_{n-2}$. Thus $\text{pc}(B_n) = 2^{n-1} + \text{pc}(B_{n-2})$.

$$ \text{As } \text{pc}(B_0) = \text{pc}(B_1) = 1, \text{ solving the recurrence yields } \text{pc}(B_{2p+1}) = \frac{2^{2p+2}-1}{3} \text{ and } \text{pc}(B_{2p}) = \frac{2^{2p+1}+5/2}{3}. \quad \square $$

In turn, we note that, in general, $\text{pc}(G)$ cannot be bounded as a function of BOMD$^*(G)$.
**Proposition 3.9.** Let $k \ge 2$ be an integer. There exists a graph $G$ such that $\text{BOMD}(G) = \text{BOMD}^*(G) = 2$ and $\text{pc}(G) \ge k$.

*Proof.* Let $G_n$ be the graph defined as follows:

$$
\begin{align*}
V(G_n) &= \{a_i \mid 0 \le i \le n\} \cup \{b_j \mid 0 \le j \le n\} \cup \{c_{i,j} \mid 1 \le i \le n, 1 \le j \le n\}; \\
E(G_n) &= \{a_{i-1}a_i \mid 1 \le i \le n\} \cup \{b_{j-1}b_j \mid 1 \le j \le n\} \cup \\
&\phantom{=} \quad \{a_{i-1}c_{i,j} \mid 1 \le i \le n, 1 \le j \le n\} \cup \{b_{j-1}c_{i,j} \mid 1 \le i \le n, 1 \le j \le n\}.
\end{align*}
$$

That is, $G_n$ is obtained from two paths $(a_0, \dots, a_n)$ and $(b_0, \dots, b_n)$, by adding, for every $0 \le i, j < n$, a new vertex $c_{i+1,j+1}$ adjacent to $a_i$ and $b_j$.

Let $D_n$ be the orientation of $G_n$ such that every $c_{i,j}$ is a sink and the paths $(a_0, \dots, a_n)$ and $(b_0, \dots, b_n)$ are directed from $a_0$ to $a_n$ and from $b_0$ to $b_n$, respectively. We have $\text{dist}_D(a_0, a_i) = i$ and $\text{dist}_D(b_0, a_i) = +\infty$ for all $0 \le i \le n$, $\text{dist}_D(a_0, b_j) = +\infty$ and $\text{dist}_D(b_0, b_j) = j$ for all $0 \le j \le n$, and $\text{dist}_D(a_0, c_{i,j}) = i$ and $\text{dist}_D(b_0, c_{i,j}) = j$ for all $1 \le i \le n$ and all $1 \le j \le n$. Consequently $\{a_0, b_0\}$ is a strong resolving set of $D_n$. Thus $\text{BOMD}^*(G_n) \le 2$.

Now observe that $C = \{c_{i,j} \mid 1 \le i \le n, 1 \le j \le n\}$ is a stable set of order $n^2$, while $W = V(G_n) \setminus C$ is a set of $2n+2$ vertices. In every path cover of $G_n$, the number of vertices of $C$ adjacent to a vertex of $W$ is at most $2 \times (2n+2) = 4n+4$. In particular, $G$ is not hypotraceable, so $\text{BOMD}(G) \ge 2$ by Corollary 3.5. Moreover there are at least $n^2 - (4n+4)$ vertices of $C$ which are isolated in the path cover. Thus, the number of paths of the path cover is at least $n^2 - (4n+4)$. Choosing $n$ large enough so that $n^2 - (4n+4) \ge k$, we get the result. $\square$

## 3.3 Best orientation of trees and forests

In this section, we give lower and upper bounds on $\text{BOMD}^*(F)$ and $\text{BOMD}(F)$ for forests $F$. In later Section 5, we present a polynomial-time algorithm that computes these values.

Let $T$ be an undirected tree. A vertex with degree 1 (resp. 2, at least 3) in $T$ is called a *leaf* (resp. *flat vertex*, *branching vertex*). A path whose internal vertices are flat and whose endvertices are either leaves or branching vertices is called a *segment*. A segment is an *outer segment* if one of its endvertices is a leaf. Otherwise it is an *inner segment*. We denote by:

* $\text{lf}(T)$ the number of leaves of $T$;

* $\text{bv}(T)$ the number of branching vertices of $T$; and

* $\text{hb}(T)$ the number of branching vertices that are endvertices of outer segments.

Note that $\text{hb}(T) \le \text{bv}(T) \le \text{lf}(T) - 2$. Observe moreover that if $T$ is not a path then $\text{hb}(T) \ge 1$. The metric dimension of an undirected tree $T$ can be expressed as a function of $\text{lf}(T)$ and $\text{hb}(T)$.

**Theorem 3.10 (Slater [19]).** Let $T$ be a tree. If $T$ is a path, then $\text{MD}(T) = 1$. Otherwise, $\text{MD}(T) = \text{lf}(T) - \text{hb}(T)$.

We start by establishing lower and upper bounds on $\text{BOMD}(T)$ for any tree $T$.

**Theorem 3.11.** $\text{MD}(T) \le \text{BOMD}^*(T) \le \text{lf}(T) - 1$ for all trees $T$.

*Proof.* We start by proving the lower bound. Consider any orientation $D$ of $T$ and any strong resolving set $R$ for $D$. Note that if $\text{dist}_D(u, v) = k$, then $\text{dist}_T(u, v) = k$ as well. Furthermore, by definition, $D$ has no infinite vertex with respect to $R$. Let $u, v \in V(D) \setminus R$. If there exists $r \in R$ such that $\text{dist}_D(r, v) < \infty$ and $\text{dist}_D(r, u) < \infty$ and $\text{dist}_D(r, v) \ne \text{dist}_D(r, u)$, then $\text{dist}_T(r, v) \ne \text{dist}_T(r, u)$ and $R$ distinguishes $u$ and $v$ in $T$. Otherwise, there must be $r \in R$ such that $\text{dist}_D(r, v) = \infty$ and $\text{dist}_D(r, u) = k < \infty$ (up to reversing the roles of $u$ and $v$). If $\text{dist}_T(r, v) \ne k$, then $r$ distinguishes $u$ and $v$ in $T$. Otherwise, let $w \in R$ such that $\text{dist}_D(w, v) < \infty$ ($w$ must exists since $D$ has no infinite vertex with respect to $R$). We show that $w$ distinguishes $v$ and $u$ in $T$. Note that the directed path from $w$ to $v$ cannot go through $r$ (since there does not exist a directed path from $r$ to $v$ in $D$). Hence, there are two cases: either the path between $w$ and $u$ in $T$ goes through $v$ (in which case, $\text{dist}_T(w, u) > \text{dist}_T(w, v)$ and $w$ distinguishes $v$ and $u$ in $T$) or there exists a vertex $w' \notin \{r, v\}$
of the path between $r$ and $v$ such that $\mathrm{dist}_T(w, u) = \mathrm{dist}_T(w, w') + \mathrm{dist}_T(w', w) + \mathrm{dist}_T(r, u)$ and $\mathrm{dist}_T(w, v) = \mathrm{dist}_T(w, w') + \mathrm{dist}_T(w', v)$. Since $\mathrm{dist}_T(r, u) = \mathrm{dist}_T(r, v) = \mathrm{dist}_T(r, w) + \mathrm{dist}_T(w', v) = k$, then $\mathrm{dist}_T(w, v) < \mathrm{dist}_T(w, u) < \infty$ and $w$ distinguishes $u$ and $v$. Consequently, $R$ is a resolving set of $T$, and, thus, $\mathrm{MD}(T) \le \mathrm{BOMD}^*(T)$.

Let us now prove the upper bound. Let $r$ be any leaf of $T$, and consider $D$ the orientation of $T$ obtained by orienting all edges towards $r$. That is, if an edge $uv$ satisfies $\mathrm{dist}_T(u, r) = \mathrm{dist}_T(v, r)-1$, then we orient $uv$ from $v$ to $u$. We now get that all leaves of $D$ but $r$ form a strong resolving set $R$. Indeed, no vertex of $D$ is infinite with respect to $R$. Now, because the out-degree of each vertex is 1, except for $r$, one can see that, for each leaf $\ell$, the set of vertices reached by $\ell$ form a directed path. Therefore, every vertex of $D$ is uniquely identified by the distances from the leaves, and it follows that $\mathrm{BOMD}^*(T) \le \mathrm{lf}(T) - 1$. $\square$

**Corollary 3.12.** $\mathrm{lf}(T) - \mathrm{hb}(T) - 1 \le \mathrm{BOMD}(T) \le \mathrm{lf}(T) - 1$, for all trees $T$.

*Proof.* The result is obvious if $T$ is a path, so let us assume that $T$ is not a path. Then, by Equation (2) and Theorems 3.10 and 3.11, we have

$$ \mathrm{lf}(T) - \mathrm{hb}(T) - 1 = \mathrm{MD}(T) - 1 \le \mathrm{BOMD}^*(T) - 1 \le \mathrm{BOMD}(T) \le \mathrm{BOMD}^*(T) \le \mathrm{lf}(T) - 1, $$

as claimed. $\square$

The upper bound in Corollary 3.12 is tight: for instance, when $T$ is a star, one easily sees that $\mathrm{BOMD}(T) = \mathrm{lf}(T) - 1$. The lower bound in Corollary 3.12 is also tight: consider the tree $T_p$ with vertex set $\{a_0, d\} \cup \bigcup_{i=1}^p \{a_i, b_i, c_i\}$ and edge set $\{a_0b_1\} \cup \bigcup_{i=1}^p \{a_ib_i, b_ic_i, b_id\}$. We have $\mathrm{lf}(T_p) = 2p + 1$ and $\mathrm{hb}(T_p) = p$. Moreover, $\{a_i \mid i \in \{1, \dots, p\}\}$ is a resolving set of the orientation $D$ of $T$ with $A(D) = \{a_0b_1\} \cup \bigcup_{i=1}^p \{a_ib_i, b_ic_i, b_id\}$. Thus $\mathrm{BOMD}(T_p) \le \mathrm{lf}(T_p) - \mathrm{hb}(T_p) - 1$.

Let $G$ be a graph. We denote by $\mathrm{cc}(G)$ its number of connected components, and by $\mathrm{pcc}(G)$ its number of connected components that are paths. In particular, if $T$ is a tree, then $\mathrm{pcc}(T) = 1$ if $T$ is a path and $\mathrm{pcc}(T) = 0$ otherwise. Hence, Theorem 3.10 can be restated as follows: $\mathrm{MD}(T) = \mathrm{lf}(T) - \mathrm{hb}(T) - \mathrm{pcc}(T)$. Therefore, Equation (2), Theorem 3.11, Corollary 3.12, and Lemma 3.3 yield the following.

**Corollary 3.13.** Let $F$ be a forest. Then,

$$ \mathrm{lf}(F) - \mathrm{hb}(F) - \max\{\mathrm{pcc}(F), 1\} \le \mathrm{BOMD}(F) \le \mathrm{lf}(F) - \mathrm{cc}(F). $$

# 4 Worst orientations of undirected graphs

In this section, we consider the problem that, given an undirected graph $G$, aims at finding an orientation $D$ of $G$ that maximises $\overrightarrow{\mathrm{MD}}(D)$ and $\overrightarrow{\mathrm{MD}}^*(D)$. Precisely, let

$$ \mathrm{WOMD}(G) = \max \{ \overrightarrow{\mathrm{MD}}(D) : D \text{ is an orientation of } G \}, $$

and

$$ \mathrm{WOMD}^*(G) = \max \{ \overrightarrow{\mathrm{MD}}^*(D) : D \text{ is an orientation of } G \}. $$

By Corollary 2.3, for any graph $G$,

$$ \mathrm{WOMD}(G) \le \mathrm{WOMD}^*(G) \le \mathrm{WOMD}(G) + 1. \qquad (3) $$

Recall that the stability number of a graph $G$, denoted by $\alpha(G)$, is the maximum size of a stable set (i.e. a set of pairwise non-adjacent vertices) in $G$. For any orientation $D$ of $G$, the stability number of $D$ is the stability number of $G$, that is $\alpha(D) = \alpha(G)$.

**Proposition 4.1.** Let $G$ be a graph and $H$ be an induced subgraph of $G$. Then $\mathrm{WOMD}^*(G) \ge \mathrm{WOMD}^*(H)$ and $\mathrm{WOMD}(G) \ge \mathrm{WOMD}(H)$.
Proof. Let $D'$ be an orientation of $H$ such that $\overrightarrow{MD}(D') = \text{WOMD}(H)$. Let $D$ be an orientation of $G$ that agrees with $D'$ on $H$, and such that all arcs between $V(H)$ and $V(G) \setminus V(H)$ are oriented away from $V(H)$. In $D$, two vertices of $V(H)$ cannot be distinguished by a vertex in $V(G) \setminus V(H)$ because they are at infinite distance from it. Therefore, if $R$ is a resolving set of $D$, then $R \cap V(H)$ is a resolving set of $D'$. Hence $\text{WOMD}(G) \ge \overrightarrow{MD}(D) \ge \overrightarrow{MD}(D') = \text{WOMD}(H)$.

One can similarly show that $\text{WOMD}^*(G) \ge \text{WOMD}^*(H)$. $\square$

Consider $E_n$, the edgeless graph of order $n$. We have $\text{WOMD}^*(E_n) = n$ and $\text{WOMD}(E_n) = n - 1$. Hence, by Proposition 4.1, we get the following.

**Corollary 4.2.** Let $G$ be a graph. Then $\text{WOMD}^*(G) \ge \alpha(G)$ and $\text{WOMD}(G) \ge \alpha(G) - 1$.

Proposition 2.5 yields the following.

**Lemma 4.3.** Let $H_1, \dots, H_p$ be the connected components of a graph $G$.

$$ (i) \text{WOMD}^*(G) = \sum_{i=1}^{p} \text{WOMD}^*(H_i). $$

$$ (ii) \text{WOMD}(G) = \sum_{i=1}^{p} \text{WOMD}^*(H_i) - \max\{\text{WOMD}^*(H_i) - \text{WOMD}(H_i) \mid i \in \{1, \dots, p\}\}. $$

In what follows, we investigate $\text{WOMD}$ and $\text{WOMD}^*$ for complete graphs and forests.

## 4.1 Worst orientations of complete graphs

In complete graphs, the metric dimension coincide with the location number, and similarly the strong metric dimension coincide with the location-domination number. In Section 6 of [11], Foucaud, Heydarshahi, and Parreau studied the location number and location-domination number of tournaments. Independently to our work and the one of Lozano [15], they gave alternative proofs of Theorems 4.4 and 4.5. Cohen and Havet [7] studied the best orientation for locating-dominating sets and Bousquet et al. [5] considered the best and worst orientation for locating-dominating sets.

Lozano [15] showed that every tournament $T$ has a set $S$ of size at most $\lfloor|V(T)|/2\rfloor$ such that, for any two distinct vertices $u, v \in V(T) \setminus S$, there exists a vertex $w \in S$ such that exactly one of $wu$ and $wv$ is an arc of $T$. Observe that such a set is a resolving set of $T$, so we have the following.

**Theorem 4.4** (Lozano [15]). $\overrightarrow{MD}(T) \le \lfloor|V(T)|/2\rfloor$ for every tournament $T$.

**Theorem 4.5.** $\overrightarrow{MD}^*(T) \le \lfloor|V(T)|/2\rfloor$ for every tournament $T$.

*Proof.* We prove the result by induction on $|V(T)| = n$.

If $T$ is strong, then $\overrightarrow{MD}^*(T) = \overrightarrow{MD}(T)$, so we have the result by Theorem 4.4. Henceforth we may assume that $T$ is not strong.

If $n$ is odd, then $\lfloor n/2 \rfloor = \lfloor n/2 \rfloor + 1$. By Theorem 4.4, $T$ has a resolving set $R$ of size $\lfloor n/2 \rfloor$. Then, $R$ may have at most one infinite vertex $v$, and adding it to $R$ leaves a strong resolving set $R \cup \{v\}$ of size at most $\lfloor n/2 \rfloor$. Henceforth, we may assume that $n$ is even.

Since $T$ is not strong, $T$ has a strong subtournament $B$ such that $T = A \to B$ with $A = T - B$. Set $n_A = |V(A)|$ and $n_B = |V(B)|$. If $n_A$ and $n_B$ are even, then, by the induction hypothesis, $\overrightarrow{MD}^*(A) \le \lfloor n_A/2 \rfloor = n_A/2$ and $\overrightarrow{MD}^*(B) \le \lfloor n_B/2 \rfloor = n_B/2$. Thus, by Lemma 2.9, $\overrightarrow{MD}^*(T) \le n_A/2 + n_B/2 = n/2$. Henceforth, we may assume that $n_A$ and $n_B$ are odd.

If $n_B > 1$, then $B$ is strong and non-trivial so $\overrightarrow{MD}^*(B) = \overrightarrow{MD}(B)$. Thus $\overrightarrow{MD}^*(B) \le \lfloor n_B/2 \rfloor = \frac{n_B-1}{2}$ by Theorem 4.4. By the induction hypothesis, $\overrightarrow{MD}^*(A) \le \lfloor n_A/2 \rfloor = \frac{n_A+1}{2}$. Therefore, by Lemma 2.9, $\overrightarrow{MD}^*(T) \le \frac{n_A+1}{2} + \frac{n_B-1}{2} = n/2$. Henceforth, we may assume that $n_B = 1$, say $B = \{b\}$.

If $A$ is strong, then $\overrightarrow{MD}^*(A) = \overrightarrow{MD}(A)$. Thus $\overrightarrow{MD}^*(A) \le \lfloor n_A/2 \rfloor = \frac{n_A-1}{2} = \frac{n}{2} - 1$ by Theorem 4.4. Let $R_A$ be a strong resolving set of $A$ of size $\frac{n}{2} - 1$. Trivially, $R_A \cup \{b\}$ is a strong
resolving set of $T$ of size $n/2$. Henceforth, we may assume that $A$ is non-strong. Thus $A$ has a strong subtournament $D$ such that $A = C \to D$ with $C = T - D$. Set $n_C = |V(C)|$ and $n_D = |V(D)|$.

If $n_D$ is even, then $D \to \{b\}$ has a resolving set $R_D$ of order $n_D/2$ by Theorem 4.4. Now $R_D$ must contain a vertex in $V(D)$, so $R_D$ is a strong resolving set of $D \to \{b\}$. By the induction hypothesis, $C$ has a strong resolving set $R_C$ of order $\lceil n_C/2 \rceil = \frac{n_C+1}{2}$. So by Lemma 2.7, $R_C \cup R_D$ is a strong resolving set of $T$, which has size $\frac{n_C+1}{2} + \frac{n_D}{2} = n/2$. Henceforth, we may assume that $n_D$ is odd, and so $n_C$ is even.

If $n_D > 1$, then $D$ is strong and non-trivial, so, by Theorem 4.4, $\overrightarrow{\mathrm{MD}}^*(D) = \overrightarrow{\mathrm{MD}}(D) \le \lfloor n_D/2 \rfloor = \frac{n_D-1}{2}$. Moreover, by the induction hypothesis, $\overrightarrow{\mathrm{MD}}^*(C) \le \lfloor n_C/2 \rfloor = \frac{n_C}{2}$, so by Lemma 2.9, $\overrightarrow{\mathrm{MD}}^*(C \to D) \le \frac{n_C}{2} + \frac{n_D-1}{2} = \frac{n}{2}-1$. Let $R$ be a strong resolving set of $C \to D$. Then $R \cup \{b\}$ is a strong resolving set of $T$ of size at most $\lfloor n/2 \rfloor$. Thus, we may assume that $n_D = 1$, say $D = \{d\}$.

Now, by the induction hypothesis, $C$ has a strong resolving set $R$ of size $\lfloor n_C/2 \rfloor = \frac{n}{2}-1$. Moreover, $\{d\}$ is a strong resolving set of $D \to B$. Thus, by Lemma 2.7, $R \cup \{d\}$ is a strong resolving set of $T$ of size $n/2$. $\square$

**Proposition 4.6.** Let $TT_n$ be the transitive tournament of order $n$. Then, $\overrightarrow{\mathrm{MD}}^*(TT_n) = \lfloor \frac{n}{2} \rfloor$ and $\overrightarrow{\mathrm{MD}}(TT_n) = \lfloor \frac{n}{2} \rfloor$.

*Proof.* Let $(v_1, \dots, v_n)$ be the transitive order of $TT_n$, that is, all edges $v_i v_j$ are oriented from $v_i$ to $v_j$ with $i < j$. The upper bounds follow from the previous theorems.

Let $R$ be a resolving set of $TT_n$. For every $i \in \{1, \dots, n-1\}$, there must be a vertex of $R$ that distinguishes $v_i$ and $v_{i+1}$. But $\mathrm{dist}(v_j, v_i) = \mathrm{dist}(v_j, v_{i+1}) = 1$ for all $1 \le j < i$, and $\mathrm{dist}(v_j, v_i) = \mathrm{dist}(v_j, v_{i+1}) = +\infty$ for all $i+1 < j \le n$. So the vertex distinguishing $v_i$ and $v_{i+1}$ is one of those two vertices. Thus $|R \cap \{v_i, v_{i+1}\}| \ge 1$ for all $i \in \{1, \dots, n-1\}$. This, implies $\overrightarrow{\mathrm{MD}}(TT_n) \ge \lfloor \frac{n}{2} \rfloor$, and $\overrightarrow{\mathrm{MD}}^*(TT_n) \ge \lfloor \frac{n}{2} \rfloor$ because every strong resolving set must contain $v_1$, which is a source in $TT_n$. $\square$

Theorems 4.4 and 4.5 and Proposition 4.6 directly imply the following.

**Corollary 4.7.** $\mathrm{WOMD}^*(K_n) = \lfloor \frac{n}{2} \rfloor$ and $\mathrm{WOMD}(K_n) = \lfloor \frac{n}{2} \rfloor$ for all positive integers $n$.

Recall that for an undirected graph $G$, the clique number $\omega(G)$ is the order of a largest clique (complete subgraph) in $G$. Corollary 4.7 and Proposition 4.1 directly imply the following.

**Corollary 4.8.** Let $G$ be a graph. Then $\mathrm{WOMD}^*(G) \ge \lfloor \frac{\omega(G)}{2} \rfloor$ and $\mathrm{WOMD}(G) \ge \lfloor \frac{\omega(G)}{2} \rfloor$.

**Theorem 4.9 (Ramsey [18])**. Let $p$ and $q$ be two positive integers. There exists a minimum integer $R(p, q)$ such that if $G$ has at least $R(p, q)$ vertices then either $\omega(G) \ge p$ or $\alpha(G) \ge q$.

**Theorem 4.10.** Let $G$ be a graph and $k$ be a positive integer.

(i) There is a (smallest) integer $C_k^*$ such that if $|V(G)| \ge C_k^*$ then $\mathrm{WOMD}^*(G) \ge k$.

(ii) There is a (smallest) integer $C_k$ such that if $|V(G)| \ge C_k$ then $\mathrm{WOMD}(G) \ge k$.

*Proof.* (i) Suppose $|V(G)| \ge R(2k-1, k)$. By Ramsey's Theorem (Theorem 4.9), either $\omega(G) \ge 2k-1$ or $\alpha(G) \ge k$. In the former case, Corollary 4.8 yields $\mathrm{WOMD}^*(G) \ge k$, and, in the latter case, Corollary 4.2 yields $\mathrm{WOMD}^*(G) \ge k$. Hence (i) holds and $C_k^* \le R(2k-1, k)$.

In the same way, assuming $|V(G)| \ge R(2k, k+1)$, we derive $\mathrm{WOMD}(G) \ge k$. Hence (ii) holds and $C_k \le R(2k, k+1)$. $\square$

**Corollary 4.11.** Let $k$ be a fixed positive integer. Given a graph $G$, deciding whether $\mathrm{WOMD}(G) \le k$ (resp. $\mathrm{WOMD}^*(G) \le k$) can be done in constant time (function of $k$).

*Proof.* By Theorem 4.10, there is a finite list $\mathcal{L}_k$ of graphs with $\mathrm{WOMD}(G) \le k$ (because $k$ is fixed). It then suffices to check whether the input graph $G$ is in $\mathcal{L}_k$, which can be done in constant time.

The same holds for graphs with $\mathrm{WOMD}^*(G) \le k$. $\square$
## 4.2 Worst orientation of forests

In this section, we give bounds on WOMD($F$) and WOMD*$({F})$ when $F$ is a forest. A consequence of our main result in Section 5 is that these values can be computed in linear time in that case.

**Theorem 4.12.** $\overrightarrow{\text{MD}}^*(D) \le \alpha(D)$ for every oriented forest $D$.

*Proof.* By Proposition 2.5 and the fact that the stability number of a digraph is the sum of the stability numbers of its connected components, it suffices to prove the theorem for oriented trees.

We do so by induction on the number of vertices of $D$, the result holding trivially if $D$ is an oriented star. Assume now that $D$ is an oriented tree but not an oriented star. Consider the first three vertices $u, v, w$ of a path $P$ whose length is equal to the diameter of the tree underlying $D$. Among the neighbours of $v$, only $w$ is not a leaf. Let $U = N[v] \setminus \{w\}$ and $D' = D - U$. By the induction hypothesis $D'$ admits a strong resolving set $S'$ of size $\alpha(D')$, and $D[U]$ is an oriented star which admits a strong resolving set $S_U$ of size $\alpha(D[U]) = |U| - 1$. By Lemma 2.7, we have that $S = S_U \cup S'$ is a strong resolving set of $D$. Moreover $\alpha(D) = \alpha(D') + |U| - 1$. Hence, $S$ is a strong resolving set of size $\alpha(D)$. $\square$

Theorem 4.12 and Corollary 4.2 directly imply the following corollary.

**Corollary 4.13.** If $F$ is a forest, then WOMD$^*(F) = \alpha(F)$ and $\alpha(F) - 1 \le \text{WOMD}(F) \le \alpha(F)$.

In view of the latter corollary, there are two kinds of forests $F$: ($\alpha - 1$)-forests for which WOMD($F$) = $\alpha(F) - 1$, and $\alpha$-forests for which WOMD($F$) = $\alpha(F)$. Similarly, a tree $T$ is an ($\alpha - 1$)-tree (resp. $\alpha$-tree) if WOMD($T$) = $\alpha(T) - 1$ (resp. WOMD($T$) = $\alpha(T)$).

Lemma 4.3 and Corollary 4.13 directly imply the following.

**Proposition 4.14.** A forest is an $\alpha$-forest if, and only if, it is the disjoint union of $\alpha$-trees.

Hence, in order to characterise $\alpha$-forests (and at the same time ($\alpha - 1$)-forests), it suffices to characterise $\alpha$-trees. In Section 5, we give a linear-time algorithm that, given a tree $T$, computes WOMD($T$) and WOMD$^*(T)$. Henceforth, using this algorithm and comparing the two values, we can decide in linear time whether a given tree is an $\alpha$-tree or not. However, this algorithm does not yield an explicit characterisation.

In the sequel, we show that every star is an $\alpha$-tree and explicitly characterise the paths that are $\alpha$-trees. We then provide constructions for building infinitely many ($\alpha - 1$)-trees and $\alpha$-trees.

### 4.2.1 Worst orientations of stars and paths

**Theorem 4.15.** Let $S_n$ be the star on $n$ vertices, $n \ge 2$. Then, WOMD($S_n$) = $\alpha(S_n) = n - 1$.

*Proof.* Let $D$ be the orientation of $S_n$ obtained by orienting all edges towards the leaves. Note that any two leaves of $D$ have the same in-neighbourhood, and any resolving set of $D$ must thus include at least $n-2$ leaves. But a set containing $n-2$ leaves only is not resolving, as the center vertex and the last leaf cannot be distinguished. Thus, any resolving set of $D$ must include an extra vertex. Hence WOMD($S_n$) $\ge \overrightarrow{\text{MD}}(D) \ge n - 1$. The result then follows from Corollary 4.13. $\square$

We denote by $P_n$ the path on $n$ vertices.

**Theorem 4.16.** Let $n$ be a positive integer. Then WOMD($P_n$) = $\alpha(P_n) - 1 = \lfloor \frac{n}{2} \rfloor$ if, and only if, $n \equiv 1 \bmod 4$.

*Proof.* The proof is by induction on $n$. As a base case, the claim is true whenever $n \in \{1, 2, 3, 4\}$, as attested in Figure 2, where minimum resolving sets are provided for all non-isomorphic orientations. In particular, WOMD($P_1$) = $\alpha(P_1) - 1 = 0$, WOMD($P_2$) = $\alpha(P_2) = 1$, and WOMD($P_i$) = $\alpha(P_i) = 2$ for $i \in \{3, 4\}$.

Assume now that $n > 4$. Let $P_n = (v_1, \dots, v_n)$. Set $P' = (v_5, \dots, v_n)$ and $P'' = (v_1, \dots, v_4)$. Note that $\alpha(P_n) = \alpha(P') + 2$.

Assume first that $n \not\equiv 1 \bmod 4$. By the induction hypothesis, there is an orientation $D'$ of $P'$ such that $\overrightarrow{\text{MD}}(D') = \alpha(P')$. Let $D$ be the orientation of $P_n$ that agrees with $D'$ on $P'$ and such that
<figure><img src="image_3.png" /><figcaption>Figure 2: Non-isomorphic orientations of $P_n$ for $n \in \{1, 2, 3, 4\}$. For each orientation, the set of grey vertices is a minimum resolving set.</figcaption></figure>

$v_5v_4, v_3v_4, v_2v_3$ and $v_2v_1$ are arcs. Note that no vertex in $\{v_1, \dots, v_4\}$ may be used to distinguish vertices in $(v_5, \dots, v_n)$, because the arc $v_5v_4$ yields infinite distances. Hence $R \cap \{v_5, \dots, v_n\}$ must be a resolving set for $D'$, for every resolving set $R$ of $D$. Moreover, at least two vertices among $\{v_1, v_2, v_3\}$ are needed to distinguish $v_1, v_2, v_3$. Hence, every resolving set of $D$ has size at least $\alpha(P') + 2 = \alpha(P_n)$. So $\text{WOMD}(P_n) \ge \overrightarrow{\text{MD}}(D) \ge \alpha(P_n)$, and, by Corollary 4.13, we get $\text{WOMD}(P_n) = \alpha(P_n)$.

Assume now that $n \equiv 1 \bmod 4$. We prove that $\text{WOMD}(P_n) \le \alpha(P_n) - 1$. In fact, we show that for every orientation $D$ of $P_n$ we get: $(*) \overrightarrow{\text{MD}}(D) \le \overrightarrow{\text{MD}}(D') + 2$, where $D'$ is the orientation $D$ restricted to $P'$. Since $\overrightarrow{\text{MD}}(D') = \alpha(D') - 1$ by the induction hypothesis, and $\alpha(D) = \alpha(D') + 2$, we get that $\overrightarrow{\text{MD}}(D) \le \alpha(D) - 1$ for every orientation $D$ of $P_n$, as we wanted to show. The fact that $(*)$ holds can be verified in Figure 3. The grey vertices represent the vertices that can be added to a resolving set of $D'$ in order to obtain a resolving set of $D$. $\square$

<figure><img src="image_4.png" /><figcaption>Figure 3: All cases for concluding the proof of Theorem 4.16. For each orientation of $P_n$, the set of grey vertices is a minimum resolving set. “$+\infty$” below a vertex indicates that this vertex is infinite. Note that, the eight cases when the edge $\{v_4, v_5\}$ is oriented towards $v_4$ are not depicted. Indeed, in these cases, the grey vertices still distinguish vertices in $\{v_1, \dots, v_4\}$, while $v_5$ is distinguished by a resolving set of $P' = (v_5, \dots, v_n)$.</figcaption></figure>

### 4.2.2 Constructing ($\alpha - 1$)-trees and $\alpha$-trees from smaller ones

Here, we provide constructions for building $\alpha$-trees (resp. ($\alpha - 1$)-trees) from smaller $\alpha$-trees (resp. ($\alpha - 1$)-trees), such as stars and paths investigated in the previous subsection.

**Theorem 4.17.** Let $T$ be an $\alpha$-tree, and $v$ be a vertex belonging to all maximum stable sets of $T$. Let $k \ge 2$, and $T'$ be the tree obtained from $T$ by adding $k$ new vertices $u_1, \dots, u_k$ and making them adjacent to $v$. Then $T'$ is an $\alpha$-tree.

*Proof.* Since $v$ belongs to all maximum stable sets of $T$, by construction we have $\alpha(T') = \alpha(T) + k - 1$. In particular, every maximum stable set $S'$ of $T'$ can be obtained from a maximum stable set $S$ of $T$, removing $v$ from $S$, and adding $u_1, \dots, u_k$ to $S$. Now let $D$ be an orientation of $T$ verifying $\overrightarrow{\text{MD}}(D) = \text{WOMD}(T) = \alpha(T)$, and let $D'$ be the orientation of $T'$ obtained from $D$ by orienting every edge $vu_i$ from $v$ to $u_i$, for each $i \in \{1, \dots, k\}$. Note that, in $D'$, no vertex $u_i$ can
resolve vertices in $V(T)$. Furthermore, in order to distinguish the $u_i$'s, any resolving set of $D'$ must include all $u_i$'s but at most one. Thus

$$ \overrightarrow{MD}(D') \geq \overrightarrow{MD}(D) + k - 1 = \alpha(T) + k - 1 = \alpha(T'). $$

Therefore, $\overrightarrow{MD}(D') = \alpha(T')$ by Corollary 4.13, and $WOMD(T') = \alpha(T')$. $\square$

**Theorem 4.18.** Let $T$ be an $\alpha$-tree, and $v$ be a vertex belonging to all maximum stable sets of $T$. Let $T'$ be the tree obtained from $T$ by adding three new vertices $u_1, u_2, u_3$ and the edges $vu_1, u_1u_2, u_2u_3$. Then $T'$ is an $\alpha$-tree.

*Proof.* Every maximum stable set $S'$ of $T'$ is either obtained from a maximum stable set $S$ of $T$ by adding either $u_2$ or $u_3$, or obtained from $S$ by removing $v$ and adding $u_1, u_3$. In other words, we have $\alpha(T') = \alpha(T) + 1$. Now let $D$ be an orientation of $T$ verifying $\overrightarrow{MD}(D) = WOMD(T) = \alpha(T)$, and let $D'$ be the orientation of $T'$ obtained from $D$ by orienting $vu_1$ from $v$ to $u_1, u_2u_1$ from $u_2$ to $u_1$, and $u_3u_2$ from $u_3$ to $u_2$. Note that, in $D'$, the only way to distinguish $u_2$ and $u_3$ is via $u_3$ or $u_2$. Thus

$$ \overrightarrow{MD}(D') \geq \overrightarrow{MD}(D) + 1 = \alpha(T) + 1 = \alpha(T'). $$

Therefore, $\overrightarrow{MD}(D') = \alpha(T')$ by Corollary 4.13, and $WOMD(T') = \alpha(T')$. $\square$

**Theorem 4.19.** Let $T_1, \dots, T_k$ be $\alpha$-trees, $k \geq 2$, and $r_1, \dots, r_k$ be vertices where $r_i \in V(T_i)$ for each $i \in \{1, \dots, k\}$. Assume $r_1$ belongs to all maximum stable sets of $T_1$. Then, the tree $T$ obtained from $T_1, \dots, T_k$ by adding a new vertex $r$ and making it adjacent to all of $r_1, \dots, r_k$, is an $\alpha$-tree.

*Proof.* Note that, by our assumption on $r_1$, we have $\alpha(T) = \sum_{i=1}^k \alpha(T_i)$. Let $D$ be the orientation of $T$ obtained by orienting each of its $T_i$'s the worst way possible (i.e. each $T_i$ is oriented in a way $D_i$ such that $\overrightarrow{MD}(D_i) = WOMD(T_i)$), and orienting all edges $r_i r$ towards $r$. Due to the orientation of the latter arcs, we clearly have

$$ \overrightarrow{MD}(D) \geq \sum_{i=1}^{k} \overrightarrow{MD}(D_i) = \sum_{i=1}^{k} WOMD(T_i) = \sum_{i=1}^{k} \alpha(T_i) = \alpha(T), $$

which proves the claim. $\square$

**Theorem 4.20.** Let $T_1, T_2$ be two $(\alpha-1)$-trees, and $r_1, r_2$ be vertices of $T_1, T_2$, respectively. Assume $r_1, r_2$ belong to all maximum stable sets of $T_1, T_2$, respectively. Then, the tree $T$ obtained from $T_1, T_2$ by adding the edge $r_1 r_2$ is an $(\alpha-1)$-tree.

*Proof.* Note that $\alpha(T) = \alpha(T_1) + \alpha(T_2) - 1$. Consider $D$ any orientation of $T$. W.l.o.g., we can assume that $r_1 r_2$ is oriented towards $r_2$. Let now $S$ be a minimum resolving set of $D$. Due to the orientation of the arc $r_1 r_2$, the set $S \cap V(T_1)$ must be a resolving set of $D_1$, the orientation of $T_1$ deduced from $D$. Thus $|S \cap V(T_1)| \leq \overrightarrow{MD}(D_1) \leq WOMD(T_1) = \alpha(T_1) - 1$. From the point of view of $D_2$, the orientation of $T_2$ derived from $D$, $S \cap V(T_2)$ might not be resolving, but, if this occurs, then we know that $(S \cap V(T_2)) \cup \{r_2\}$ is a resolving set of $D_2$. Thus $|S \cap V(T_2)| \leq \overrightarrow{MD}(D_2) - 1 \leq WOMD(T_2) - 1 = \alpha(T_2) - 2$, and $|S| \leq \alpha(T) - 1$. $\square$

# 5 Finding WOMD, BOMD, WOMD* and BOMD* for trees and forests

In this section, we prove that given a tree $T$, one can find $BOMD^*(T)$, $BOMD(T)$, $WOMD^*(T)$ and $WOMD(T)$ in linear time. Also, orientations attaining these values can be retrieved. Note that using Lemmas 3.3 and 4.3, this implies that, given a forest $F$, one can find $BOMD^*(F)$, $BOMD(F)$, $WOMD^*(F)$ and $WOMD(F)$ in linear time.

Our algorithm uses a dynamic programming approach. Therefore, we root the tree $T$ at some vertex $r$. Let $D$ be an orientation of $T$ and $s$ be a source in $D$. We say that $a \in V(D)$ is a 1-witness for $s$ if $N^-(a) = \{s\}$. We say that $(a, b, c) \in V(D)^3$ is a 2-witness for $s$ if $s \neq b$, $N^-(a) = \{s, b\}$,
and $N^-(c) = \{b\}$. A witness for $s$ is a 1-witness or a 2-witness and a witness for $s$ is unique if there is no other witness for $s$. Recall from the proof of Corollary 2.15 that a source $s \in V(D)$ is removable (in $D$) if, and only if, there are no witnesses for $s$ in $D$.

For $v \in V(T)$ with children $v_1, \dots, v_d$, let $T_v$ be the subtree of $T$ rooted in $v$, and for each $i \in \{1, \dots, d\}$, let $T_{v,i}$ be the subtree induced by $\{v\} \cup \bigcup_{j=1}^i V(T_{v,j})$. Also let $T_{v,0}$ denote the trivial tree $(\{v\}, \emptyset)$, and note that $T_v = T_{v,d}$. In this section, we compute BOMD($T$) and WOMD($T$) in a bottom up way using dynamic programming. For this, let us consider a few properties that a given orientation $D$ of $T_{v,i}$ may have.

**Property s:** $v$ is a source in $D$.

**Property r:** $v$ is a removable source in $D$.

**Property u:** there is a source $s$ in $D$ with a 2-witness $(a, b, c)$, and either $v = c$, in which case $(a, b, c)$ is the unique witness for $s$, or $v = a$, in which case every witness for $s$ is of the form $(a = v, b, c')$ for some vertex $c'$.

**Property $\overleftarrow{a}$:** there is a source $s$ in $D$ s.t. $v$ is a 1-witness which is a unique witness for $s$ in $D$.

**Property $\overrightarrow{a}$:** there are $b, c \in V(T_{v,i})$ such that $v \neq c$ and $N_D^-(v) = N_D^-(c) = \{b\}$.

**Property $\overleftarrow{b}$:** there are $s, a \in V(T_{v,i})$ s.t. $N_D^-(a) = \{s, v\}$ and $s$ is a removable source in $D$.

**Property $\overrightarrow{b}$:** there is $c \in V(T_{v,i})$ such that $N_D^-(c) = \{v\}$.

**Property $r^*$:** $D$ contains a removable source $s$ such that $s \neq v$ and there is no vertex $a \in V(T_{v,i})$ such that $N_D^-(a) = \{s, v\}$.

Regarding these properties, a removable source $s$ can be of three kinds: it is an **r-source** if $s = v$, a **b-source** if there exists $a \in V(T_{v,i})$ such that $N_D^-(a) = \{s, v\}$, and an **r*-source otherwise. The general idea of our dynamic programming algorithm is to keep track on whether or not, orientations have a removable source. Intuitively, the **r**-sources are the ‘safe’ ones, in the sense that they will remain removable sources in the remaining of the algorithm because they are so far from the root of their subtree that no witness for them can be later created. **r-sources** and **b-sources** are ‘dangerous’ in the sense that such a source might, in the rest of the algorithm, either not remain a source (if it is the root of the subtree and an arc towards it is added) or not remain removable because some witnesses for them can be created. In the opposite, upon deleting the witnesses of some remove source, note that new removable sources may appear. The appearance and disappearance of removable sources happen in very particular cases that can be characterised in terms of the above properties. See Subsection 5.1.

Let $\mathcal{P} = \{\mathbf{s}, \mathbf{r}, \mathbf{u}, \overleftarrow{\mathbf{a}}, \overrightarrow{\mathbf{a}}, \overleftarrow{\mathbf{b}}, \overrightarrow{\mathbf{b}}, \mathbf{r}^*\}$ be the set of properties an orientation can have. For $X \subseteq \mathcal{P}$, we say that an orientation $D$ of $T_{v,i}$ agrees with $X$ if $X$ describes exactly all the properties that $D$ has, i.e. if $D$ has the properties in $X$ and has no properties in $\mathcal{P} \setminus X$. The next lemma tells us that in order to compute $\overrightarrow{\mathrm{MD}}(D)$, we only need to know the value $\overrightarrow{\mathrm{MD}}^*(D)$ and the set of properties with which $D$ agrees. Let $1[c]$ be the indicator function that condition $c$ is true: $1[c] = 1$ if $c$ is true and $1[c] = 0$ otherwise.

**Lemma 5.1.** If $D$ is an orientation of $T_{v,i}$ that agrees with $X \subseteq \mathcal{P}$, then

$$ \overrightarrow{\mathrm{MD}}(D) = \overrightarrow{\mathrm{MD}}^*(D) - 1 \left[ X \cap \{\mathbf{r}, \overleftarrow{\mathbf{b}}, \mathbf{r}^*\} \neq \emptyset \right]. $$

*Proof.* Corollary 2.15 states that $\overrightarrow{\mathrm{MD}}(D) = \overrightarrow{\mathrm{MD}}^*(D) - 1$ if $D$ has a removable source and $\overrightarrow{\mathrm{MD}}(D) = \overrightarrow{\mathrm{MD}}^*(D)$ otherwise. Since $D$ agrees with $X$, we know that $D$ has a removable source if, and only if, $X \cap \{\mathbf{r}, \overleftarrow{\mathbf{b}}, \mathbf{r}^*\} \neq \emptyset$ $\square$

Therefore, in order to compute BOMD($T_{v,i}$) and WOMD($T_{v,i}$) (and similarly $\mathrm{BOMD}^*(T_{v,i})$ and $\mathrm{WOMD}^*(T_{v,i})$), we just need to keep track of the best and worst values of the strong metric dimension related to orientations that agree with each possible subset of properties. More formally,
for each $X \subseteq \mathcal{P}$, let $B_X(v, i)$ and $W_X(v, i)$ be, respectively, the minimum and maximum value of $\overrightarrow{\text{MD}}^*(D)$ over all orientations $D$ of $T_{v,i}$ that agrees with $X$. We set $B_X(v, i) = +\infty$ and $W_X(v, i) = -\infty$ if no orientation of $T_{v,i}$ agrees with $X$. If $v$ has $d$ children, then we use $B_X(v)$ and $W_X(v)$ to denote $B_X(v, d)$ and $W_X(v, d)$, respectively. By the previous lemma, the desired values can be extracted from the tables of the root $r$, namely by letting $\delta(X) = 1$ [$X \cap \{\mathbf{r}, \overleftarrow{\mathbf{b}}, \mathbf{r}^*\} \neq \emptyset$], we get:

$$ \text{BOMD}(T) = \min_{X \subseteq \mathcal{P}} (B_X(r) - \delta(X)), \text{ and} \quad (4) $$

$$ \text{WOMD}(T) = \max_{X \subseteq \mathcal{P}} (W_X(r) - \delta(X)). \quad (5) $$

**Theorem 5.2.** For $v \in V(T)$, we have

$$ \text{BOMD}(T_v) = \min_{X \subseteq \mathcal{P}} \left( B_X(v) - 1 \left[ X \cap \{\mathbf{r}, \overleftarrow{\mathbf{b}}, \mathbf{r}^*\} \neq \emptyset \right] \right) $$

$$ \text{WOMD}(T_v) = \max_{X \subseteq \mathcal{P}} \left( W_X(v) - 1 \left[ X \cap \{\mathbf{r}, \overleftarrow{\mathbf{b}}, \mathbf{r}^*\} \neq \emptyset \right] \right) $$

$$ \text{BOMD}^*(T_v) = \min_{X \subseteq \mathcal{P}} B_X(v) $$

$$ \text{WOMD}^*(T_v) = \max_{X \subseteq \mathcal{P}} W_X(v) $$

*Proof.* Let $D$ be an orientation of $T_v$ that minimises $\overrightarrow{\text{MD}}(D)$. Let $X \subseteq \mathcal{P}$ be such that $D$ agrees with $X$. Using Lemma 5.1, we get that

$$ \begin{aligned} \text{BOMD}(T_v) &= \overrightarrow{\text{MD}}(D) = \overrightarrow{\text{MD}}^*(D) - 1 \left[ X \cap \{\mathbf{r}, \overleftarrow{\mathbf{b}}, \mathbf{r}^*\} \neq \emptyset \right] \\ &\geq B_X(v) - 1 \left[ X \cap \{\mathbf{r}, \overleftarrow{\mathbf{b}}, \mathbf{r}^*\} \neq \emptyset \right] \\ &\geq \min_{X \subseteq \mathcal{P}} \left( B_X(v) - 1 \left[ X \cap \{\mathbf{r}, \overleftarrow{\mathbf{b}}, \mathbf{r}^*\} \neq \emptyset \right] \right). \end{aligned} \quad (6) $$

On the other hand, let $X \subseteq \mathcal{P}$ and suppose there is some orientation of $T_v$ that agrees with $X$. Let $D$ be an orientation of $T_v$ that agrees with $X$ and minimises $\overrightarrow{\text{MD}}^*(D)$. By definition, we have

$$ \text{BOMD}(T_v) \leq \overrightarrow{\text{MD}}(D) $$

and, by using Lemma 5.1, we get

$$ \begin{aligned} \text{BOMD}(T_v) &\leq \overrightarrow{\text{MD}}(D) = \overrightarrow{\text{MD}}^*(D) - 1 \left[ X \cap \{\mathbf{r}, \overleftarrow{\mathbf{b}}, \mathbf{r}^*\} \neq \emptyset \right] \\ &= B_X(v) - 1 \left[ X \cap \{\mathbf{r}, \overleftarrow{\mathbf{b}}, \mathbf{r}^*\} \neq \emptyset \right], \end{aligned} \quad (7) $$

where the last equality comes from the definition of $B_X(v)$. Since Inequality 7 is valid for any $X \subseteq \mathcal{P}$, we have

$$ \text{BOMD}(T_v) \leq \min_{X \subseteq \mathcal{P}} \left( B_X(v) - 1 \left[ X \cap \{\mathbf{r}, \overleftarrow{\mathbf{b}}, \mathbf{r}^*\} \neq \emptyset \right] \right). \quad (8) $$

We get the first equality of this theorem from Inequalities 6 and 8. The second equality of this theorem is analogous to the first one. The third and fourth inequalities follow directly from the definition of $B_X(v)$. $\square$

We compute the table of $T_{v,i}$ assuming that we know the tables of $T_{v,i-1}$ and of $T_{v_i}$. Therefore, our base cases are the trivial subtrees $T_{v,0}$, for each $v \in V(T)$.

**Lemma 5.3.** For $v \in V(T)$ and $X \subseteq \mathcal{P}$, we have $B_X(v, 0) = W_X(v, 0) = 1$, if $X = \{\mathbf{s}, \mathbf{r}\}$, or $B_X(v, 0) = +\infty$ and $W_X(v, 0) = -\infty$, otherwise.

*Proof.* Since $T_{v,0}$ has a unique vertex, it has a unique orientation which only agrees with $X = \{\mathbf{s}, \mathbf{r}\}$ and has strong metric dimension 1. $\square$
Now, given $v \in V(T)$ with children $v_1, \dots, v_d, X \subseteq \mathcal{P}$, and $i \in \{1, \dots, d\}$, we need to show that we can compute $B_X(v, i)$, $W_X(v, i)$ based on the tables of $T_{v,i-1}$ and of $T_{v,i}$. For this, we need to understand how an entry $X_1$ of $T_{v,i-1}$ can be combined with an entry $X_2$ of $T_{v,i}$ into an entry $X$ of $T_{v,i}$. For $X_1, X_2 \subseteq \mathcal{P}$ and $o \in \{\mathbf{in}, \mathbf{out}\}$, an orientation $D$ of $T_{v,i}$ is called an $(X_1, X_2, o)$-orientation if $D$ agrees with $X_1$ when restricted to $T_{v,i-1}$, agrees with $X_2$ when restricted to $T_{v,i}$, and the edge $vv_i$ is oriented towards $v$ if $o = \mathbf{in}$ and away from $v$ if $o = \mathbf{out}$. The next lemma tells us how to compute the size of a minimum strong resolving set of an $(X_1, X_2, o)$-orientation as a function of the values on the subtrees and a function that depends only on $X_1, X_2$ and $o$. To simplify its statement, let

$$ \delta(X_1, X_2, o) = -1 [(\mathbf{s} \in X_1 \text{ and } o = \mathbf{in}) \text{ or } (\mathbf{s} \in X_2 \text{ and } o = \mathbf{out})] \\ + 1 [(\mathbf{s} \in X_1 \text{ and } \vec{\mathbf{b}} \in X_2 \text{ and } o = \mathbf{in}) \text{ or } (\mathbf{s} \in X_2 \text{ and } \vec{\mathbf{b}} \in X_1 \text{ and } o = \mathbf{out})] \\ - 1 [(\vec{\mathbf{a}} \in X_1 \text{ and } o = \mathbf{in}) \text{ or } (\vec{\mathbf{a}} \in X_2 \text{ and } o = \mathbf{out})]. $$

**Lemma 5.4.** If $D$ is an $(X_1, X_2, o)$-orientation of $T_{v,i}$ such that $D_1$ and $D_2$ are the orientations of $D$ restricted $T_{v,i-1}$ and $T_{v,i}$, respectively, then

$$ \overrightarrow{MD}^*(D) = \overrightarrow{MD}^*(D_1) + \overrightarrow{MD}^*(D_2) + \delta(X_1, X_2, o) $$

*Proof.* We know from Corollary 2.12 that

$$ \overrightarrow{MD}^*(D) = |S(D)| + |V(D)| - |\mathcal{T}(D)|. \qquad (9) $$

Furthermore, we have

$$ |V(D)| = |V(D_1)| + |V(D_2)|. \qquad (10) $$

A source in $D_1$ is a source in $D$ except when $v$ is a source and $v_iv$ is an arc of $D$, which happens when $\mathbf{s} \in X_1$ and $o = \mathbf{in}$. Similarly, every source in $D_2$ is a source of $D$ except possibly $v_i$ when $\mathbf{s} \in X_2$ and $o = \mathbf{out}$. Therefore,

$$ |S(D)| = |S(D_1)| + |S(D_2)| - 1 [(\mathbf{s} \in X_1 \text{ and } o = \mathbf{in}) \text{ or } (\mathbf{s} \in X_2 \text{ and } o = \mathbf{out})]. \quad (11) $$

Denote by $a$ the arc in $\{vv_i, v_iv\} \cap A(D)$. Observe that $\mathcal{T}(D-a) = \mathcal{T}(D_1) \cup \mathcal{T}(D_2)$ and $|\mathcal{T}(D-a)| = |\mathcal{T}(D_1)| + |\mathcal{T}(D_2)|$. So the partition $\mathcal{T}(D)$ may differ from $\mathcal{T}(D_1) \cup \mathcal{T}(D_2)$ only because of the orientation of the edge $vv_i$. It happens only in one of the following cases.

* $\{v\}$ is a singleton of $\mathcal{T}(D-a)$ but not of $\mathcal{T}(D)$. In such a case, in $\mathcal{T}(D)$, $v$ is in the same part as another vertex, say $c$. Hence $N^-(c) = N^-(v) = \{v_i\}$, and so we must have $o = \mathbf{in}$ and $v$ is a source in $D_1$. This is equivalent to $\mathbf{s} \in X_1, \vec{\mathbf{b}} \in X_2$ and $o = \mathbf{in}$.

* $\{v_i\}$ is a singleton of $\mathcal{T}(D-a)$ but not of $\mathcal{T}(D)$. Similarly to the previous case, such a case happens when $\mathbf{s} \in X_2, \vec{\mathbf{b}} \in X_1$ and $o = \mathbf{out}$.

* $\{v\}$ is a singleton of $\mathcal{T}(D)$ but not of $\mathcal{T}(D-a)$. In such a case, there exist $b, c \in V(T_{v,i-1})$ such that $c \neq v, N_{D_1}^-(v) = N_{D_1}^-(c) = \{b\}$, and $d_D^-(v) = 2$ so that it is in a singleton of $\mathcal{T}(D)$; this happens precisely when $\vec{\mathbf{a}} \in X_1$ and $o = \mathbf{in}$.

* $\{v_i\}$ is a singleton of $\mathcal{T}(D)$ but not of $\mathcal{T}(D-a)$. Similarly, to the previous case, such a case happens when $\vec{\mathbf{a}} \in X_2$ and $o = \mathbf{out}$.

In all other cases, we have $\mathcal{T}(D) = \mathcal{T}(D-a)$. Thus,

$$ |\mathcal{T}(D)| = |\mathcal{T}(D_1)| + |\mathcal{T}(D_2)| + 1 [(\vec{\mathbf{a}} \in X_1 \text{ and } o = \mathbf{in}) \text{ or } (\vec{\mathbf{a}} \in X_2 \text{ and } o = \mathbf{out})] \\ - 1 [(\mathbf{s} \in X_1 \text{ and } \vec{\mathbf{b}} \in X_2 \text{ and } o = \mathbf{in}) \text{ or } (\mathbf{s} \in X_2 \text{ and } \vec{\mathbf{b}} \in X_1 \text{ and } o = \mathbf{out})]. \quad (12) $$

The result of this lemma is obtained by combining Equations 9, 10, 11 and 12 together with Corollary 2.12 on $D_1$ and $D_2$. $\square$
The following result is rather technical and we postpone its proof until Section 5.1.

**Theorem 5.5.** There exists a function $f: 2^P \times 2^P \times \{\text{in, out}\} \to 2^P$ such that, if an $(X_1, X_2, o)$-orientation of $T_{v,i}$ agrees with $X$, then $f(X_1, X_2, o) = X$. Furthermore, $f(X_1, X_2, o)$ can be computed in constant time for any $(X_1, X_2, o) \in 2^P \times 2^P \times \{\text{in, out}\}$.

Let $A(X)$ be the set of all triples $(X_1, X_2, o) \in 2^P \times 2^P \times \{\text{in, out}\}$ such that there exists an $(X_1, X_2, o)$-orientation $D$ that agrees with $X$. Observe that Theorem 5.5 tells us that $A(X) = f^{-1}(X)$ and therefore that $\{A(X) | X \subseteq P\}$ forms a partition of $2^P \times 2^P \times \{\text{in, out}\}$. In particular, we have $|A(X)| \le 2^{17}$. The following result provides the appropriate formulas to compute $B_X(v, i)$ and $W_X(v, i)$, which is necessary for our dynamic programming algorithm.

**Theorem 5.6.** Let $v \in V(T)$ have $d$ children and $1 \le i \le d$. For $X \subseteq P$, we have

$$ B_X(v, i) = \begin{cases} \min_{(X_1, X_2, o) \in A(X)} (B_{X_1}(v, i-1) + B_{X_2}(v_i) + \delta(X_1, X_2, o)), & \text{if } A(X) \neq \emptyset \\ +\infty, & \text{if } A(X) = \emptyset \end{cases} \quad (13) $$

and

$$ W_X(v, i) = \begin{cases} \max_{(X_1, X_2, o) \in A(X)} (W_{X_1}(v, i-1) + W_{X_2}(v_i) + \delta(X_1, X_2, o)), & \text{if } A(X) \neq \emptyset \\ -\infty, & \text{if } A(X) = \emptyset. \end{cases} \quad (14) $$

*Proof.* We first note that if no orientation of $T_{v,i}$ agrees with $X$, then, by definition, $B_X(v, i) = +\infty$ and $W_X(v, i) = -\infty$. In particular, this is the case if $A(X) = \emptyset$. Furthermore, if no orientation of $T_{v,i}$ agrees with $X$ and $A(X) \neq \emptyset$, then for every $(X_1, X_2, o) \in A(X)$ either there is no orientation of $T_{v,i-1}$ that agrees with $X_1$ or there is no orientation of $T_{v,i}$ that agrees with $X_2$. This implies:

$$ B_X(v, i) = +\infty = \min_{(X_1, X_2, o) \in A(X)} (B_{X_1}(v, i-1) + B_{X_2}(v_i) + \delta(X_1, X_2, o)). $$

and

$$ W_X(v, i) = -\infty = \max_{(X_1, X_2, o) \in A(X)} (W_{X_1}(v, i-1) + W_{X_2}(v_i) + \delta(X_1, X_2, o)). $$

From now on, we consider that there is some orientation of $T_{v,i}$ that agrees with $X$ and, for some $(X_1, X_2, o) \in A(X)$, there is an orientation of $T_{v,i-1}$ that agrees with $X_1$ and an orientation of $T_{v,i}$ that agrees with $X_2$.

Let $D$ be an orientation of $T_{v,i}$ that agrees with $X$ and minimises $\overrightarrow{MD}^*(D)$. Let $X_1, X_2 \subseteq P$ and $o \in \{\text{in, out}\}$ be such that $D$ is an $(X_1, X_2, o)$-orientation of $T_{v,i}$. Let $D_1$ and $D_2$, respectively, be the orientations of $D$ restricted to $T_{v,i-1}$ and $T_{v,i}$. By definition, we have

$$ \overrightarrow{MD}^*(D_1) \ge B_{X_1}(v, i-1) $$

and

$$ \overrightarrow{MD}^*(D_2) \ge B_{X_2}(v_i). $$

Now, using Lemma 5.4, we get

$$ \begin{align} B_X(v, i) &= \overrightarrow{MD}^*(D) = \overrightarrow{MD}^*(D_1) + \overrightarrow{MD}^*(D_2) + \delta(X_1, X_2, o) \nonumber \\ &\ge B_{X_1}(v, i-1) + B_{X_2}(v_i) + \delta(X_1, X_2, o) \tag{15} \\ &\ge \min_{(X_1, X_2, o) \in A(X)} (B_{X_1}(v, i-1) + B_{X_2}(v_i) + \delta(X_1, X_2, o)). \nonumber \end{align} $$

Now, let $(X_1, X_2, o) \in A(X)$ such that there is an orientation of $T_{v,i-1}$ that agrees with $X_1$ and an orientation of $T_{v,i}$ that agrees with $X_2$. In this case, both $B_{X_1}(v, i-1)$ and $B_{X_2}(v_i)$ are finite. Let $D_1$ be an orientation of $T_{v,i-1}$ that agrees with $X_1$ and with $\overrightarrow{MD}^*(D_1) = B_{X_1}(v, i-1)$. Let $D_2$ be an orientation of $T_{v,i}$ that agrees with $X_2$ and with $\overrightarrow{MD}^*(D_2) = B_{X_2}(v_i)$. Let $D$ be the
orientation of $T_{v,i}$ that extends $D_1$ and $D_2$ by orienting the edge $vv_i$ from $v$ to $v_i$ if $o = \textbf{out}$ and from $v_i$ to $v$ if $o = \textbf{in}$. Since $(X_1, X_2, o) \in A(X)$, we have that $D$ agrees with $X$ and, therefore,

$$B_X(v, i) \leq \overrightarrow{MD}^*(D).$$

Finally, using Lemma 5.4, we get

$$ \begin{aligned} B_X(v, i) &\leq \overrightarrow{MD}^*(D) = \overrightarrow{MD}^*(D_1) + \overrightarrow{MD}^*(D_2) + \delta(X_1, X_2, o) \\ &= B_{X_1}(v, i-1) + B_{X_2}(v_i) + \delta(X_1, X_2, o). \end{aligned} \quad (16) $$

Since Inequality 16 is valid for every $(X_1, X_2, o) \in A(X)$, we have

$$ B_X(v, i) \leq \min_{(X_1, X_2, o) \in A(X)} (B_{X_1}(v, i-1) + B_{X_2}(v_i) + \delta(X_1, X_2, o)). \quad (17) $$

Equation (13) follows from Inequalities 15 and 17.

The proof of Equation (14) is analogous to the one of Equation (13). □

Finally, we can present the main result of this section.

**Corollary 5.7.** For a tree $T$, we can find BOMD($T$), WOMD($T$), BOMD$^*(T)$ and WOMD$^*(T)$ in linear time. Moreover, an orientation attaining each of these values can also be retrieved in linear time.

*Proof.* Theorem 5.2 states that we can find BOMD($T$), WOMD($T$), BOMD$^*(T)$ and WOMD$^*(T)$ by computing the subproblems $B_X(v, i)$ and $W_X(v, i)$. For each $X \subseteq \mathcal{P}$ and each $v \in V(T)$, we have a total of $d(v) + 1$ subproblems, one for each child of $v$ and one for $v$, representing the pair $(v, 0)$. This gives a total of $256(|V(T)| + |E(T)|)$ subproblems. Theorem 5.5 also tells us that $A(X)$ can be computed in constant time. Indeed, we just need to run through all of the triples $(X_1, X_2, o) \in 2^P \times 2^P \times \{\textbf{in}, \textbf{out}\}$ and, for each one, compute in constant time $f(X_1, X_2, o)$. Therefore, each subproblem can be computed in constant time using Theorem 5.6 due to the fact that $|A(X)| \leq 2^{17}$ for any $X \subseteq \mathcal{P}$.

As for the retrieval of an orientation attaining the desired value, this can be done with a search starting at the entry of the root $r$ that gives the searched value as follows. For this, we can assume that when Lemma 5.6 is applied, entry $X$ keeps track of which triple $(X_1, X_2, o)$ originated it. Let $D$ denote the orientation being constructed. Let $\{v_1, \dots, v_d\}$ be the children of vertex $r$, and $X$ be the entry in the table of $T_{r,d}$ containing the desired value (either of BOMD($T$), WOMD($T$), BOMD$^*(T)$ and WOMD$^*(T)$). Let $(X_1, X_2, o)$ be the triple that gives the value related to $X$. Add $rv_d$ to $D$ if $o = \textbf{out}$; otherwise, add $v_d r$. Repeat the process to entry $X_1$ in $T_{r,d-1}$ and $X_2$ in $T_{v_d}$.

**Remark 5.8.** For sake of clarity, we presented an algorithm which runs in linear time, but with a huge multiplicative constant. Indeed the algorithm considers $256(|V(T)| + |E(T)|)$ subproblems. Moreover, for each subproblem, it runs through all triples in $\mathcal{P} \times \mathcal{P} \times \{\textbf{in}, \textbf{out}\}$ for a total of $2^{17} = 131$ 072 triples.

However, the constant in the running time of the algorithm can be easily improved because we only need to consider subproblems related to a subset $\mathcal{V} \subseteq 2^P$, and only runs through triples in $\mathcal{V} \times \mathcal{V} \times \{\textbf{in}, \textbf{out}\}$. More precisely,

**Lemma 5.9.** If an orientation of $T_{v,i}$ agrees with $X \subseteq \mathcal{P}$, then $X$ has the following properties:

* if $X$ contains $\mathbf{r}$, then it also contains $\mathbf{s}$;

* $X$ does not intersect both $\{\mathbf{s}, \mathbf{r}\}$ and $\{\mathbf{u}, \overleftarrow{\mathbf{a}}, \overrightarrow{\mathbf{a}}\}$; and

* $X$ does not contain $\{\overleftarrow{\mathbf{a}}, \overrightarrow{\mathbf{a}}\}$ or $\{\overleftarrow{\mathbf{b}}, \overrightarrow{\mathbf{b}}\}$.

*Proof.* Note that if $X$ contains $\mathbf{r}$, then $v$ is a source and it also satisfies $\mathbf{s}$. Furthermore, if $X$ contains $\mathbf{r}$ or $\mathbf{s}$, then $v$ is a source vertex, while if $X$ contains $\mathbf{u}, \overleftarrow{\mathbf{a}}$ or $\overrightarrow{\mathbf{a}}$, then $v$ is not a source vertex. Therefore, $X$ cannot intersect both $\{\mathbf{s}, \mathbf{r}\}$ and $\{\mathbf{u}, \overleftarrow{\mathbf{a}}, \overrightarrow{\mathbf{a}}\}$.
If $\vec{a} \in X$, then there are $b, c \in V(T_{v,i})$ such that $v \neq c$ and $N^-(v) = N^-(c) = \{b\}$. If $b$ is a source vertex, then $v$ and $c$ are distinct 1-witnesses for $b$ and, thus, $\overleftarrow{a} \notin X$.

Now, for the sake of a contradiction, suppose that $\{\overleftarrow{\mathbf{b}}, \vec{\mathbf{b}}\} \subseteq X$. From $\overleftarrow{\mathbf{b}}$, there are $s, a \in V(T_{v,i})$ such that $N^-(a) = \{s, v\}$, and from $\vec{\mathbf{b}}$, there is $c \in V(T_{v,i})$ such that $N^-(c) = \{v\}$. We have that $a \neq c$ since they have different in-degrees, so $a, v, c$ is a 2-witness for $s$ and this is valid for any choice of vertices $s, a \in V(T_{v,i})$. Therefore, we get a contradiction as $\overleftarrow{\mathbf{b}}$ requires $s$ to be a removable source. $\square$

Therefore, it is sufficient to consider $\mathcal{V}$ the set of subsets of $\mathcal{P}$ that satisfy these properties. This set is of size 48. It contains the 24 sets below and the 24 sets obtained from those by adding $\mathbf{r}^*$.

$$ \emptyset, \{\mathbf{s}\}, \{\mathbf{u}\}, \{\overleftarrow{\mathbf{b}}\}, \{\vec{\mathbf{b}}\}, \{\overleftarrow{\mathbf{a}}\}, \{\vec{\mathbf{a}}\}, \{\mathbf{s}, \mathbf{r}\}, \{\mathbf{s}, \overleftarrow{\mathbf{b}}\}, \{\mathbf{s}, \vec{\mathbf{b}}\}, \{\mathbf{u}, \overleftarrow{\mathbf{a}}\}, \{\mathbf{u}, \vec{\mathbf{a}}\}, \{\mathbf{u}, \overleftarrow{\mathbf{b}}\}, \{\mathbf{u}, \vec{\mathbf{b}}\}, \{\overleftarrow{\mathbf{a}}, \overleftarrow{\mathbf{b}}\}, \\ \{\overleftarrow{\mathbf{a}}, \vec{\mathbf{b}}\}, \{\vec{\mathbf{a}}, \overleftarrow{\mathbf{b}}\}, \{\vec{\mathbf{a}}, \vec{\mathbf{b}}\}, \{\mathbf{s}, \mathbf{r}, \overleftarrow{\mathbf{b}}\}, \{\mathbf{s}, \mathbf{r}, \vec{\mathbf{b}}\}, \{\mathbf{u}, \overleftarrow{\mathbf{a}}, \overleftarrow{\mathbf{b}}\}, \{\mathbf{u}, \overleftarrow{\mathbf{a}}, \vec{\mathbf{b}}\}, \{\mathbf{u}, \vec{\mathbf{a}}, \overleftarrow{\mathbf{b}}\} \text{ and } \{\mathbf{u}, \vec{\mathbf{a}}, \vec{\mathbf{b}}\}. $$

Doing so, the algorithm only considers $48(|V(T)|+|E(T)|)$ subproblems (instead of $256(|V(T)|+|E(T)|)$) and each of these subproblems requires the computation of 4 608 triples (instead of 131 072).

Note that the number of subproblems and triples can be further reduced, by analysing more carefully the dependencies between subsets of $\mathcal{P}$.

**Remark 5.10.** For sake of brevity, we presented an algorithm that computes BOMD($T$), WOMD($T$), BOMD$^*(T)$ and WOMD$^*(T)$ at the same time. However, one can easily design a simpler algorithm that computes only BOMD$^*(T)$ and WOMD$^*(T)$ as the properties of $\mathcal{P}$ are mainly required to determine whether there is a removable source or not.

Furthermore, as WOMD$^*(T) = \alpha(T)$, it can be computed in linear time using the standard dynamic programming algorithm finding a maximum stable set in a tree. A corresponding orientation can then be found by orienting all arcs away from this stable set as shown in the proof of Proposition 4.1.

## 5.1 Proof of Theorem 5.5

The remainder of this section is devoted to the proof of Theorem 5.5. We break it down into a collection of lemmas that provide necessary and sufficient conditions which can be checked in constant time to characterise when an $(X_1, X_2, o)$-orientation that agrees with $X$ satisfies $x \in X$, for each property $x \in \mathcal{P}$.

In each of the lemmas, we consider $X_1, X_2, X \subseteq \mathcal{P}$, and assume that there exists an $(X_1, X_2, o)$-orientation $D$ of $T_{v,i}$ that agrees with $X$. We also denote by $D_1$ and $D_2$ the subdigraphs of $D$ induced by $V(T_{v,i-1})$ and $V(T_{v,i})$, respectively.

**Lemma 5.11.** $s \in X$ if, and only if, $s \in X_1$ and $o = \text{out}$.

*Proof.* If $s \in X$, then $v$ is a source in $D$ and then it must be a source in $T_{v,i-1}$ and $vv_i \in A(D)$, i.e. $o = \text{out}$. Reciprocally, if $s \in X_1$, then $v$ is a source in $T_{v,i-1}$, and if, in addition, $o = \text{out}$, then $v$ is a source in $D$. Hence $s \in X$. $\square$

**Lemma 5.12.** $\mathbf{r} \in X$ if, and only if, $\mathbf{r} \in X_1, \{\mathbf{s}, \vec{\mathbf{a}}\} \cap X_2 = \emptyset$, and $o = \text{out}$.

*Proof.* To prove necessity, suppose that $\mathbf{r} \in X$, which means that $v$ is a removable source. This implies that $o = \text{out}$ and, since there is no 1-witness or 2-witness of $v$ in $D$, that remains true in $D_1$, so $\mathbf{r} \in X_1$. Furthermore, if $\mathbf{s} \in X_2$, then $v_i$ is a 1-witness for $v$, and if $\vec{\mathbf{a}} \in X_2$, then $v_i$ is part of a 2-witness for $v$ in $D_2$. Neither can occur since $v$ is removable, so $\{\mathbf{s}, \vec{\mathbf{a}}\} \cap X_2 = \emptyset$.

To prove sufficiency, assume that $\mathbf{r} \in X_1, o = \text{out}$ and $\{\mathbf{s}, \vec{\mathbf{a}}\} \cap X_2 = \emptyset$. Let us show that $v$ is a removable source in $D$, that is a source without witnesses. Since $\mathbf{r} \in X_1$ and $o = \text{out}$, vertex $v$ is a source in $D_1$ and $vv_i \in A(D)$. Thus $v$ is a source in $D$. Furthermore, $\mathbf{r} \in X_1$ also implies that there are no witnesses for $v$ in $D_1$. Now, as $\mathbf{s} \notin X_2, v_i$ is not a source in $D_2$ so $d_{\overleftarrow{D}}(v_i) \ge 2$, so $v_i$ is not a 1-witness of $v$. Moreover $\vec{\mathbf{a}} \notin X_2$ implies that there is no 2-witness of $v$ using $v_i$. Hence $v$ has no witnesses, and thus it is a removable source, that is $\mathbf{r} \in X$. $\square$
**Lemma 5.13.** $\mathbf{u} \in X$ if, and only if, one of the following occurs:

(i) $(\mathbf{u} \in X_1 \text{ and } o = \text{out})$;

(ii) $(\mathbf{r} \in X_1 \text{ and } \overrightarrow{\mathbf{b}} \in X_2 \text{ and } o = \text{in})$;

(iii) $(\overrightarrow{\mathbf{a}} \in X_1 \text{ and } \mathbf{r} \in X_2 \text{ and } o = \text{in})$;

(iv) $(\overleftarrow{\mathbf{a}} \in X_1 \text{ and } \overrightarrow{\mathbf{b}} \in X_2 \text{ and } o = \text{in})$.

*Proof.* First assume that $\mathbf{u} \in X$. Let $(a, b, c)$ be a 2-witness of some source $s$ in $D$ such that either $v = c$ and $(a, b, c)$ is the unique witness for $s$ in $D$, or $v = a$ and all witnesses for $s$ in $D$ are of the form $(a, b, c')$ for some vertex $c'$. We analyse the cases:

* If $o = \text{out}$, note that $v$ has out-degree 0 in $D[(a, b, c)]$. Therefore, $\{s, a, b, c\} \subseteq V(T_{v,i-1})$, and $(a, b, c)$ is a 2-witness for $s$ in $D_1$. Furthermore, for the same reason, no witness of $s$ contains $v_i$. Hence the witnesses of $s$ in $D$ are those in $D_1$. Hence, $\mathbf{u} \in X_1$ and (i) holds.

* If $o = \text{in}$, then we distinguish two cases:

$v = c$: In this case $N_D^-(v) = \{v_i\}$. Thus $v$ is a source in $T_{v,i-1}$, i.e. $s \in X_1$. Moreover $b = v_i$ and $\{a, s\} \subseteq V(T_{v_i})$. Note also that $s$ must be removable in $D_2$ since otherwise there would be more witnesses for $s$ in $D$. Hence $\overleftarrow{\mathbf{b}} \in X_2$ and (ii) holds.

$v = a$: In that $N_D^-(v) = \{s, b\}$. We distinguish two subcases depending on which vertex of $\{s, b\}$ is $v_i$.

$v_i = s$: In this case, $b \in V(T_{v,i-1})$. Observe that $v_i$ cannot have a 2-witness in $D_2$ for otherwise it would also be a 2-witness in $D_2$, which would contradict the fact that such a witness is of the form $(v = a, b, c')$ for some vertex $c'$. Similarly $v_i$ cannot have a 1-witness in $D_2$ since it would be also a 1-witness for $s$ in $D$. Therefore $v_i$ has no witnesses in $D_2$, which means that $v_i$ is a removable source in $D_2$ and $\mathbf{r} \in X_2$. Moreover, $N_{D_1}^-(v) = N_{D_1}^-(c) = \{b\}$, and hence $\overrightarrow{\mathbf{a}} \in X_1$. Hence (iii) holds.

$v_i = b$: In that case $s \in V(T_{v,i-1})$. As $N_{D_2}^-(c) = \{v_i\}$, we get that $\overrightarrow{\mathbf{b}} \in X_2$. Moreover $v$ is a 1-witness for $s$ in $D_1$ because $N_{D_1}^-(v) = \{s\}$. Finally, $s$ cannot have another witness in $D_1$ because all witnesses for $s$ in $D$ are of the form $(a, b = v_i, c')$ for some vertex $c' \in N_{D_2}^+(v_i)$. It follows that $\overleftarrow{\mathbf{a}} \in X_1$ and so (iv) holds.

Reciprocally, assume that one of (i), (ii), (iii), or (iv) holds. We analyse each case separately.

(i) $\mathbf{u} \in X_1$ and $o = \text{out}$. Let $(a, b, c)$ be a 2-witness of some source $s$ in $D_1$ such that either $v = c$ and $(a, b, c)$ is the unique witness for $s$ in $D_1$, or $v = a$ and all 2-witnesses for $s$ in $D_1$ are of the form $(a, b, c')$ for some vertex $c' \in V(T_{v,i-1})$. Clearly, $(a, b, c)$ remains a 2-witness for $s$ in $D$ and because $o = \text{out}$, no other 2-witness with a form different from $(a, b, c')$ can be added for $s$ in $D$. Hence, $\mathbf{u} \in X$.

(ii) $\mathbf{r} \in X_1$, $\overleftarrow{\mathbf{b}} \in X_2$, and $o = \text{in}$. Since $\overleftarrow{\mathbf{b}} \in X_2$, there are $s, a \in V(T_{v,i})$ such that $N_{D_2}^-(a) = \{s, v_i\}$ and $s$ is a removable source in $D_2$. Since $\mathbf{r} \in X_1$, $N_D^-(v) = \{v_i\}$. Hence $(a, v_i, v)$ is a witness for $s$ in $D$. Moreover, it is the unique one, because $s$ is removable in $D_2$. Therefore $\mathbf{u} \in X$.

(iii) $\overrightarrow{\mathbf{a}} \in X_1$, $\mathbf{r} \in X_2$, and $o = \text{in}$. Since $\overrightarrow{\mathbf{a}} \in X_1$, there are $b, c \in V(T_{v,i-1})$ such that $v \neq c$ and $N_{D_1}^-(v) = N_{D_1}^-(c) = \{b\}$. Since $\mathbf{r} \in X_2$ and $v_i v \in A(D)$, we get that $v_i$ is a source in $D$ and $(a = v, b, c)$ is a 2-witness for $v_i$ in $D$. Moreover, because $v_i$ is a removable source in $D_2$, vertex $v_i$ has no witnesses in $T_{v_i}$. Hence, $(a = v, b, c)$ is a 2-witness for $v_i$ in $D$ and all witnesses for $v_i$ in $D$ are of the form $(a = v, b, c')$ for any $c' \in V(T_{v,i-1})$ with $N_D^-(c) = \{b\}$. Hence $\mathbf{u} \in X$.

(iv) $\overleftarrow{\mathbf{a}} \in X_1$, $\overrightarrow{\mathbf{b}} \in X_2$, and $o = \text{in}$. Since $\overleftarrow{\mathbf{a}} \in X_1$, in $D_1$, there is a source $s$ such that $v$ is a 1-witness for $s$ and is also the unique witness for $s$ in $D_1$. Let $C = \{c \in V(T_{v_i}) | N_{D_2}^-(c) = \{v_i\}\}$. Since $\overrightarrow{\mathbf{b}} \in X_2$, we have $C \neq \emptyset$. Then, for all $c \in C$, we have that $(a = v, b = v_i, c)$ is a 2-witness for $s$ in $D$ and thus $\mathbf{u} \in X$. $\square$
**Lemma 5.14.** $\overleftarrow{\mathbf{a}} \in X$ if, and only if, $(\overleftarrow{\mathbf{a}} \in X_1 \text{ and } o = \text{out})$ or $(\mathbf{s} \in X_1, \mathbf{r} \in X_2 \text{ and } o = \text{in})$.

*Proof.* Suppose first that $\overleftarrow{\mathbf{a}} \in X$. By definition, there exists a source $s \in V(T_{v,i})$ for which $v$ is a 1-witness and also the unique witness for $v$ in $D$. If $vv_i \in A(D)$, then $s \neq v_i$, in which case $s \in V(T_{v,i-1})$ and $\overleftarrow{\mathbf{a}} \in X_1$. If $v_iv \in A(D)$, then $s = v_i$ since $N_D^-(v) = \{s\}$. Hence $v$ is a source in $D_1$, that is $\mathbf{s} \in X_1$. Moreover, because $v$ is the unique witness of $v_i = s$, this vertex has no witness in $D_2$, i.e. $\mathbf{r} \in X_2$.

Let us now prove the reciprocal.

Assume first that $\overleftarrow{\mathbf{a}} \in X_1$ and $o = \text{out}$. Then, in $D_1$, $v$ is a 1-witness and is the unique 1-witness for some source in $T_{v,i-1}$. As $vv_i \in A(D)$, the same holds in $D$, so $\overleftarrow{\mathbf{a}} \in X$.

Assume now that $\mathbf{s} \in X_1, \mathbf{r} \in X_2$ and $o = \text{in}$. Then $v$ is a source in $D_1$ and $v_iv \in A(D)$, so $N_D^-(v) = \{v_i\}$. Moreover, $v_i$ is a removable source in $D_2$, so it is still a source in $D$. Moreover, $v$ is a 1-witness for $v_i$, and it is unique as $v_i$ has no witness in $D_2$ since it is removable in $D_2$. Hence $\overleftarrow{\mathbf{a}} \in X$. $\square$

**Lemma 5.15.** $\overrightarrow{\mathbf{a}} \in X$ if, and only if, $(\overrightarrow{\mathbf{a}} \in X_1 \text{ and } o = \text{out})$ or $(\mathbf{s} \in X_1, \overrightarrow{\mathbf{b}} \in X_2 \text{ and } o = \text{in})$.

*Proof.* Suppose first that $\overrightarrow{\mathbf{a}} \in X$. There exist $b, c \in V(T_{v,i})$ such that $v \neq c$ and $N_D^-(v) = N_D^-(c) = \{b\}$. If $vv_i \in A(D)$, then $b \neq v_i$, so $\{b, c\} \subseteq V(T_{v,i-1})$ and $\overrightarrow{\mathbf{a}} \in X_1$. If $v_iv \in A(D)$, then $b = v_i$, so $\{b, c\} \subseteq V(T_{v_i})$, and $\overrightarrow{\mathbf{b}} \in X_2$ since $N_D^-(c) = \{b\}$. Moreover, since $N_D^-(v) = \{b\}$, vertex $v$ is a source in $D_1$, i.e. $\mathbf{s} \in X_1$.

Let us now prove the reciprocal.

Assume first that $\overrightarrow{\mathbf{a}} \in X_1$ and $o = \text{out}$. There exist $b, c$ in $V(T_{v,i-1})$ such that $v \neq c$ and $N_{D_1}^-(v) = N_{D_1}^-(c) = \{b\}$. But $N_D^-(c) = N_{D_1}^-(c)$ and $N_D^-(v) = N_{D_1}^-(v)$ because since $vv_i \in A(D)$. Hence $N_D^-(v) = N_D^-(c) = \{b\}$, so $\overrightarrow{\mathbf{a}} \in X$.

Assume now that $\mathbf{s} \in X_1$, $o = \text{in}$ and $\overrightarrow{\mathbf{b}} \in X_2$. Then, there exists $c \in V(T_{v_i})$ such that $N_D^-(c) = \{v_i\}$. But because $v$ is a source in $D_1$, we have $N_D^-(v) = \{v_i\}$, and so $\overrightarrow{\mathbf{a}} \in X$. $\square$

**Lemma 5.16.** $\overleftarrow{\mathbf{b}} \in X$ if, and only if, $(o = \text{in}$ and $\overleftarrow{\mathbf{b}} \in X_1)$, or $(o = \text{out}, \overleftarrow{\mathbf{b}} \in X_1 \text{ and } \mathbf{s} \notin X_2)$, or $(o = \text{out}, \overrightarrow{\mathbf{b}} \notin X_1 \text{ and } \overleftarrow{\mathbf{a}} \in X_2)$.

*Proof.* Suppose first that $\overleftarrow{\mathbf{b}} \in X$. There exist $s, a \in V(T_{v,i})$ such that $N_D^-(a) = \{v, s\}$ and $s$ is a removable source in $D$.

If $v_iv \in A(D)$, i.e. $o = \text{in}$, then $\{v, s, a\} \subseteq V(T_{v,i-1})$, and $\overleftarrow{\mathbf{b}} \in X_1$ trivially holds.

Suppose now $o = \text{out}$, that is $vv_i \in A(D)$. If $\overleftarrow{\mathbf{b}} \in X_1$, then $\mathbf{s} \notin X_2$ as otherwise $(a, v, v_i)$ would be a 2-witness for $s$ in $D$, a contradiction to $s$ being removable. Suppose now that $\overleftarrow{\mathbf{b}} \notin X_1$. Then $s, a \in V(T_{v_i})$. Thus $a = v_i$ and $N_{D_2}^-(v_i) = \{s\}$, in which case $v_i$ is a 1-witness for $s$ in $D_2$. But since $s$ is removable in $D$, it means that $v_i$ is the unique witness for $s$ in $D_2$; hence $\overleftarrow{\mathbf{a}} \in X_2$.

Let us now prove the reciprocal.

First suppose that $\overleftarrow{\mathbf{b}} \in X_1$. There exist $s, a \in V(T_{v,i-1})$ such that $N_{D_1}^-(a) = \{v, s\}$ and $s$ is a removable source in $D_1$. If $v_iv \in A(D)$, then $N_D^-(a) = N_{D_1}^-(a) = \{v, s\}$ and $s$ is a removable source in $D$, so $\overleftarrow{\mathbf{b}} \in X$. The same holds if $vv_i \in A(D)$ and $d_D^-(v_i) \ge 2$ (i.e. $\mathbf{s} \notin X_2$).

Assume now that $(o = \text{out}, \overrightarrow{\mathbf{b}} \notin X_1 \text{ and } \overleftarrow{\mathbf{a}} \in X_2)$. By the definition of $\overleftarrow{\mathbf{a}}$, there exists a source $s$ in $D_2$ such that $v_i$ is a 1-witness for $s$ in $D_2$, and is also the unique witness for $s$ in $D_2$. Because $N_D^-(v_i) = \{s, v\}$, vertex $v_i$ is not a 1-witness of $s$ in $D$, and since $\overrightarrow{\mathbf{b}} \notin X_1$, the source $s$ has no 2-witnesses in $D$. Thus, by the proof of Corollary 2.15, $s$ is a removable source in $D$. Hence $\overleftarrow{\mathbf{b}} \in X$ since $N_D^-(v_i) = \{s, v\}$. $\square$

**Lemma 5.17.** $\overrightarrow{\mathbf{b}} \in X$ if, and only if, $\overleftarrow{\mathbf{b}} \in X_1$ or $(\mathbf{s} \in X_2 \text{ and } o = \text{out})$.

*Proof.* Suppose first that $\overrightarrow{\mathbf{b}} \in X$. There exists $c \in V(T_{v,i})$ be such that $N_D^-(c) = \{v\}$. If $c \in V(T_{v,i-1})$, then $\overleftarrow{\mathbf{b}} \in X_1$. If $c \in V(T_{v_i})$, then necessarily $c = v_i$ and $N_D^-(v_i) = \{v\}$. So $vv_i \in A(D)$ and $v_i$ is a source in $D_2$, that is $o = \text{out}$ and $\mathbf{s} \in X_2$.
Let us prove the reciprocal. If $\overrightarrow{\mathbf{b}} \in X_1$, then there is $c \in V(T_{v,i-1})$ such that $N_{\overline{D}_1}(c) = \{v\}$. Note that $N_{\overline{D}}(c) = N_{\overline{D}_1}(c)$, so $\overrightarrow{\mathbf{b}} \in X$. If $o = \mathbf{out}$ and $\mathbf{s} \in X_2$, then $vv_i \in A(D)$ and $v_i$ has no in-neighbour in $D_2$. Hence $N_{\overline{D}}(v_i) = \{v\}$, that is $\overrightarrow{\mathbf{b}} \in X$. $\square$

**Lemma 5.18.** $\mathbf{r}^* \in X$ if, and only if, one of the following occurs:

(i) $(\mathbf{r}^* \in X_1 \cup X_2)$;

(ii) $(\overleftarrow{\mathbf{a}} \in X_1 \text{ and } \overrightarrow{\mathbf{b}} \notin X_2 \text{ and } o = \mathbf{in})$;

(iii) $(\mathbf{u} \in X_1 \text{ and } o = \mathbf{in})$;

(iv) $(\mathbf{u} \in X_2 \text{ and } o = \mathbf{out})$;

(v) $(\mathbf{r} \in X_2 \text{ and } \{\mathbf{s}, \overrightarrow{\mathbf{a}}\} \cap X_1 = \emptyset \text{ and } o = \mathbf{in})$;

(vi) $(\overleftarrow{\mathbf{b}} \in X_2 \text{ and } o = \mathbf{out})$;

(vii) $(\overleftarrow{\mathbf{b}} \in X_2 \text{ and } o = \mathbf{in} \text{ and } \mathbf{s} \notin X_1)$.

*Proof.* Suppose first that $\mathbf{r}^* \in X$. Then there exists an $\mathbf{r}^*$-source $s \in V(T_{v,i})$.

If $s \in V(D_1)$ then let $\alpha = 1$, $w = v$ and $\overline{w} = v_i$, and if $s \in V(D_2)$ then let $\alpha = 2$, $w = v_i$, and $\overline{w} = v$. Note that $s$ is a source in $D_\alpha$.

If $\mathbf{r}^* \in X_1 \cup X_2$, then (i) holds, so we may assume $\mathbf{r}^* \notin X_1 \cup X_2$. We distinguish two cases depending on the orientation of the edge between $w$ and $\overline{w}$.

* $\overline{w}w \in A(D)$. In this case $s \neq w$.

Assume first that $s$ is a removable source in $D_\alpha$. Since $s \neq w$ and $\mathbf{r}^* \notin X_\alpha$, necessarily $\overleftarrow{\mathbf{b}} \in X_\alpha$. Thus there exists $a \in V(D_\alpha)$ such that $N^-(a) = \{s, w\}$. Now $N_{\overline{D}_\alpha}^-(a) = N_{\overline{D}}^-(a)$, so $w \neq v$ for otherwise $s$ would be a $\overleftarrow{\mathbf{b}}$-source in $D$. Therefore $w = v_i$ so $\alpha = 2$ and $\overline{w}w = vv_i \in A(D)$, i.e. $o = \mathbf{out}$. Hence (vi) holds.

Assume now that $s$ is not removable in $D_\alpha$. By Corollary 2.15, $s$ must have a witness in $D_\alpha$. Since this witness is not a witness in $D$, the vertex $w$ is part of every witness for $s$ in $D_\alpha$. First suppose that $w$ is a 1-witness for $s$ in $D_\alpha$. Observe that $w$ cannot be simultaneously contained in a 2-witness for $s$ in $D_\alpha$, and since $w$ is contained in every witness for $s$ in $D_\alpha$, we get that $w$ is the only witness, in which case $\overleftarrow{\mathbf{a}} \in X_\alpha$. Also, because $s$ has no 2-witness in $D$, we must have $\overrightarrow{\mathbf{b}} \notin X_{2-\alpha}$. Finally, note that if $w = v_i$, then $N_{\overline{D}}(v_i) = \{v, s\}$, and $s$ would be a $\overleftarrow{\mathbf{b}}$-source in $D$, a contradiction. Therefore $w = v$ and thus $\alpha = 1$ and (ii) holds.

Now, suppose that $(a, b, c)$ is a 2-witness for $s$ in $D_\alpha$. As it is not a 2-witness for $s$ is $D$, necessarily $w \in \{a, c\}$. If $w = c$, then note that $(a, b, c)$ is the only witness for $s$ in $D_\alpha$ as any other witness would be also a witness in $D$; thus we get $\mathbf{u} \in X_\alpha$ and (iii) or (iv) holds. If $w = a$, then, as every witness must contain $w$ and $N_{\overline{D}_\alpha}^-(w) = \{s, b\}$, every witness must be of the form $(a = w, b, c')$. Again $\mathbf{u} \in X_\alpha$ and (iii) or (iv) holds.

* $\overline{w}\overline{w} \in A(D)$. Note that, in this case, any witness for $s$ in $D_\alpha$ is also a witness for $s$ in $D$. Therefore $s$ must be removable in $D_\alpha$.

First suppose $s = w$. Because $s$ is not an $\mathbf{r}$-source, $s \neq v$, so $s = w = v_i$ and $\alpha = 2$. Thus $\mathbf{r} \in X_2$. Furthermore, since $s$ has no witnesses in $D$, we get that neither $\mathbf{s}$ nor $\overrightarrow{\mathbf{a}}$ can be in $X_1$ as otherwise $s$ would have either a 1-witness or a 2-witness in $D$, respectively. Hence (v) holds.

Finally, suppose $s \neq w$. Since $s$ is not an $\mathbf{r}^*$-source in $D_\alpha$ (i.e. $\mathbf{r}^* \notin X_\alpha$), $s$ must be a $\overleftarrow{\mathbf{b}}$-source in $D_\alpha$, i.e. $\overleftarrow{\mathbf{b}} \in X_\alpha$. Thus there exists $a \in V(D_\alpha)$ such that $N_{\overline{D}_\alpha}^-(a) = \{w, s\}$. Note that $w = v_i$ and $\alpha = 2$ for otherwise $s$ would be a $\overleftarrow{\mathbf{b}}$-source in $D$. Therefore $v_i v \in A(D)$, i.e. $o = \mathbf{in}$. In addition, $s$ is not a source in $D_2$ for otherwise $(a, v_i, v)$ would be a 2-witness for $s$ in $D$. Hence $\mathbf{s} \notin X_1$ and (vii) holds.
Let us now prove the reciprocal. We analyse the different cases.

(i) **r**\* ∈ X₁ ∪ X₂: There exists an **r**\*-source s in Dⱼ, for some j ∈ {1, 2}. Since it is not an **r**-source, s ∉ {v, vᵢ}.

We first argue that s is removable in D. Assume first that s has a 1-witness in D. As it is not a 1-witness in Dⱼ, necessarily s ∈ {v, vᵢ}, a contradiction. Suppose now that s has a 2-witness (a, b, c) in D. Since it is not a 2-witness in Dⱼ, {a, b, c} must contain v and vᵢ and the arc joining them. If b = v and c = vᵢ (resp. b = vᵢ and c = v), then s is $\overleftarrow{\mathbf{b}}$-source in D₁ = Dⱼ (resp. D₂ = Dⱼ), a contradiction. If a = v and b = vᵢ (resp. a = vᵢ and b = v), then v is a 1-witness for s in D₁ = Dⱼ (resp. D₂ = Dⱼ), a contradiction.

Let us now prove that s is an **r**\*-source in D. Recall that s ≠ v and so s is not an **r**-source. Suppose for a contradiction that s is a $\overleftarrow{\mathbf{b}}$-source. Then there is a $a \in V(D)$ such that $N_D^-(a) = \{s, v\}$. If $a \in V(D_1)$, then $N_{D_1}^-(a) = N_D^-(a) = \{s, v\}$, so s is a $\overleftarrow{\mathbf{b}}$-source in D₁, a contradiction to s being an **r**\*-source s in D₁. If $a \notin V(D_1)$, then $a = v_i$, and $v_i$ is a 1-witness for s in D₂, a contradiction. Hence s is an **r**\*-source in D, i.e. $\mathbf{r}^* \in X$.

(ii) $\overleftarrow{\mathbf{a}} \in X_1, \overrightarrow{\mathbf{b}} \notin X_2$ and $o = \mathbf{in}$: There is a source $s \in V(T_{v,i-1})$ for which v is a 1-witness in D₁, and additionally v is the only witness for s. Because $o = \mathbf{in}$ and $\overrightarrow{\mathbf{b}} \notin X_2$, the source s has no witnesses in D. Moreover because $s \in N_D^-(v)$, one trivially sees that s is neither an **r**-source nor a $\overleftarrow{\mathbf{b}}$-source in D. Hence s is an **r**\*-source in D, i.e. $\mathbf{r}^* \in X$.

(iii) **u** ∈ X₁ and **o** = **in**: Let {a, b, c, s} ⊆ V(T<sub>v,i-1</sub>) be such that s is a source and (a, b, c) is a 2-witness for s in D₁ that satisfies Property **u**.

First suppose that v = c, in which case (a, b, c) is the unique witness for s in D₁. Since $o = \mathbf{in}$, $N_D^-(c) = \{b, v_i\}$, so (a, b, c) is no more a 2-witness for s in D. So s is a removable source in D. In addition, since s is at distance 3 from v, it cannot be an **r**-source or a $\overleftarrow{\mathbf{b}}$-source in D. Hence s is an **r**\*-source in D, so $\mathbf{r}^* \in X$.

Now consider v = a, in which case every witness for s in D₁ is of the form (v, b, c') for some c' ∈ N<sup>+</sup>(b). Since $N_D^-(v) = \{s, b, v_i\}$, we get that s has no witnesses in D, and because s ∈ N<sup>-</sup><sub>D</sub>(v), cannot be an **r**-source or a $\overleftarrow{\mathbf{b}}$-source in D. Hence s is an **r**\*-source in D, so $\mathbf{r}^* \in X$.

(iv) **u** ∈ X₂ and **o** = **out**: Let {a, b, c, s} ⊆ V(T<sub>vᵢ</sub>) be such that s is a source and (a, b, c) is a 2-witness for s in D₂ that satisfies Property **u**. One can verify that, because $d_D^-(v_i) = d_{D_2}^-(v_i) + 1$, s has no witnesses in D. Also either s is at distance 4 from v in T, or $N_D^-(v_i) = \{v, b, s\}$. In both cases, s cannot be an **r**-source or a $\overleftarrow{\mathbf{b}}$-source in D. Hence s is an **r**\*-source in D, so $\mathbf{r}^* \in X$.

(v) **r** ∈ X₂, {s, $\overrightarrow{\mathbf{a}}$} ∩ X₁ = ∅ and $o = \mathbf{in}$: Then $v_i$ is a removable source in D₂. Since $o = \mathbf{in}$, $v_i$ is still a source in D. Since s ∉ X₁, v is not a source in D₁, and so it has in-degree at least 2 in D. Thus v is not a 1-witness of $v_i$ in D and so $v_i$ has no 1-witness in D. Moreover since $\overrightarrow{\mathbf{a}} \notin X_1$, there is no 2-witness for $v_i$ containing v in D, and so there is no 2-witness for $v_i$ in D. Hence, by Corollary 2.15, $v_i$ is removable in D. Finally, since $v_i \in N_D^-(v)$, $v_i$ cannot be an **r**-source or a $\overleftarrow{\mathbf{b}}$-source in D. Hence $v_i$ is an **r**\*-source in D, so $\mathbf{r}^* \in X$.

(vi) $\overleftarrow{\mathbf{b}} \in X_2$ and $o = \mathbf{out}$: There exist $s, a \in V(T_{v_i})$ such that $N_{D_2}^-(a) = \{s, v_i\}$ and s is a removable source in D₂. Since $o = \mathbf{out}$, then s is also removable in D, and because of the distance between v and s in T, s must be an **r**\*-source. Hence $\mathbf{r}^* \in X$.

(vii) $\overleftarrow{\mathbf{b}} \in X_2$ and $o = \mathbf{in}$ and $s \notin X_1$. This implies that $d_D^-(v) > 1$, and so $v_i$ does not have any neighbour c in D such that (a, vᵢ, c) is a 2-witness for s in D. Thus s is removable in D, and because of the distance between v and s in T, s must be an **r**\*-source. Hence $\mathbf{r}^* \in X$. □

Using Lemmas 5.11 to 5.18, it is simple to prove Theorem 5.5.
*Proof of Theorem 5.5.* Let $(X_1, X_2, o) \in 2^P \times 2^P \times \{\text{in, out}\}$ and suppose that an $(X_1, X_2, o)$-orientation of $T_{v,i}$ agrees with $X$. For every $x \in P$, one of the lemmas from Lemmas 5.11 to 5.18 characterises when $x \in X$ as a function that depends only on $X_1, X_2$ and $o$. This implies that $X$ is uniquely defined by $X_1, X_2$ and $o$. Furthermore, since each such characterisation can be computed in constant time, we can compute $f(X_1, X_2, o)$ in constant time. □

# 6 Further research

In this paper, we proved a number of bounds and complexity results about the parameters BOMD, BOMD*, WOMD, and WOMD*, but many questions remain open. We list a few interesting ones.

We proved in Subsection 3.2 that, for a general graph $G$, we have $\text{BOMD}(G) \le \text{BOMD}^*(G) \le \text{pc}(G)$, and that $\text{pc}(G)$ cannot be bounded by a function of $\text{BOMD}(G)$ (or $\text{BOMD}^*(G)$). But it would be interesting to know whether this is the case for some classes of graphs, e.g., for trees.

**Problem 6.1.** For which classes of graphs $\mathcal{F}$ does there exist a function $f_{\mathcal{F}}$ such that $\text{pc}(G) \le f_{\mathcal{F}}(\text{BOMD}(G))$ for every $G \in \mathcal{F}$?

It is known [3] that for a connected graph $G$, there is a spanning tree $T$ of $G$ such that $\text{pc}(T) = \text{pc}(G)$. Does the same hold for BOMD or BOMD*?

**Problem 6.2.** Is it true that for any connected graph $G$, there is a spanning tree $T$ of $G$ such that $\text{BOMD}^*(T) = \text{BOMD}^*(G)$ (resp. $\text{BOMD}(T) = \text{BOMD}(G)$)?

We showed in Theorem 4.10 that there is a (smallest) integer $C_k$ (resp. $C_k^*$) such that if $|V(G)| \ge C_k$ (resp. $|V(G)| \ge C_k^*$), then WOMD($G$) $\ge k$ (resp. WOMD*($G$) $\ge k$). The proof of this theorem establishes $C_k \le R(2k, k+1)$ and $C_k \le R(2k-1, k)$. As $R(p, q) \le \binom{p+q-2}{q-1}$, we get $C_k \le \binom{3k-1}{k}$ and $C_k \le \binom{3k-3}{k-1}$. However these upper bounds are certainly not tight and it would be interesting to determine the values of $C_k$ and $C_k^*$, or at least better bounds on them. This can be rephrased as follows.

**Problem 6.3.** What are the minimum functions $f$ and $f^*$ such that $|V(G)| \le f(\text{WOMD}(G))$ and $|V(G)| \le f^*(\text{WOMD}^*(G))$ for every graph $G$?

Regarding the complexity aspect, we proved that, given a graph $G$, computing $\text{BOMD}(G)$ and $\text{BOMD}^*(G)$ is NP-hard. But can it be approximated? Moreover, we showed that those parameters can be computed in polynomial (and even linear) time for trees. It would be then natural to identify other classes of graphs for which this can also be done. We then have the following questions.

**Problem 6.4.** For which classes of graphs, can we

* compute BOMD (resp. BOMD*) in polynomial time?

* approximate BOMD (resp. BOMD*) in polynomial time?

* decide whether BOMD = BOMD* in polynomial time?

Regarding the complexity of deciding whether $\text{BOMD}(G) \le k$ (and similarly $\text{BOMD}^*(G) \le k$) for a given graph $G$, we have proved in Corollary 3.6 that it is NP-hard for every $k \ge 1$. Looking at our proof, however, it can be noted that this result only holds for $G$ being non-connected. Since we mostly focused on connected graphs throughout this work, it is legitimate to wonder about the following:

**Problem 6.5.** Does Corollary 3.6 hold when restricted to connected graphs $G$?

While, for every $k$, one can decide in constant time (function of $k$) whether $\text{WOMD}(G)$ (resp. $\text{WOMD}^*(G)$) is at most $k$, we do not know the complexity of computing $\text{WOMD}(G)$ (resp. $\text{WOMD}^*(G)$). We proved that this can be done in polynomial (and even linear) time for trees. But what about other classes of graphs? Hence we are left with the analogous questions to those of Problem 6.4.
**Problem 6.6.** For which classes of graphs, can we

• compute WOMD (resp. WOMD*) in polynomial time?

• approximate WOMD (resp. WOMD*) in polynomial time?

• decide whether WOMD = WOMD* in polynomial time?

Finally, recall that there are two kinds of trees $T$ with respect to WOMD: ($\alpha-1$)-trees $T$ for which $WOMD(T) = \alpha(T) - 1$, and $\alpha$-trees $T$ for which $WOMD(T) = \alpha(T)$. In addition, given a tree $T$, one can compute $WOMD(T)$ in linear time. This suggests that there might be a nice characterisation of $\alpha$-trees (and of ($\alpha-1$)-trees at the same time), i.e. a simple description of what the precise structure of $\alpha$-trees is. We did so for stars and paths, but the problem remains open in general.

**Problem 6.7.** Give a nice characterisation of $\alpha$-trees.

# 7 Compliance with Ethical Standards

Disclosure of potential conflicts of interest

## References

[1] Florian Barbero, Lucas Isenmann, and Jocelyn Thiebaut. On the distance identifying set meta-problem and applications to the complexity of identifying problems on graphs. *Algorithmica, Special Issue on Parameterized and Exact Computation, IPEC 2018*, 155(17):2242–2256, 2007.

[2] Julien Bensmail, Fionn Mc Inerney, and Nicolas Nisse. Metric dimension: from graphs to oriented graphs. *Electronic Notes in Theoretical Computer Science*, 346:111–123, 2019. The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019).

[3] F. T. Boesch, S. Chen, and N. A. M. McHugh. On covering the points of a graph with point disjoint paths. In *Graphs and Combinatorics*, number 406 in Lecture Notes in Math, pages 201–212, 1974.

[4] J. A. Bondy and U. S. R. Murty. *Graph Theory with Applications*. Elsevier, New York, 1976.

[5] Nicolas Bousquet, Quentin Deschamps, Tuomo Lehtilä, and Aline Parreau. Locating-dominating sets: From graphs to oriented graphs. *Discrete Mathematics*, 346(1):113124, 2023.

[6] Gary Chartrand, Michael Raines, and Ping Zhang. The directed distance dimension of oriented graphs. *Mathematica Bohemica*, 125(2):155–168, 2000.

[7] Nathann Cohen and Frédéric Havet. On the minimum size of an identifying code over all orientations of a graph. *The Electronic Journal of Combinatorics*, 25:P1.49, 2018.

[8] Josep Diaz, Olli Pottonen, Maria Serna, and Erik Jan [van Leeuwen]. Complexity of metric dimension on planar graphs. *Journal of Computer and System Sciences*, 83(1):132–158, 2017.

[9] Melodie Fehr, Shonda Gosselin, and Ortrud R. Oellermann. The metric dimension of cayley digraphs. *Discrete Mathematics*, 306(1):31–41, 2006.

[10] Min Feng, Min Xu, and Kaishun Wang. On the metric dimension of line graphs. *Discrete Applied Mathematics*, 161(6):802–805, 2013.

[11] Florent Foucaud, Shahrzad Heydarshahi, and Aline Parreau. Domination and location in twin-free digraphs. *Discrete Applied Mathematics*, 284:42–52, 2020.
[12] 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, July 2016.

[13] F. Harary and R.A. Melter. On the metric dimension of a graph. Ars Combinatoria, 2:191 – 195, 1976.

[14] Ruo-Wei Hung and Maw-Shang Chang. Finding a minimum path cover of a distance-hereditary graph in polynomial time. Discrete Applied Mathematics, 155(17):2242 – 2256, 2007.

[15] Antoni Lozano. Symmetry breaking in tournaments. The Electronic Journal of Combinatorics, 20(1):#P69, 2013.

[16] S. Pancahayani and R. Simanjuntak. Directed metric dimension of oriented graphs with cyclic covering. Journal of Combinatorial Mathematics and Combinatorial Computing, 94:15–25, 2015.

[17] Bharati Rajan, Indra Rajasingh, Jude Annie Cynthia, and Paul Manuel. Metric dimension of directed graphs. International Journal of Computer Mathematics, 91(7):1397–1406, 2014.

[18] F.P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, 30:264–286, 1930.

[19] P.J. Slater. Leaves of trees. In Proceeding of the 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing, number XIV in Congressus Numerantium, pages 549–559, 1975.

[20] Craig A. Tovey. A simplified np-complete satisfiability problem. Discrete Applied Mathematics, 8(1):85 – 89, 1984.