# Exploiting Low Scanwidth to Resolve Soft Polytomies

Sebastian Bruchhold, Mathias Weller

► To cite this version:

Sebastian Bruchhold, Mathias Weller. Exploiting Low Scanwidth to Resolve Soft Polytomies. 51st International Conference on Current Trends in Theory and Practice of Computer Science, Feb 2026, Cracovie, Poland. pp.22. hal-05392755

HAL Id: hal-05392755

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

Submitted on 2 Dec 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Exploiting Low Scanwidth to Resolve Soft Polytomies*

Sebastian Bruchhold

0009-0003-7413-4263
Technische Universität Berlin, Germany
bruchhold@math.tu-berlin.de

Mathias Weller

0000-0002-9653-3690
LIGM, CNRS, Univ Gustave Eiffel, F77454 Marne-la-Vallée, France
mathias.weller@cnrs.fr

November 25, 2025

## Abstract

Phylogenetic networks allow modeling reticulate evolution, capturing events such as hybridization and horizontal gene transfer. A fundamental computational problem in this context is the TREE CONTAINMENT problem, which asks whether a given phylogenetic network is compatible with a given phylogenetic tree. However, the classical statement of the problem is not robust to poorly supported branches in biological data, possibly leading to false negatives. In an effort to address this, a relaxed version that accounts for uncertainty, called SOFT TREE CONTAINMENT, has been introduced by Bentert, Malík, and Weller [SWAT'18]. We present an algorithm that solves SOFT TREE CONTAINMENT in $2^{O(\Delta_T \cdot k \cdot \log(k))} \cdot n^{O(1)}$ time, where $k := \text{sw}(\Gamma) + \Delta_N$, with $\Delta_T$ and $\Delta_N$ denoting the maximum out-degrees in the tree and the network, respectively, and $\text{sw}(\Gamma)$ denoting the “scanwidth” [Berry, Scornavacca, and Weller, SOFSEM'20] of a given tree extension of the network, while $n$ is the input size. Our approach leverages the fact that phylogenetic networks encountered in practice often exhibit low scanwidth, making the problem more tractable.

**Keywords:** Phylogenetic networks – Containment relations – Directed width measures

## 1 Introduction

Evolutionary processes are not always represented well by tree-like models, as hybridization, horizontal gene transfer, and other reticulate events often give rise

<footnote>*This paper presents a result from the first author's master's thesis (available at https://doi.org/10.14279/depositonce-21448), which was supervised by the second author. An extended abstract of this paper was accepted at SOFSEM [6].</footnote>
S. Bruchhold and M. Weller

<figure><img src="image_2.png" /><figcaption>Figure 1: (A) Example of a phylogenetic network *N* with one reticulation *r*, and (B) a tree *T*<sub>B</sub> that is (firmly) displayed by *N* ("compatible" with *N*). The tree *T*<sub>C</sub> depicted in (C) is *not* firmly displayed by *N*. However, if the branch *xy* in *T*<sub>C</sub> has low support in the biological data used to construct *T*<sub>C</sub>, it is possible that *T*<sub>C</sub> does not reflect the true evolutionary history between taxa *a*, *b*, and *c*. To avoid such artifacts, branches with low support are usually contracted, resulting in the tree *T*<sub>D</sub>, depicted in (D), which now represents exactly the information that is well supported in the data. The information represented by *T*<sub>D</sub> is now consistent with the information represented by *N*, so we would like to say that *T*<sub>D</sub> is "compatible" with *N*, even though *N* does not firmly display *T*<sub>D</sub>. This motivates the formulation of "soft containment". Indeed, *T*<sub>D</sub> is softly displayed by *N* (since *T*<sub>B</sub> is a binary resolution of *T*<sub>D</sub> that is firmly displayed by *N*).</figcaption></figure>

to more complex structures [7, 23]. To capture these evolutionary relationships,
researchers use phylogenetic networks, which generalize phylogenetic trees by
allowing for "reticulations" that represent non-tree-like events (see the monographs
by Gusfield [14] and Huson, Rupp, and Scornavacca [16]).

A fundamental computational problem arising in this context is the TREE CONTAINMENT problem, which asks whether a given phylogenetic network is “compatible” with (“firmly displays” (see Definition 5)) a given phylogenetic tree, that is, whether the network contains a subdivision of the tree (as a subdigraph respecting leaf-labels). This question is important for reconstruction methods and in the estimation of distances between evolutionary scenarios.

While the TREE CONTAINMENT problem is known to be NP-hard [18, 26], numerous special cases of practical interest have been shown to admit polynomial-time solutions [10, 9, 5, 12, 18, 26, 11, 27, 25]. However, the classical formulation of TREE CONTAINMENT is not robust against branches that are only poorly supported by the biological data. Indeed, to be compatible, all branches must be represented as-is, even when they are weakly supported (see Fig. 1 for an example).

To address this limitation, a relaxed version of TREE CONTAINMENT, called SOFT TREE CONTAINMENT, was proposed by Bentert and Weller [2]. This relaxed framework allows “undoing” contractions of poorly supported branches (contracting low-support branches is a common preprocessing step in network analysis), effectively allowing uncertainty in the form of so-called “soft polytomies”. The corresponding notion of “soft display” (see Definition 5) permits us to resolve each high-degree vertex into a binary tree. Then, the resulting binary resolution of the network ought to firmly display the resulting binary resolution of the tree.

Although both versions of TREE CONTAINMENT remain NP-hard [2], we aim
to solve even large instances in practice. To achieve this, we leverage the fact
that phylogenetic networks occurring in empirical studies are expected to exhibit a
certain degree of tree-likeness, which can be effectively quantified using the recently introduced measure of tree-likeness called “scanwidth” [3]. Our algorithm solves SOFT TREE CONTAINMENT in $2^{O(\Delta_T \cdot k \cdot \log(k))} \cdot n^{O(1)}$ time, where $k := \text{sw}(\Gamma) + \Delta_N$, with $\Delta_T$ and $\Delta_N$ denoting the maximum out-degrees in the tree and the network, respectively, and $\text{sw}(\Gamma)$ denoting the scanwidth of a tree extension that is given as part of the input. The algorithm first makes the network binary through “stretching” and “in-splitting”. This special case (where the network is binary but the tree need not be) is then solved via bottom-up dynamic programming along the given tree extension.

If a claim is marked with a star (⋆), then its proof is given in the appendix.

## 2 Related Work

On a binary network $N$ and a binary tree $T$, the TREE CONTAINMENT problem can be solved in $2^{O(t^2)} \cdot |A(N)|$ time, where $t$ denotes the treewidth of $N$ [24]. This special case of TREE CONTAINMENT is also a special case of SOFT TREE CONTAINMENT, as the notions of “firm” and “soft” display coincide when $N$ and $T$ are both binary [1]. Additionally, SOFT TREE CONTAINMENT is a generalization of the CLUSTER CONTAINMENT problem [1]. Van Iersel, Semple, and Steel [26] show that the latter problem can be solved in polynomial time on binary networks of constant “level”. Note that level-$c$ networks have scanwidth at most $c+1$ [15]. A comparison of the level, scanwidth, and treewidth of real-world phylogenetic networks was conducted by Holtgrefe [15], concluding that treewidth is not much smaller than scanwidth in practice. He further points out that “edge-treewidth” by Magne et al. [19] is the undirected analogue of scanwidth. We also remark that SOFT TREE CONTAINMENT is conceptually similar to MINOR CONTAINMENT: The question of whether a binary network $N$ softly displays a possibly non-binary tree $T$ is equivalent to asking if $T$ can be obtained from a subtree of $N$ through arc contraction (while preserving leaf-labels). In fact, the reduction of general SOFT TREE CONTAINMENT to this special case is the subject of Sect. 4.2. Janssen and Murakami [17] study a similar containment notion based on arc contraction.

## 3 Preliminaries

**Directed Graphs.** A directed graph (or digraph) is an ordered pair $D = (V, A)$ that consists of a non-empty, finite set $V$ of vertices and a set $A \subseteq \{(u, v) \in V^2 \mid u \neq v\}$ of arcs. We also use the notation $V(D) := V$ and $A(D) := A$. The in-neighbors of a vertex $v \in V$ are referred to as its parents (denoted $V_D^-(v)$), and its out-neighbors are referred to as its children (denoted $V_D^+(v)$). The set of incoming arcs of $v$ is denoted $A_D^-(v)$, and the set of outgoing arcs of $v$ is denoted $A_D^+(v)$. The in-degree of $v$ is $\text{deg}_D^-(v) := |V_D^-(v)|$, the out-degree of $v$ is $\text{deg}_D^+(v) := |V_D^+(v)|$, and the degree of $v$ is $\text{deg}_D(v) := \text{deg}_D^-(v) + \text{deg}_D^+(v)$. The maximum out-degree of any vertex in $D$ is denoted $\Delta_D$. If the maximum in-degree and the maximum out-degree of $D$ are both at most 2, then $D$ is called binary. A root of $D$ is a vertex with in-degree 0, and $D$ is called rooted if it has exactly one root (denoted $\text{root}(D)$). A leaf of $D$ is a vertex with out-degree 0, and the set of all leaves of $D$ is denoted $L(D)$. We use $\ge_D \subseteq V^2$ to denote the reachability relation of $D$ (so $u \ge_D v$ means that there is a directed path from $u$ to $v$, possibly having length 0).
The irreflexive kernel of $\ge_D$ is denoted $>_D$. We say that $D$ is weakly connected if the underlying graph of $D$ is connected. The result of removing $v$ from $D$ is denoted $D - v$. We also use the notation $D - U$ when removing a set of vertices $U$ from $D$. If a digraph $D'$ can be obtained by removing vertices and arcs from $D$, then $D'$ is a subdigraph of $D$, denoted $D' \subseteq D$, and $D'$ is called leaf-monotone if, additionally, $L(D') \subseteq L(D)$. The subdigraph induced by a non-empty set $U \subseteq V$ is $D[U] := (U, A \cap (U^2))$. When subdividing an arc $(u, v) \in A$ with a new vertex $w \notin V$, the arc $(u, v)$ is removed from $D$, while the vertex $w$ and the arcs $(u, w)$ and $(w, v)$ are added. The inverse operation, removing $w$ with its incident arcs and adding $(u, v)$, is called suppression of $w$. When contracting $(u, v)$, the parents of $v$, except for $u$, become parents of $u$, and the children of $v$, except for possibly $u$, become children of $u$; the vertex $v$ and its incident arcs are then removed. If $D$ can be obtained from a digraph $D'$ by subdividing arcs, then $D$ is a subdivision of $D'$. The union of two digraphs $D$ and $D'$ is $D \cup D' := (V(D) \cup V(D'), A(D) \cup A(D'))$. A directed acyclic graph (DAG) is a digraph without directed cycles. An out-tree is a rooted DAG in which every vertex has in-degree at most 1.

**Phylogenetic Networks.** A (phylogenetic) network is a rooted DAG whose root has out-degree at least 2 and in which each non-root vertex either has in-degree 1 (and is called a tree vertex) or has out-degree 1 (and is called a reticulation), but not both (see Fig. 1(A)). The root of a network is also considered to be a tree vertex. If a network has no reticulations (that is, it is an out-tree), then it is called a (phylogenetic) tree.

**Scanwidth.** Undoubtedly, one of the most successful concepts in algorithmic graph theory is the notion of treewidth [4]. While some problems in phylogenetics yield efficient algorithms on networks of bounded treewidth, the “undirected nature” of treewidth often makes dynamic programming prohibitively complicated or outright unimplementable [22]. Since phylogenetic networks exhibit a “natural flow of information” along the direction of the arcs, Berry, Scornavacca, and Weller [3] introduced a width measure similar to treewidth, but respecting the direction of the arcs (see [20, 21] for previous efforts to port the notion of treewidth to directed graphs), called “scanwidth”. The idea is to “inscribe” the arcs of the network $N$ into an out-tree $\Gamma$ (called a “tree extension”) on $V(N)$, such that all network arcs are directed away from the root of $\Gamma$ (see Fig. 2(middle) on page 8). This structure allows a bottom-up dynamic-programming approach whose exponential part depends on the size of the set $GW_v(\Gamma)$ of arcs of $N$ that would be cut when slicing just above any vertex $v$ of $\Gamma$.

Formally: Let $D$ be a DAG. A tree extension of $D$ is an out-tree $\Gamma$ on $V(\Gamma) = V(D)$ with $A(D) \subseteq >_{\Gamma}$. For a tree extension $\Gamma$ of $D$, define $GW_t^D(\Gamma) := \{(u, v) \in A(D) \mid u >_{\Gamma} t \ge_{\Gamma} v\}$, for every $t \in V(\Gamma)$, and $sw_D(\Gamma) := \max_{t \in V(\Gamma)} |GW_t^D(\Gamma)|$. The scanwidth of $D$, denoted $sw(D)$, is the minimum $sw_D(\Gamma)$ achievable by any tree extension $\Gamma$ of $D$. If $D$ is rooted, then a canonical tree extension $\Gamma$ of $D$ is such that $D[\{v \in V(D) \mid t \ge_{\Gamma} v\}]$ is weakly connected for all $t \in V(\Gamma)$ [15]; further, $L(\Gamma) = L(D)$ and $\deg_{\Gamma}^+(v) \le \deg_D^+(v)$ for each $v \in V(D)$ [3]. For every tree extension $\Gamma$ of a rooted DAG $D$, a canonical tree extension $\Gamma'$ of $D$ with $sw_D(\Gamma') \le sw_D(\Gamma)$ can be constructed in polynomial time [15].

Assuming that no ambiguity arises, we may omit sub- or superscripts.
# 4 Deciding Soft Tree Containment

In this paper, we develop a parameterized algorithm for SOFT TREE CONTAINMENT. Informally speaking, this problem, first considered by Bentert, Malík, and Weller [1], asks us to decide if a given phylogenetic tree can be embedded in a given phylogenetic network while taking into account uncertainty in the form of soft polytomies (high-degree vertices to be resolved into a binary tree). We build up to its formal definition (Problem 1) in a way that differs slightly from the original. First, we adapt the notion of splitting [2, 17].

**Definition 1.** Let $N$ be any network, let $v \in V(N)$ have out-degree at least 3, and let $u, w \in V_N^+(v)$ be two distinct children of $v$. Then, out-splitting $u$ and $w$ from $v$ produces the network $N' := (V(N) \uplus \{x\}, A)$, where $x \notin V(N)$ is a new vertex and $A := (A(N) \setminus \{(v, u), (v, w)\}) \cup \{(v, x), (x, u), (x, w)\}$.

Exhaustive out-splitting enables us to resolve a high-out-degree tree vertex into a binary out-tree. Its dual for high-in-degree reticulations is defined below.

**Definition 2.** Let $N$ be any network, let $v \in V(N)$ have in-degree at least 3, and let $u, w \in V_N^-(v)$ be two distinct parents of $v$. Then, in-splitting $u$ and $w$ from $v$ produces the network $N' := (V(N) \uplus \{x\}, A)$, where $x \notin V(N)$ is a new vertex and $A := (A(N) \setminus \{(u, v), (w, v)\}) \cup \{(u, x), (w, x), (x, v)\}$.

We now introduce terminology for partially and fully resolved networks. Note that we use a different definition of binary resolution than Bentert, Malík, and Weller [1]. This avoids corner cases violating the intuition behind soft polytomies.

**Definition 3.** Let $N$ be a network. Any network that is obtained from $N$ through exhaustive out-splitting is called a *binary out-resolution* of $N$, and any network that is obtained from $N$ through exhaustive in-splitting is called a *binary in-resolution* of $N$. A *binary resolution* of $N$ is a binary out-resolution of a binary in-resolution of $N$.

When discussing firm and soft display, we want to treat leaves as labeled and all other vertices as unlabeled. This is achieved via the following notion of an isomorphism that agrees with the identity function on all leaves.

**Definition 4.** Let $D$ and $D'$ be DAGs with $L(D) = L(D')$. Let $\iota: V(D) \to V(D')$ be an isomorphism between $D$ and $D'$ with $\iota|_{L(D)} = \text{id}_{L(D)}$, where $\iota|_{L(D)}: L(D) \to V(D')$ denotes the restriction of $\iota$ to $L(D)$. Then, $\iota$ is called *leaf-respecting*.

At this point, we have everything needed to define the central notions of display for this work. Recall that, when taking a leaf-monotone subdigraph, no new leaves can be created.

**Definition 5 ([1]).** Let $N$ be any network and let $T$ be any tree. We say that $N$ *firmly displays* $T$ if there is a leaf-respecting isomorphism between a subdivision of $T$ and a leaf-monotone subdigraph of $N$. We say that $N$ *softly displays* $T$ if there is a binary resolution $N'$ of $N$ as well as a binary resolution $T'$ of $T$ such that $N'$ firmly displays $T'$.

We are now ready to define the problem under consideration. Note that, for technical reasons, we restrict the input slightly more than Bentert, Malík, and Weller [1]; in particular, networks in our sense cannot contain any vertex that has both in-degree and out-degree 1.
**Problem 1 ([1]). SOFT TREE CONTAINMENT**

**Input:** A phylogenetic network $N$ and a phylogenetic tree $T$ with $L(T) \subseteq L(N)$.

**Question:** Does $N$ softly display $T$?

We solve this problem in two steps, corresponding to the next two sections. In Sect. 4.1, we consider the special case where the given network $N$ is binary. In Sect. 4.2, we describe a reduction mapping an arbitrary network to a binary one.

## 4.1 Soft Display by Binary Networks

Van Iersel, Jones, and Weller [25] present a dynamic-programming algorithm that uses tree extensions, thereby leveraging low scanwidth, to solve the TREE CONTAINMENT problem, which asks for firm rather than soft containment. In the following, we adapt their algorithm for our purposes. Although our approach closely follows theirs, access to the unpublished manuscript is not required to understand our presentation. We will, however, highlight both similarities and differences between the two approaches. To start with, we use their definition of a downward-closed subforest and of top arcs in $T$, which are mapped into the “bags” of a given tree extension of $N$.

In contrast to the definition of a phylogenetic network/tree, it will be more convenient to work with $N$ and $T$ whose roots have out-degree 1. This is for technical reasons and does not limit practical applicability. We also assume to be given a canonical tree extension, which might be more problematic in practice, but it allows us to separate the problem of computing/approximating low-scanwidth tree extensions from the problem of deciding soft containment. The following assumption formally introduces these objects, but its scope is restricted to this section and we drop it for Sect. 4.2.

**Assumption 1.** Let $N^*$ be any binary phylogenetic network, and let $T^*$ be an arbitrary phylogenetic tree with $L(T^*) = L(N^*)$. We construct the rooted DAG $N := (V(N^*) \uplus \{\rho_N\}, A(N^*) \cup \{(\rho_N, \text{root}(N^*))\})$ by attaching a new root $\rho_N \notin V(N^*)$, and we construct the out-tree $T := (V(T^*) \uplus \{\rho_T\}, A(T^*) \cup \{(\rho_T, \text{root}(T^*))\})$ by attaching a new root $\rho_T \notin V(T^*)$. Also, let $\Gamma$ be a canonical tree extension of $N$.

We generalize the strict reachability relation defined earlier in order to define reachability between arcs and vertices/arcs. The new reachability relation agrees with the old relation when comparing vertices with vertices.

**Definition 6 ([25]).** Let $D$ be a DAG, $u, v \in V(D)$ vertices, and $(w, x), (y, z) \in A(D)$ arcs. Then, the relation $>_{D} \subseteq (V(D) \uplus A(D))^2$ is defined as follows:

1. We have $u >_{D} v$ if and only if $u \geq_{D} v$ and $u \neq v$,

2. we have $(w, x) >_{D} (y, z)$ if and only if $x \geq_{D} y$,

3. we have $u >_{D} (y, z)$ if and only if $u \geq_{D} y$, and

4. we have $(w, x) >_{D} v$ if and only if $x \geq_{D} v$ (read $v$ is reachable from $(w, x)$).

This relation lets us describe parts of $N$ or $T$ that are “below” a specified set of arcs. In particular, our dynamic-programming table will indicate whether the parts of $T$ that are below an anti-chain of arcs (called “top arcs”) can be embedded below a set of arcs in $N$.
**Definition 7 ([25]).** A downward-closed subforest of $T$ is a subdigraph $F$ of $T$ that does not contain isolated vertices and whose arc set is such that, for all arcs $a \in A(F)$ and $b \in A(T)$, if $a >_T b$, then $b \in A(F)$. An arc $(x, y) \in A(F)$ is called a top arc of $F$ if $\deg_F(x) = 0$. The set $S \subseteq A(F)$ that contains exactly the top arcs of $F$ is called a top-arc set for $L(F)$, and $F$ is called the forest below $S$.

In contrast to firm containment, soft containment allows embedding distinct arcs $(x, y)$ and $(x, z)$ of $T$ as paths in $N$ that may start with the same arcs but separate further down. We call such paths “eventually arc-disjoint”.

**Definition 8.** Two distinct paths $P, Q \subseteq N$ are called eventually arc-disjoint if they have length at least 1 and (a) $P$ and $Q$ are arc-disjoint or (b) $P$ and $Q$ start at the same vertex $v \in V(N)$ and $P - v$ and $Q - v$ are eventually arc-disjoint.

We remark that the union of several pairwise eventually arc-disjoint paths that all start with the same vertex can be used to form an out-tree. To witness soft containment, we associate each vertex of $T$ with such a collection of paths in $N$. Formalizing this intuition, we adapt the notion of a pseudo-embedding [25] to work with eventually arc-disjoint paths. Then, we show that such an embedding of $T$ into $N$ witnesses $N^*$ softly displaying $T^*$.

**Definition 9.** A soft pseudo-embedding of a downward-closed subforest $F$ of $T$ into the rooted DAG $N$ is a function $\phi$ that maps every arc $(x, y) \in A(F)$ to some directed path $\phi(x, y) \subseteq N$ of length at least 1 in $N$ and satisfies the following:

(SPE1) For any two arcs of the form $(x, y), (y, z) \in A(F)$, the last vertex of $\phi(x, y)$ is the first vertex of $\phi(y, z)$.

(SPE2) For all arcs $(x, y), (x', y') \in A(F)$ with $x \neq x'$, the two directed paths $\phi(x, y)$ and $\phi(x', y')$ are arc-disjoint.

(SPE3) For all arcs $(x, y), (x, y') \in A(F)$ with $y \neq y'$, the two directed paths $\phi(x, y)$ and $\phi(x, y')$ are eventually arc-disjoint.

(SPE4) For every arc $(x, \ell) \in A(F)$ with $\ell \in L(T)$, the last vertex of $\phi(x, \ell)$ is $\ell$.

Also, for any arc $(x, y) \in A(F)$, we use $\phi(y)$ to denote the last vertex of $\phi(x, y)$.

**Lemma 1 (★).** The binary network $N^*$ softly displays the tree $T^*$ if and only if there is a soft pseudo-embedding of $T$ into $N$.

Recall that we assume to be given a canonical tree extension $\Gamma$ of $N$ (see Assumption 1). We define $\text{HW}_t(\Gamma) := \{(u, v) \in A(N) \mid u \ge_{\Gamma} t >_{\Gamma} v\}$ for every $t \in V(\Gamma)$. When visualizing scanwidth via scanner lines [3], the set $\text{HW}_t(\Gamma)$ may be thought of as containing the arcs of $N$ cut right below $t \in V(\Gamma)$, whereas $\text{GW}_t(\Gamma)$ contains the arcs cut right above $t$.

In the following, we develop a dynamic-programming algorithm that computes its table entries ("signatures") bottom-up along $\Gamma$. Intuitively, for each $t \in V(\Gamma)$, each top-arc set $S$ in $T$, and each $\psi: S \to \text{GW}_t(\Gamma)$, we set the table entry / signature $[\text{GW}_t(\Gamma), S, \psi]$ to "valid" if the forest below $S$ in $T$ is softly displayed by the network below $\text{GW}_t(\Gamma)$ in such a way that each arc $a \in S$ is embedded in a path starting with $\psi(a) \in \text{GW}_t(\Gamma)$. An example of a valid signature is depicted in Fig. 2. Note that $\psi$ is not required to be injective.
<figure><img src="image_3.png" /><figcaption>Figure 2: A valid signature $[B, S, \psi]$, adapted from [25]. **Right:** A top-arc set $S$ in an out-tree $T$. The three arcs of $S$ have distinct colors. **Left:** A “bag” $B$ of arcs in $N$. The colors indicate which arc of $S$ is mapped to which arc in $B$ by $\psi$. Note that $\psi$ maps both the magenta and the green arc of $S$ to the same magenta–green arc in $B$. **Middle:** A canonical tree extension $\Gamma$ of $N$ (arcs of $\Gamma$ depicted in gray) with the arcs of $N$ drawn in. The set $GW_v(\Gamma)$ is the current choice for $B$.</figcaption></figure>

**Definition 10.** A *signature* is an ordered triple $[B, S, \psi]$ containing a set $B \subseteq A(N)$ of arcs of $N$, a top-arc set $S \subseteq A(T)$ for the set of leaves reachable from $B$ in $N$, and a function $\psi: S \to B$. Such a signature $[B, S, \psi]$ is called *valid* if there is a soft pseudo-embedding $\phi$ of the forest below $S$ into $N$ such that, for every arc $(x, y) \in S$, the first arc of the path $\phi(x, y)$ is $\psi(x, y)$; then, $\phi$ is a *witness* for the valid signature $[B, S, \psi]$.

We now prove several lemmas leading up to Proposition 1, bounding the running time and establishing the correctness of Algorithm 1. First, it is important to bound the number of valid signatures.

**Lemma 2 (*)**. For each set $B \subseteq A(N)$, there are at most $(4 \cdot |B|)^{\Delta_T \cdot |B|}$ valid signatures of the form $[B, S, \psi]$.

For every non-root $v \in V(\Gamma)$, Algorithm 1 constructs the set $GWS_v$ of pairs $(S, \psi)$ for which $[GW_v(\Gamma), S, \psi]$ is a valid signature (and analogously for $HWS_v$). The construction has three steps: First, handling the case where $v$ is a leaf. Second, constructing $HWS_v$ when $v$ is not a leaf. Third, constructing $GWS_v$ when $v$ is not a leaf. The next three lemmas imply the steps' correctness.

**Lemma 3 (*)**. For each leaf $v \in L(\Gamma)$, there is exactly one ordered pair $(S, \psi)$ such that $[GW_v(\Gamma), S, \psi]$ is a valid signature.

For every non-root, non-leaf $v \in V(\Gamma)$, Algorithm 1 constructs $HWS_v$ by combining pairs from $GWS_{q_1}$ and $GWS_{q_2}$, where $q_1$ and $q_2$ are the children of $v$ in $\Gamma$. We define $D_u := D[\{w \in V(D) \mid u \ge_D w\}]$ for each $u \in V(D)$ in a DAG $D$, to refer to subtrees of $T$ and $\Gamma$. Recall that $\psi|_Z$ is the restriction of $\psi$ to $Z$.

**Lemma 4 (*)**. Let $v \in (V(\Gamma) \setminus \{\text{root}(\Gamma)\}) \setminus L(\Gamma)$ have children $V_\Gamma^+(v) = \{q_1, q_2\}$ in $\Gamma$, where $q_1$ and $q_2$ are not necessarily distinct, and let $[HW_v(\Gamma), S, \psi]$ be a signature. Further, for each $i \in \{1, 2\}$, let $S_i := \{(x, y) \in S \mid L(T_y) \subseteq L(\Gamma_{q_i})\}$.
Then, the signature $[HW_v(\Gamma), S, \psi]$ is valid if and only if (a) $S = S_1 \cup S_2$ and (b) $[GW_{q_i}(\Gamma), S_i, \psi|_{S_i}]$ is a valid signature for each $i \in \{1, 2\}$.

The next lemma concerns the correctness of the procedure POPULATEGWS. Given a non-root, non-leaf vertex $v \in V(\Gamma)$, this procedure constructs the set $GWS_v$ based on the elements of $HWS_v$. Informally speaking, this step from $HW_v(\Gamma)$ to $GW_v(\Gamma)$ unlocks the incoming arcs of $v$ in $N$. There are three ways in which these arcs may be used: (1) not at all, (2) to elongate paths of an existing embedding, or (3) to enlarge the downward-closed subforest to be embedded.

**Lemma 5 (★).** Let $v \in (V(\Gamma) \setminus \{\text{root}(\Gamma)\}) \setminus L(\Gamma)$ be a vertex and $[GW_v(\Gamma), S, \psi]$ a signature. Then, $[GW_v(\Gamma), S, \psi]$ is valid if and only if at least one of the three conditions below is met:

(1) $\psi(x, y) \notin A_N^-(v)$ for every $(x, y) \in S$, and $[HW_v(\Gamma), S, \psi]$ is a valid signature.

(2) $(u, v) \in \psi(S)$ for exactly one vertex $u \in V_N^-(v)$; further, it holds that

(2.1) $X := \psi^{-1}(u, v) \subseteq A_T^+(x)$ for some $x \in V(T)$, and

(2.2) $[HW_v(\Gamma), S, \psi']$ is a valid signature, where $\psi': S \to HW_v(\Gamma)$ is some function with $\psi'(X) \subseteq A_N^+(v)$ and, for all $(x', y') \in S \setminus X$, we have $\psi'(x', y') = \psi(x', y')$.

(3) $\psi(x, y) \in A_N^-(v)$ for exactly one $(x, y) \in S$; further, it holds that

(3.1) $y \notin L(T)$, and

(3.2) $[HW_v(\Gamma), S_{x,y}, \psi']$ is a valid signature, where $S_{x,y} := (S \setminus \{(x,y)\}) \cup A_T^+(y)$ and $\psi': S_{x,y} \to HW_v(\Gamma)$ is some function with $\psi'(A_T^+(y)) \subseteq A_N^-(v)$ and, for all $(x', y') \in S \setminus \{(x,y)\}$, we have $\psi'(x', y') = \psi(x', y')$.

While the previous lemmas established that Algorithm 1 constructs its valid signatures correctly, the next lemma implies that its final answer is correct.

**Lemma 6 (★).** Let $v \in V(N)$ be the child of the root of $N$, and let $a \in A(T)$ be the top arc of $T$. Then, $N^*$ softly displays $T^*$ if and only if there exists a valid signature of the form $[GW_v(\Gamma), \{a\}, \psi]$.

We now piece the previous lemmas together to conclude this section.

**Proposition 1.** Given $N$, $T$, and $\Gamma$ fulfilling Assumption 1, Algorithm 1 decides whether $N^*$ softly displays $T^*$ in $O^*(2^{\Delta_T \cdot (\text{sw}(\Gamma)+1) \cdot \log_2(4 \cdot \text{sw}(\Gamma)+4)})$ time.

*Proof.* Let $v \in V(\Gamma) \setminus \{\text{root}(\Gamma)\}$ be a vertex. Whenever Algorithm 1 adds a pair $(S, \psi)$ to $GWS_v$ (or $HWS_v$), it is true that $[GW_v(\Gamma), S, \psi]$ (or $[HW_v(\Gamma), S, \psi]$) is a signature. From Lemmas 3 to 5, it follows that Algorithm 1 generates precisely every such signature that is valid. Then, the correctness of Algorithm 1 is a consequence of Lemma 6. The bound on the running time may be deduced as follows: Because $N$ is binary, we have $|HW_v(\Gamma)| \le |GW_v(\Gamma)| + 1 \le \text{sw}(\Gamma) + 1$. Hence, by Lemma 2, the sets $GWS_v$ and $HWS_v$ contain at most $2^{\Delta_T \cdot (\text{sw}(\Gamma)+1) \cdot \log_2(4 \cdot \text{sw}(\Gamma)+4)}$ elements each. This also bounds the number of iterations of the loop in Line 14, as each iteration adds a new pair to $HWS_v$. $\square$
**Algorithm 1** Solve SOFT TREE CONTAINMENT on $N^*$ and $T^*$.

**Input:** $N$ (binary), $T$ (not necessarily binary), and $\Gamma$; see Assumption 1.

**Output:** If $N^*$ softly displays $T^*$, then YES, otherwise NO.

1: **procedure** SOLVESTC($N, T, \Gamma$)
2: &nbsp;&nbsp;&nbsp;&nbsp;**for** $v \in V(\Gamma) \setminus \{\text{root}(\Gamma)\}$ **in a bottom-up traversal of $\Gamma$** **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;GWS$_v \leftarrow \emptyset$;
4: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;HWS$_v \leftarrow \emptyset$;
5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $v \in L(\Gamma)$ **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$p \leftarrow$ parent of $v$ in $T$;
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$u \leftarrow$ parent of $v$ in $N$;
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;GWS$_v \leftarrow \{(\{(p, v)\}, \psi)\}$, where $\psi(p, v) := (u, v)$;
9: &nbsp;&nbsp;&nbsp;&nbsp;**else**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;\{q$_1$, q$_2$\} $\leftarrow$ $V_{\Gamma}^{+}(v)$; $\triangleright$ Note that $q_1$ and $q_2$ are not necessarily distinct.
11: &nbsp;&nbsp;&nbsp;&nbsp;**if** $q_1 = q_2$ **then**
12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;HWS$_v \leftarrow GWS_{q_1}$;
13: &nbsp;&nbsp;&nbsp;&nbsp;**else**
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** $((S_1, \psi_1), (S_2, \psi_2)) \in GWS_{q_1} \times GWS_{q_2}$ **do**
15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Add $(S_1 \cup S_2, \psi_1 \cup \psi_2)$ to $HWS_v$;
16: &nbsp;&nbsp;&nbsp;&nbsp;**POPULATE**GWS($N, T, \Gamma, v$); $\triangleright$ **Populate GWS**$_v$ using $HWS_v$.
17: &nbsp;&nbsp;&nbsp;&nbsp;v $\leftarrow$ child of the root of $N$;
18: &nbsp;&nbsp;&nbsp;&nbsp;a $\leftarrow$ top arc of $T$;
19: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\exists(S, \psi) \in GWS_v: S = \{a\}$ **then**
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** YES;
21: &nbsp;&nbsp;&nbsp;&nbsp;**else**
22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** NO;
23: **procedure** POPULATEGWS($N, T, \Gamma, v$)
24: &nbsp;&nbsp;&nbsp;&nbsp;**for** $(S, \psi) \in HWS_v$ **do**
25: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $\psi^{-1}(A_N^{+}(v)) = \emptyset$ **then**
26: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Add $(S, \psi)$ to $GWS_v$;
27: &nbsp;&nbsp;&nbsp;&nbsp;**else**
28: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $\exists x \in V(T): \psi^{-1}(A_N^{+}(v)) \subseteq A_T^{+}(x)$ **then**
29: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** $u \in V_N^{-}(v)$ **do**
30: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Define $\psi': S \to GW_v(\Gamma)$ such that
31: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$\psi'(x, y) := (u, v) \text{ for every } (x, y) \in \psi^{-1}(A_N^{+}(v)) \text{ and}$$
32: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$\psi'(x', y') := \psi(x', y') \text{ for every } (x', y') \in S \setminus \psi^{-1}(A_N^{+}(v));$$
33: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Add $(S, \psi')$ to $GWS_v$;
34: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\exists y \in V(T) \setminus \{\text{root}(T)\}: \psi^{-1}(A_N^{+}(v)) = A_T^{+}(y)$ **then**
35: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$x \leftarrow$ parent of $y$ in $T$;
36: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$S' \leftarrow (S \setminus \psi^{-1}(A_N^{+}(v))) \cup \{(x, y)\}$;
37: &nbsp;&nbsp;&nbsp;&nbsp;**for** $u \in V_N^{-}(v)$ **do**
38: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Define $\psi': S' \to GW_v(\Gamma)$ such that $\psi'(x, y) := (u, v)$ and
39: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$\psi'(x', y') := \psi(x', y') \text{ for every } (x', y') \in S \setminus \psi^{-1}(A_N^{+}(v));$$
40: &nbsp;&nbsp;&nbsp;&nbsp;Add $(S', \psi')$ to $GWS_v$;
<figure><img src="image_4.png" /><figcaption>Figure 3: Stretching a vertex $v$ with three children $c_1, c_2$, and $c_3$ gives this stretch gadget.</figcaption></figure>

## 4.2 Soft Display by Arbitrary Networks

In this section, we devise a reduction that maps any network to a binary one while preserving the trees that the network softly displays. The reduction can be performed in polynomial time, and the resulting increase in the scanwidth of the network can be bounded. Relying on the considerations of the previous section, we then obtain our main result (Theorem 1). The reduction consists of two steps:

1. We *stretch* the network. This means that we modify the network using gadgets that are conceptually very similar to the *universal networks* by Zhang [28] (see Fig. 3, also compare [28, Fig. 4]). Like these universal networks, our gadgets consist of a triangular upper part and a lower part that is based on a sorting network.

The triangular upper part is essentially one half of a grid that was slightly modified to obtain a phylogenetic network. In it, any binary phylogenetic tree (up to some number of leaves) can be embedded. As each high-out-degree vertex is replaced by a gadget when stretching, the stretched network represents all possible binary out-resolutions.

However, embedding a binary tree in the triangular upper part artificially enforces an order on the leaves of the binary tree. The lower part allows us to undo this. We choose a different sorting network than Zhang [28].

2. We compute an arbitrary binary in-resolution of the stretched network through exhaustive in-splitting. This does not affect which trees are firmly displayed.

**Definition 11.** Let $N$ be any arbitrary network, and let $v \in V(N)$ be a vertex with an out-degree of at least 3 in $N$. Then, *stretching* $v$ produces the network $N' := (V, A)$ formally specified in the appendix; see Fig. 3 for an example. Further, *stretching* $N$ refers to stretching every vertex of $N$ that has an out-degree of at least 3, and it produces the network $\text{str}(N)$.

The proof of Theorem 1 relies on four key claims: Lemmas 7 and 8, which state that stretching and in-splitting preserve the collection of trees softly displayed a network, and Lemmas 9 and 10, which state that the increase in scanwidth when stretching and in-splitting is bounded, using the network's maximum out-degree.
**Lemma 7** (⋆). Let $N$ be any network and let $T$ be any tree. Then, $N$ softly displays $T$ if and only if $\text{str}(N)$ softly displays $T$.

We argue that a stretched network can be made binary through in-splitting without altering the collection of softly displayed trees; the collection of firmly displayed trees also stays unaltered.

**Lemma 8** (⋆). Let $N$ be any network such that $\Delta_N = 2$, let $N'$ be any binary (in-)resolution of $N$, and let $T$ be any tree. Then, $N$ firmly/softly displays $T$ if and only if $N'$ firmly/softly displays $T$.

Finally, we show that neither stretching nor in-splitting to obtain a binary in-resolution can blow up the scanwidth too much, in order to prove Theorem 1.

**Lemma 9** (⋆). Let $N$ be any network. Then, $\text{sw}(\text{str}(N)) \le \text{sw}(N) + 2 \cdot \Delta_N$.

**Lemma 10** (⋆). Let $N'$ arise from any network $N$ through in-splitting. Then, $\text{sw}(N') \le \text{sw}(N)$.

**Theorem 1.** Given a network $N$, a tree $T$, and a tree extension $\Gamma$ of $N$, we can decide whether $N$ softly displays $T$ in $O^*(2^{O(\Delta_T \cdot k \cdot \log(k))})$ time, where $k := \text{sw}_N(\Gamma) + \Delta_N$.

*Proof.* Let $N'$ be a binary (in-)resolution of $\text{str}(N)$. By Lemmas 7 and 8, we know that $N$ softly displays $T$ if and only if $N'$ softly displays $T$. Based on $\Gamma$, we construct a tree extension $\Gamma'$ of $N'$ such that $\text{sw}_{N'}(\Gamma')$ is bounded from above by some linear function of $\text{sw}_N(\Gamma) + \Delta_N$, as described in the proofs of Lemmas 9 and 10. It is easy to modify $N'$ and $\Gamma'$ so as to fulfill the requirements of Assumption 1, since we reject if $L(T) \not\subseteq L(N)$. This involves removing excess leaves from $N'$, updating $\Gamma'$ accordingly, and making it canonical. Finally, we invoke Algorithm 1, from which we derive the promised running time; see Proposition 1. $\square$

**Disclosure of Interests.** The authors have no competing interests to declare.

# A Appendix

## A.1 Conclusion

We devised a parameterized algorithm for the SOFT TREE CONTAINMENT problem, where it has to be decided whether a phylogenetic network softly displays a phylogenetic tree. This algorithm consists of two steps: solving the problem via dynamic programming when the network is binary and reducing any non-binary network to an equivalent binary one. The running time of this algorithm depends exponentially on a function of the network's and the tree's maximum out-degree and of the scanwidth attained by a given tree extension of the network. The dependence on the input size is polynomial.

Future work can attempt to eliminate the superpolynomial dependence on the maximum out-degrees or, alternatively, rule out the existence of such an algorithm. Because of the dependence on scanwidth, it is essential to be able to obtain low-scanwidth tree extensions in a reasonable amount of time. This further motivates the search for exact or approximate algorithms to construct such tree extensions.
Additionally, it is of interest to tackle SOFT TREE CONTAINMENT with parameters stronger than scanwidth, such as node-scanwidth [15], edge-treewidth [19], or treewidth. Even weaker parameters could be of interest, when they give rise to algorithms that perform better in practice for example. Finally, it is worth exploring whether our techniques can be adapted to approach other containment problems, for instance, NETWORK CONTAINMENT in the sense of Janssen and Murakami [17].

## A.2 Further Details for Section 4.1

**Lemma 1** (⋆). The binary network $N^*$ softly displays the tree $T^*$ if and only if there is a soft pseudo-embedding of $T$ into $N$.

*Proof of Lemma 1.* There are two directions to consider.

“⇒”: Assume that $N^*$ softly displays $T^*$. There exists a leaf-respecting isomorphism $\iota$ between a subdivision $T^\dagger$ of a binary resolution of $T^*$ and a leaf-monotone subdigraph $N^\dagger$ of $N^*$. Note that, since $N^*$ is binary, it is its own unique binary resolution. We construct a soft pseudo-embedding $\phi$ of $T$ into $N$ as follows:

1. For every $(x, y) \in A(T^*)$, we define $\phi(x, y)$ as the path from $\iota(x)$ to $\iota(y)$ in $N^\dagger$.

2. We define $\phi(\rho_T, \text{root}(T^*))$ as a path from $\rho_N$ to $\iota(\text{root}(T^*))$ in $N$.

This defines $\phi$ for all arcs of $T$ because $A(T) = A(T^*) \cup \{(\rho_T, \text{root}(T^*))\}$. Moreover, $\phi$ maps each arc of $T$ to a directed path of length at least 1 in $N$.

We show that (SPE1) is satisfied: Let $(x, y), (y, z) \in A(T)$. By construction of $\phi$, the last vertex of $\phi(x, y)$ is $\iota(y)$. Since $x$ is a parent of $y$ in $T$, we have $y \neq \rho_T$. Thus, the first vertex of $\phi(y, z)$ is also $\iota(y)$.

We show that (SPE2) is satisfied: Let $(x, y), (x', y') \in A(T)$ with $x \neq x'$. Because $T$ is an out-tree, we have $y \neq y'$. The case where $x = \rho_T$ or $x' = \rho_T$ is easy. Hence, we now assume that $(x, y), (x', y') \in A(T^*)$. Then, $\phi(x, y), \phi(x', y') \subseteq N^\dagger$. To infer that $\phi(x, y)$ and $\phi(x', y')$ are arc-disjoint, it is sufficient to argue that, in $T^\dagger$, the path from $x$ to $y$ and the path from $x'$ to $y'$ are arc-disjoint, as $\iota$ is a leaf-respecting isomorphism between $T^\dagger$ and $N^\dagger$. In $T^*$, the path from $x$ to $y$ and the path from $x'$ to $y'$ are clearly arc-disjoint. When out-splitting or subdividing, the corresponding paths continue to be arc-disjoint, as a consequence of $x \neq x'$.

We show that (SPE3) is satisfied: Let $(x, y), (x, y') \in A(T)$ with $y \neq y'$. Since $y \neq y'$, we know that $x \neq \rho_T$. Thus, we have $(x, y), (x, y') \in A(T^*)$, and so $\phi(x, y), \phi(x, y') \subseteq N^\dagger$. It then suffices to argue that, in $T^\dagger$, the path from $x$ to $y$ and the path from $x$ to $y'$ are eventually arc-disjoint. This holds in $T^*$ and continues to hold when out-splitting or subdividing.

We show that (SPE4) is satisfied: Let $(x, \ell) \in A(T)$ with $\ell \in L(T)$. By construction of $\phi$, the last vertex of $\phi(x, \ell)$ is $\iota(\ell) = \ell$, using the fact that $\iota$ is leaf-respecting.

“ ⇐”: Let $\phi$ be a soft pseudo-embedding of $T$ into $N$. We perform the following steps:

1. We construct the out-tree $N' := \bigcup_{a \in A(T)} \phi(a)$.

2. We construct the set $R := \{v \in V(N') \mid \forall u \ge N' \ v: \deg_{N'}^+(u) = 1\}$.

3. We construct the out-tree $N'' := N' - R$.
It is easy to see that $N''$ is a leaf-monotone subdigraph of $N^*$. We argue that there is a leaf-respecting isomorphism between a subdivision of a binary resolution of $T^*$ and $N''$. To this end, we define a function $\tau$ mapping each non-leaf $x$ of $T^*$ to the binary out-tree to which the outgoing arcs of $x$ in $T^*$ are mapped by $\phi$. Then, each $\tau(x)$ can be obtained by out-splitting and subdividing around $x$ in $T^*$, except when $x$ is the root of $T^*$; we have to handle the root separately using the set $R$.

Formally, for every vertex $x \in V(T^*) \setminus L(T^*)$, define $\tau(x) := \bigcup_{a \in A_{T^*}^+(x)} \phi(a)$, and note that $(\bigcup_{x \in V(T^*) \setminus L(T^*)} \tau(x)) - R = N''$. Let $x, x' \in V(T^*) \setminus L(T^*)$ be distinct. The constraint (SPE2) implies that $\tau(x)$ and $\tau(x')$ are arc-disjoint. By (SPE3), we know that $\tau(x)$ is an out-tree. It is binary, its root is $\phi(x)$, and its leaves are $L(\tau(x)) = \{\phi(y) \mid y \in V_{T^*}^+(x)\}$. Starting from $T^*$, for each $x \in (V(T^*) \setminus L(T^*)) \setminus \{\text{root}(T^*)\}$, an out-tree corresponding to $\tau(x)$ can be constructed through out-splitting and subdividing; for $x = \text{root}(T^*)$, an out-tree corresponding to $\tau(x) - R$ can be constructed. $\square$

**Lemma 2** (⋆). For each set $B \subseteq A(N)$, there are at most $(4 \cdot |B|)^{\Delta_T \cdot |B|}$ valid signatures of the form $[B, S, \psi]$.

*Proof of Lemma 2.* Let $B \subseteq A(N)$ be a set of arcs. For all valid signatures of the form $[B, S, \psi]$, it holds that $|S| \le \Delta_T \cdot |B|$, since $|\psi^{-1}(u, v)| \le \Delta_T$ for every arc $(u, v) \in B$. This is because, when $\psi$ maps multiple arcs of $S$ to a single arc in $B$, these arcs of $S$ must have the same tail in order to permit eventual arc-disjointness. Therefore, to construct a valid signature of the form $[B, S, \psi]$, the number of choices for $S$ is at most $4^{\Delta_T \cdot |B|}$: This bound on the number of top-arc sets of bounded size for a fixed set of leaves is derived from a bound on the number of important separators due to Chitnis, Hajiaghayi, and Marx [8, Lemma 4.2]. Specifically, from every top-arc set $S$, an important $\{\rho_T\}$-$L(F)$ separator in a slight modification of $T$ can be obtained using the heads of the arcs in $S$, where $F$ is the forest below $S$ (see also [25, Lemma 6]). For each choice of $S$, the number of choices for $\psi$ is at most $|B|^{\lfloor S \rfloor} \le |B|^{\Delta_T \cdot |B|}$. Multiplying $4^{\Delta_T \cdot |B|}$ with $|B|^{\Delta_T \cdot |B|}$ gives the promised bound. $\square$

**Lemma 3** (⋆). For each leaf $v \in L(\Gamma)$, there is exactly one ordered pair $(S, \psi)$ such that $[GW_v(\Gamma), S, \psi]$ is a valid signature.

*Proof of Lemma 3.* Let $v \in L(\Gamma) = L(N) = L(T)$ be a leaf. We observe that a signature of the form $[GW_v(\Gamma), S, \psi]$ is valid if and only if (a) $S = A_T^-(v)$ and (b) $\psi$ maps the unique arc in $S$ to the unique arc in $GW_v(\Gamma) = A_N^-(v)$. $\square$

**Lemma 4** (⋆). Let $v \in (V(\Gamma) \setminus \{\text{root}(\Gamma)\}) \setminus L(\Gamma)$ have children $V_\Gamma^+(v) = \{q_1, q_2\}$ in $\Gamma$, where $q_1$ and $q_2$ are not necessarily distinct, and let $[HW_v(\Gamma), S, \psi]$ be a signature. Further, for each $i \in \{1, 2\}$, let $S_i := \{(x, y) \in S \mid L(T_y) \subseteq L(\Gamma_{q_i})\}$. Then, the signature $[HW_v(\Gamma), S, \psi]$ is valid if and only if (a) $S = S_1 \cup S_2$ and (b) $[GW_{q_i}(\Gamma), S_i, \psi|_{S_i}]$ is a valid signature for each $i \in \{1, 2\}$.

*Proof of Lemma 4.* “⇒”: Suppose that $[HW_v(\Gamma), S, \psi]$ is valid, and let $\phi$ be a witness for it.

First, we show $S \subseteq S_1 \cup S_2$: Let $(x, y) \in S$ be an arc of $T$ and let $(u, w) := \psi(x, y)$. Since $(u, w) \in HW_v(\Gamma)$, we have $v >_\Gamma w$ and, hence, $q_i \ge_\Gamma w$ for some $i \in \{1, 2\}$. In the following, we prove that $L(T_y) \subseteq L(\Gamma_{q_i})$ and, thus, $(x, y) \in S_i$. To this end, let $\ell \in L(T_y)$ be a leaf and let $P \subseteq T_y$ be the $y-\ell$ path in $T_y$. Then, $\bigcup_{a \in A(P)} \phi(a)$
is a path from $\phi(y)$ to $\ell$ in $N$ unless $\phi(y) = \ell$. Either way, $w \ge_N \phi(y) \ge_N \ell$, so
$q_i \ge_\Gamma w \ge_\Gamma \ell$ and, consequently, $\ell \in L(\Gamma_{q_i})$.

Second, let $i \in \{1, 2\}$ and let $F \subseteq T$ be the forest below $S_i$. Then, $\phi|_{A(F)}$ is a witness for the valid signature $[GW_{q_i}(\Gamma), S_i, \psi|_{S_i}]$.

“$\Leftarrow$”: We assume that $S = S_1 \cup S_2$ and that $[GW_{q_i}(\Gamma), S_i, \psi|_{S_i}]$ is a valid signature for each $i \in \{1, 2\}$, witnessed by $\phi_i$. If $q_1 = q_2$, then $HW_v(\Gamma) = GW_{q_1}(\Gamma)$, $S = S_1$, and $\psi = \psi|_{S_1}$, so $[HW_v(\Gamma), S, \psi]$ is valid. If $q_1 \neq q_2$, then $S_1 \cap S_2 = \emptyset$ and $\phi := \phi_1 \uplus \phi_2$ is a witness for $[HW_v(\Gamma), S, \psi]$. $\square$

**Lemma 5 (*)**. Let $v \in (V(\Gamma) \setminus \{\text{root}(\Gamma)\}) \setminus L(\Gamma)$ be a vertex and $[GW_v(\Gamma), S, \psi]$ a signature. Then, $[GW_v(\Gamma), S, \psi]$ is valid if and only if at least one of the three conditions below is met:

(1) $\psi(x, y) \notin A_N^-(v)$ for every $(x, y) \in S$, and $[HW_v(\Gamma), S, \psi]$ is a valid signature.

(2) $(u, v) \in \psi(S)$ for exactly one vertex $u \in V_N^-(v)$; further, it holds that

(2.1) $X := \psi^{-1}(u, v) \subseteq A_T^+(x)$ for some $x \in V(T)$, and

(2.2) $[HW_v(\Gamma), S, \psi']$ is a valid signature, where $\psi': S \to HW_v(\Gamma)$ is some function with $\psi'(X) \subseteq A_N^+(v)$ and, for all $(x', y') \in S \setminus X$, we have $\psi'(x', y') = \psi(x', y')$.

(3) $\psi(x, y) \in A_N^-(v)$ for exactly one $(x, y) \in S$; further, it holds that

(3.1) $y \notin L(T)$, and

(3.2) $[HW_v(\Gamma), S_{x,y}, \psi']$ is a valid signature, where $S_{x,y} := (S \setminus \{(x,y)\}) \cup A_T^+(y)$ and $\psi': S_{x,y} \to HW_v(\Gamma)$ is some function with $\psi'(A_T^+(y)) \subseteq A_N^+(v)$ and, for all $(x', y') \in S \setminus \{(x,y)\}$, we have $\psi'(x', y') = \psi(x', y')$.

*Proof of Lemma 5, sketch.* “⇒”: Suppose that $[GW_v(\Gamma), S, \psi]$ is valid, and let $\phi$ be a witness for it. Then, at least one of the following holds, and we consider them individually:

(a) $\psi(x, y) \notin A_N^-(v)$ for every arc $(x, y) \in S$.

(b) $\psi(x, y) \in A_N^-(v)$ for some arc $(x, y) \in S$ with $\phi(y) \neq v$.

(c) $\psi(x, y) \in A_N^-(v)$ for some arc $(x, y) \in S$ with $\phi(y) = v$.

Case (a): Because $\psi(S) \subseteq GW_v(\Gamma) \setminus A_N^-(v) \subseteq HW_v(\Gamma)$, we know that $[HW_v(\Gamma), S, \psi]$ is a valid signature witnessed by $\phi$, so (1) is met.

Case (b): We observe that $\psi(S) \cap A_N^-(v)$ contains a single arc $(u, v)$. Consider the set $X := \psi^{-1}(u, v)$, and note that $(x, y) \in X$ and $X \subseteq A_T^+(x)$. For each arc $(x, z) \in X$, we define $\phi'(x, z)$ as the path obtained by removing $u$ from the path $\phi(x, z)$. For each arc $(x', y') \in A(F) \setminus X$, where $F$ is the forest below $S$, we define $\phi'(x', y') := \phi(x', y')$. Further, we construct $\psi': S \to HW_v(\Gamma)$ by setting $\psi'(a)$ to be the first arc of $\phi'(a)$ for all $a \in S$. Then, $[HW_v(\Gamma), S, \psi']$ is a valid signature, and $\phi'$ is a witness for it. We observe that (2) is met now.

Case (c): As $\phi(y) = v$ and $v \notin L(\Gamma) = L(N) = L(T)$, we have $y \notin L(T)$. The existence of an arc $(x', y') \in S \setminus \{(x,y)\}$ with $\psi(x', y') \in A_N^-(v)$ would lead to violations of (eventual) arc-disjointness, so no such arc $(x', y')$ exists. We construct $\phi' := \phi|_{A(F)}$, where $F$ is the forest below $S_{x,y}$, and we define $\psi'(a)$ to be the
S. Bruchhold and M. Weller

first arc of $\phi'(a)$ for each $a \in S_{x,y}$. Then, $\phi'$ is a witness for the valid signature $[HW_v(\Gamma), S_{x,y}, \psi']$. We can infer that (3) is met.

“$\Leftarrow$”: We argue the three cases, assuming that (1), (2), or (3) holds, individually.

Case (1): Let $\phi'$ be a witness for the valid signature $[HW_v(\Gamma), S, \psi]$. Then, $\phi'$ is a witness for $[GW_v(\Gamma), S, \psi]$ as well, proving its validity.

Case (2): Let $\phi'$ be a witness for the valid signature $[HW_v(\Gamma), S, \psi']$. For each $(x, y) \in X$, we define $\phi(x, y)$ to be the path obtained by prepending the vertex $u$ and the arc $(u, v)$ to the path $\phi'(x, y)$. For each $(x', y') \in A(F) \setminus X$, where $F$ is the forest below $S$, we define $\phi(x', y') := \phi'(x', y')$. Then, $\phi$ is a witness for the valid signature $[GW_v(\Gamma), S, \psi]$.

Case (3): Let $\phi'$ be a witness for the valid signature $[HW_v(\Gamma), S_{x,y}, \psi']$. We define $\phi(x, y)$ to be the length-1 path containing the arc $\psi(x, y)$, and we define $\phi(x', y') := \phi'(x', y')$ for every $(x', y') \in A(F)$, where $F$ is the forest below $S_{x,y}$. Then, $\phi$ witnesses the validity of $[GW_v(\Gamma), S, \psi]$. $\square$

**Lemma 6** (⋆). Let $v \in V(N)$ be the child of the root of $N$, and let $a \in A(T)$ be the top arc of $T$. Then, $N^*$ softly displays $T^*$ if and only if there exists a valid signature of the form $[GW_v(\Gamma), \{a\}, \psi]$.

*Proof of Lemma 6.* “⇒”: Suppose that $N^*$ softly displays $T^*$. From the proof of Lemma 1, we deduce that there is a soft pseudo-embedding $\phi$ of $T$ into $N$ such that the first arc of the path $\phi(a)$ is $(\rho_N, v)$. We define the function $\psi(a) := (\rho_N, v)$. Then, $[GW_v(\Gamma), \{a\}, \psi]$ is a valid signature, and $\phi$ is a witness for it.

“$\Leftarrow$”: Let $[GW_v(\Gamma), \{a\}, \psi]$ be a valid signature, and let $\phi$ be a witness for it. Then, $\phi$ is a soft pseudo-embedding of $T$ into $N$. Thus, $N^*$ softly displays $T^*$ by Lemma 1. $\square$

## A.3 Further Details for Section 4.2

**Definition 12** (Full version of Definition 11). Let $N$ be any arbitrary network, and let $v \in V(N)$ be a vertex with an out-degree of at least 3 in $N$. Then, stretching $v$ produces the network $N' := (V, A)$ by adding several new vertices, that is,

$$ 
\begin{align*}
V &:= V(N) \uplus (\{u_{i,j} \mid i \in [2, d-1] \wedge j \in [1, i]\}) \\
&\quad \uplus (\{u'_{i,j} \mid i \in [3, d-1] \wedge j \in [2, i-1]\}) \\
&\quad \uplus (\{u_{d,j} \mid j \in [2, d-1]\}) \\
&\quad \uplus \{w_{i,j,k} \mid i, j \in [1, d-1] \wedge k \in [1, 4]\})),
\end{align*}
$$

where $d := \deg_N^+(v)$, while using the arcs

$$ 
\begin{align*}
A &:= (A(N) \setminus A_N^+(v)) \\
  &\quad \cup \{(v, u_{2,1}), (v, u_{2,2})\} \\
  &\quad \cup \{(u_{i,1}, u_{i+1,1}), (u_{i,1}, u_{i+1,2}) \mid i \in [2, d-2]\} \\
  &\quad \cup \{(u_{i,i}, u_{i+1,i}), (u_{i,i}, u_{i+1,i+1}) \mid i \in [2, d-2]\} \\
  &\quad \cup \{(u_{i,j}, u'_{i,j}) \mid i \in [3, d-1] \wedge j \in [2, i-1]\} \\
  &\quad \cup \{(u'_{i,j}, u_{i+1,j}), (u'_{i,j}, u_{i+1,j+1}) \mid i \in [3, d-1] \wedge j \in [2, i-1]\} \\
  &\quad \cup \{(u_{d-1,1}, w_{1,1,1}), (u_{d-1,1}, u_{d,2})\}
\end{align*}
$$
$$
\begin{align*}
& \cup \{(u_{d-1,d-1}, u_{d,d-1}), (u_{d-1,d-1}, w_{1,d-1,2})\} \\
& \cup \{(u_{d,j}, w_{1,j-1,2}) \mid j \in [2, d-1]\} \\
& \cup \{(w_{i,j,1}, w_{i,j,3}), (w_{i,j,1}, w_{i,j,4}) \mid i, j \in [1, d-1]\} \\
& \cup \{(w_{i,j,2}, w_{i,j,3}), (w_{i,j,2}, w_{i,j,4}) \mid i, j \in [1, d-1]\} \\
& \cup \{(w_{i,j,4}, w_{i,j+1,1}) \mid i \in [1, d-1] \land j \in [1, d-2]\} \\
& \cup \{(w_{i,1,3}, w_{i+1,1,1}) \mid i \in [1, d-2]\} \\
& \cup \{(w_{i,d-1,4}, w_{i+1,d-1,2}) \mid i \in [1, d-2]\} \\
& \cup \{(w_{i,j,3}, w_{i+1,j-1,2}) \mid i \in [1, d-2] \land j \in [2, d-1]\} \\
& \cup \{(w_{d-1,j,3}, c_j) \mid j \in [1, d-1]\} \\
& \cup \{(w_{d-1,d-1,4}, c_d)\},
\end{align*}
$$

assuming that the children of $v$ in $N$ are $V_N^+(v) = \{c_1, c_2, \dots, c_d\}$. Further, stretching $N$ refers to stretching every vertex of $N$ that has an out-degree of at least 3, and it produces the network $\text{str}(N)$.

To prove Lemma 7, we first formalize the intuition that the stretched network “represents” all possible binary out-resolutions.

**Lemma 11.** Let $N$ be a network and let $T$ be a tree. Then, $\text{str}(N)$ firmly displays $T$ if and only if there is a binary out-resolution of $N$ that firmly displays $T$.

*Proof.* “⇒”: Suppose $\text{str}(N)$ firmly displays $T$, that is, there is some leaf-monotone subdigraph $N'$ of $\text{str}(N)$ that is isomorphic (respecting leaves) to some subdivision $T'$ of $T$, and let $\iota: V(T') \to V(N')$ denote this isomorphism. We note that $T$ is necessarily binary. We then aim to establish the existence of a binary out-resolution of $N$ that firmly displays $T$. Informally, we first suppress all suppressible vertices of $N'$ that are strictly inside the stretch gadgets of $\text{str}(N)$. Now, there might be some vertices $u$ of $N$ with out-degree 1 left that have bifurcating vertices in their stretch gadgets, and so we contract the top bifurcation onto $u$. More formally,

1. we construct the set $S_1 := \{v \in V(N') \setminus V(N) \mid \deg_{N'}(v) = \deg_{N'}(v) = 1\}$,

2. we obtain $N''$ from $N'$ by suppressing all vertices that are in $S_1$,

3. we obtain $T''$ from $T'$ by suppressing all vertices that are in $\iota^{-1}(S_1)$,

4. we construct the leaf-respecting isomorphism $\kappa := \iota|_{V(T'')}$ between $T''$ and $N''$,

5. we construct $S_2 := \{u \in V(N'') \cap V(N) \mid \deg_{N''}^+(u) = 1 \land \deg_{N''}^+(u) \not\subseteq \deg_{N''}^+(u)\}$,

6. we obtain $N'''$ from $N''$ by, for each $u \in S_2$, contracting the child of $u$ into $u$, and

7. we obtain $T'''$ from $T''$ by suppressing all vertices that are in $\kappa^{-1}(S_2)$.

We observe that $T'''$ is a subdivision of $T$, that there is some leaf-respecting isomorphism between $T'''$ and $N'''$, and that there is a subdivision of $N'''$ that simultaneously is a leaf-monotone subdigraph of some binary out-resolution of $N$. We can conclude that such a binary out-resolution of $N$ firmly displays $T$.
“$\Leftarrow$”: Suppose $T$ is firmly displayed by a binary out-resolution $N'$ of $N$, that is, $N'$ has a leaf-monotone subdigraph $N''$ that is isomorphic (respecting leaves) to a subdivision of $T$, and let $\iota$ denote this isomorphism. By construction of $\mathrm{str}(N)$, we know that $\mathrm{str}(N)$ has a leaf-monotone subdigraph $N'''$ that is isomorphic (respecting leaves) to some subdivision of $N''$, and we let $\kappa$ denote this isomorphism. From $\iota$ and $\kappa$, we can construct a leaf-respecting isomorphism between some suitable subdivision of $T$ and $N'''$, proving that $\mathrm{str}(N)$ firmly displays $T$. $\square$

**Lemma 7** (⋆). Let $N$ be any network and let $T$ be any tree. Then, $N$ softly displays $T$ if and only if $\mathrm{str}(N)$ softly displays $T$.

*Proof of Lemma 7.* “⇒”: First, assume that $N$ softly displays $T$. There is a binary out-resolution $N''$ of a binary in-resolution $N'$ of $N$ as well as a binary resolution $T'$ of $T$ such that $N''$ firmly displays $T'$. From Lemma 11, it follows that $\mathrm{str}(N')$ firmly displays $T'$. Since $\mathrm{str}(N')$ is a binary resolution of $\mathrm{str}(N)$, we conclude that $\mathrm{str}(N)$ softly displays $T$.

“$\Leftarrow$”: Second, suppose that $\mathrm{str}(N)$ softly displays $T$. Then, there is a binary resolution $T'$ of $T$ that is firmly displayed by some binary resolution of $\mathrm{str}(N)$. Any such binary resolution of $\mathrm{str}(N)$ may be assumed to have the form $\mathrm{str}(N')$ for some binary in-resolution $N'$ of $N$. To summarize, $\mathrm{str}(N')$ firmly displays $T'$. From Lemma 11, it follows that there is a binary out-resolution $N''$ of $N'$ that firmly displays $T'$. Because $N''$ is a binary resolution of $N$, this implies that $N$ softly displays $T$. $\square$

**Lemma 8** (⋆). Let $N$ be any network such that $\Delta_N = 2$, let $N'$ be any binary (in-)resolution of $N$, and let $T$ be any tree. Then, $N$ firmly/softly displays $T$ if and only if $N'$ firmly/softly displays $T$.

*Proof of Lemma 8.* The “firmly”-part is a slight adaptation of a proposition by Gunawan [13, Proposition 3.9]. As the proof is analogous, we omit it here and show only the “softly”-part.

“⇒”: Suppose that $N$ softly displays $T$. Then, there are binary resolutions $N''$ of $N$ and $T'$ of $T$ such that $N''$ firmly displays $T'$. Applying the “firmly”-part, it follows that $N$ firmly displays $T'$. By applying the “firmly”-part again, we infer that $N'$ firmly displays $T'$. Since $N'$ is its own binary resolution, we can conclude that $N'$ softly displays $T$.

“$\Leftarrow$”: Suppose that $N'$ softly displays $T$. Then, $N'$ firmly displays some binary resolution of $T$. As $N'$ is a binary resolution of $N$, we deduce that $N$ softly displays $T$. $\square$

**Lemma 9** (⋆). Let $N$ be any network. Then, $\mathrm{sw}(\mathrm{str}(N)) \le \mathrm{sw}(N) + 2 \cdot \Delta_N$.

*Proof of Lemma 9.* Let $\Gamma$ be any tree extension of $N$. We prove the lemma in two steps.

First, let $v \in V(N)$ be a vertex with $d := \mathrm{deg}_N^+(v) \ge 3$, and let $N'$ be obtained from $N$ by stretching $v$, thereby adding several new vertices:

$$ 
\begin{aligned}
V(N') = V(N) &\uplus \{u_{i,j} \mid i \in [2, d-1] \wedge j \in [1, i]\} \\
&\uplus \{u'_{i,j} \mid i \in [3, d-1] \wedge j \in [2, i-1]\} \\
&\uplus \{u_{d,j} \mid j \in [2, d-1]\} \\
&\uplus \{w_{i,j,k} \mid i,j \in [1, d-1] \wedge k \in [1, 4]\})\}.
\end{aligned}
$$
We construct a tree extension $\Gamma'$ of $N'$ by inserting the new vertices, $V(N') \setminus V(N)$, in the form of a path right below $v$ in $\Gamma$, above the children of $v$ in $\Gamma$. The new vertices are inserted one after the other according to the following procedure:

1. For $i \leftarrow 2$ to $d-1$:

(a) For $j \leftarrow 1$ to $i$, insert $u_{i,j}$.

(b) For $j \leftarrow 2$ up to $i-1$, insert $u'_{i,j}$.

2. For $j \leftarrow 2$ to $d-1$, insert $u_{d,j}$.

3. For $i \leftarrow 1$ to $d-1$, for $j \leftarrow 1$ to $d-1$, for $k \leftarrow 1$ to 4, insert $w_{i,j,k}$.

It is easy to verify that the resulting out-tree $\Gamma'$ is a tree extension of $N'$.

Second, we construct a tree extension $\Gamma''$ of $\text{str}(N)$ as follows: Starting from $\Gamma$, we perform the above procedure for each vertex of $N$ that was stretched to obtain $\text{str}(N)$, inserting a new path each time. We observe that $\text{sw}(\Gamma'') \le \text{sw}(\Gamma) + 2 \cdot \Delta_N$ and, since $\Gamma$ was chosen arbitrarily, $\text{sw}(\text{str}(N)) \le \text{sw}(N) + 2 \cdot \Delta_N$. $\square$

**Lemma 10 (★).** Let $N'$ arise from any network $N$ through in-splitting. Then, $\text{sw}(N') \le \text{sw}(N)$.

*Proof of Lemma 10.* Let $N$ be any arbitrary network, let $v \in V(N)$ have in-degree at least 3 in $N$, let $u, w \in V_N^-(v)$ be two distinct parents of $v$ in $N$, and let $N'$ be the result of in-splitting $u$ and $w$ from $v$ in $N$, thereby adding a new vertex $x \in V(N') \setminus V(N)$. Also, let $\Gamma$ be any tree extension of $N$. Clearly, $v$ cannot be the root of $\Gamma$; let $s \in V_\Gamma^-(v)$ be the parent of $v$ in $\Gamma$. We construct $\Gamma'$ by subdividing the arc $(s, v) \in A(\Gamma)$ with $x$ in $\Gamma$. It is easy to see that $\Gamma'$ is a tree extension of $N'$. To conclude that $\text{sw}(N') \le \text{sw}(N)$, as $\text{sw}_{N'}(\Gamma') \le \text{sw}_N(\Gamma)$, we make the following observations: Let $t \in V(\Gamma') \setminus \{x, v\} \subseteq V(\Gamma)$ be a vertex.

1. We have $\text{GW}_t(\Gamma') \setminus \{(u, x), (w, x)\} \subseteq \text{GW}_t(\Gamma) \setminus \{(u, v), (w, v)\}$.

2. If $(u, x) \in \text{GW}_t(\Gamma')$, then $(u, v) \in \text{GW}_t(\Gamma)$.

3. If $(w, x) \in \text{GW}_t(\Gamma')$, then $(w, v) \in \text{GW}_t(\Gamma)$.

4. We have $\text{GW}_x(\Gamma') \uplus \{(u, v), (w, v)\} \subseteq \text{GW}_v(\Gamma) \uplus \{(u, x), (w, x)\}$.

5. We have $\text{GW}_v(\Gamma') \uplus \{(u, v), (w, v)\} \subseteq \text{GW}_v(\Gamma) \uplus \{(x, v)\}$.

Therefore, $|\text{GW}_t(\Gamma')| \le |\text{GW}_t(\Gamma)|$, $|\text{GW}_x(\Gamma')| \le |\text{GW}_v(\Gamma)|$, and $|\text{GW}_v(\Gamma')| \le |\text{GW}_v(\Gamma)|$. $\square$

## References

[1] Matthias Bentert, Josef Malík, and Mathias Weller. Tree containment with soft polytomies. In *16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)*, volume 101 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 9:1–9:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.SWAT.2018.9.
[2] Matthias Bentert and Mathias Weller. Tree containment with soft polytomies. *Journal of Graph Algorithms and Applications*, 25(1):417–436, 2021. doi: 10.7155/jgaa.00565.

[3] Vincent Berry, Celine Scornavacca, and Mathias Weller. Scanning phylogenetic networks is NP-hard. In *SOFSEM 2020: Theory and Practice of Computer Science*, volume 12011 of *Lecture Notes in Computer Science*, pages 519–530. Springer, 2020. Full version: https://hal.science/hal-02353161v2. doi:10.1007/978-3-030-38919-2_42.

[4] H. L. Bodlaender. A tourist guide through treewidth. *Acta Cybernetica*, 11(1-2):1-21, 1993. URL: https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3417.

[5] Magnus Bordewich and Charles Semple. Reticulation-visible networks. *Advances in Applied Mathematics*, 78:114–141, 2016. doi:10.1016/j.aam.2016.04.004.

[6] Sebastian Bruchhold and Mathias Weller. Exploiting low scanwidth to resolve soft polytomies. In *SOFSEM 2026: Theory and Practice of Computer Science*, 2026. Accepted.

[7] Joseph Minhow Chan, Gunnar Carlsson, and Raul Rabadan. Topology of viral evolution. *Proceedings of the National Academy of Sciences*, 110(46):18566–18571, 2013. doi:10.1073/pnas.1313480110.

[8] Rajesh Chitnis, Mohammad Taghi Hajiaghayi, and Dániel Marx. Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset. *SIAM Journal on Computing*, 42(4):1674–1696, 2013. doi: 10.1137/12086217X.

[9] Jittat Fakcharoenphol, Tanee Kumpijit, and Attakorn Putwattana. A faster algorithm for the tree containment problem for binary nearly stable phylogenetic networks. In *12th International Joint Conference on Computer Science and Software Engineering (JCSSE'15)*, pages 337–342. IEEE, 2015. doi:10.1109/JCSSE.2015.7219820.

[10] Philippe Gambette, Andreas D. M. Gunawan, Anthony Labarre, Stéphane Vlalette, and Louxin Zhang. Locating a tree in a phylogenetic network in quadratic time. In *Research in Computational Molecular Biology*, volume 9029 of *Lecture Notes in Bioinformatics*, pages 96–107. Springer, 2015. doi: 10.1007/978-3-319-16706-0_12.

[11] Andreas D. M. Gunawan. Solving tree containment problem for reticulation-visible networks with optimal running time, 2017. arXiv:1702.04088, doi: 10.48550/arXiv.1702.04088.

[12] Andreas D. M. Gunawan, Bhaskar DasGupta, and Louxin Zhang. A decomposition theorem and two algorithms for reticulation-visible networks. *Information and Computation*, 252:161–175, 2017. doi:10.1016/j.ic.2016.11.001.

[13] Andreas Dwi Maryanto Gunawan. *On the Tree and Cluster Containment Problems for Phylogenetic Networks*. PhD thesis, National University of
Singapore, 2018. URL: https://scholarbank.nus.edu.sg/handle/10635/144270.

[14] Dan Gusfield. *ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks*. MIT Press, 2014. doi:10.7551/mitpress/9432.001.0001.

[15] Niels Holtgrefe. Computing the scanwidth of directed acyclic graphs. Master's thesis, Delft University of Technology, 2023. URL: http://resolver.tudelft.nl/uuid:9c82fd2a-5841-4aac-8e40-d4d22542cdf5.

[16] Daniel H. Huson, Regula Rupp, and Celine Scornavacca. *Phylogenetic Networks: Concepts, Algorithms and Applications*. Cambridge University Press, 2010. doi:10.1017/CB09780511974076.

[17] Remie Janssen and Yukihiro Murakami. On cherry-picking and network containment. *Theoretical Computer Science*, 856:121–150, 2021. doi:10.1016/j.tcs.2020.12.031.

[18] Iyad A. Kanj, Luay Nakhleh, Cuong Than, and Ge Xia. Seeing the trees and their branches in the network is hard. *Theoretical Computer Science*, 401(1–3):153–164, 2008. doi:10.1016/j.tcs.2008.04.019.

[19] Loïc Magne, Christophe Paul, Abhijat Sharma, and Dimitrios M. Thilikos. Edge-treewidth: Algorithmic and combinatorial properties. *Discrete Applied Mathematics*, 341:40–54, 2023. doi:10.1016/j.dam.2023.07.023.

[20] B. Reed. Introducing directed tree width. *Electronic Notes in Discrete Mathematics*, 3:222–229, 1999. 6th Twente Workshop on Graphs and Combinatorial Optimization. doi:10.1016/S1571-0653(05)80061-7.

[21] Mohammad Ali Safari. D-width: A more natural measure for directed tree width. In *Mathematical Foundations of Computer Science 2005*, pages 745–756. Springer, 2005. doi:10.1007/11549345_64.

[22] Celine Scornavacca and Mathias Weller. Treewidth-based algorithms for the small parsimony problem on networks. *Algorithms Mol. Biol.*, 17, 2022. doi:10.1186/s13015-022-00216-w.

[23] Todd J. Treangen and Eduardo P. C. Rocha. Horizontal transfer, not duplication, drives the expansion of protein families in prokaryotes. *PLoS Genet.*, 7(1), 2011. doi:10.1371/journal.pgen.1001284.

[24] Leo van Iersel, Mark Jones, and Mathias Weller. Embedding phylogenetic trees in networks of low treewidth. *Discrete Mathematics & Theoretical Computer Science*, 25(2), 2023. doi:10.46298/dmtcs.10116.

[25] Leo van Iersel, Mark Jones, and Mathias Weller. Tree and network containment parameterized by scanwidth. Unpublished manuscript, 2025.

[26] Leo van Iersel, Charles Semple, and Mike Steel. Locating a tree in a phylogenetic network. *Information Processing Letters*, 110(23):1037–1043, 2010. doi:10.1016/j.ipl.2010.07.027.
[27] Mathias Weller. Linear-time tree containment in phylogenetic networks. In *RECOMB International conference on Comparative Genomics*, pages 309–323. Springer, 2018. doi:10.1007/978-3-030-00834-5_18.

[28] Louxin Zhang. On tree-based phylogenetic networks. *Journal of Computational Biology*, 23(7):553–565, 2016. doi:10.1089/cmb.2015.0228.