Structural Parameterization of Steiner Tree Packing

Hastrich, Niko; Simonov, Kirill

doi:10.4230/LIPIcs.STACS.2026.51

Structural Parameterization of Steiner Tree Packing

Niko Hastrich

Saarland University and Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany Kirill Simonov

Department of Informatics, University of Bergen, Norway

Abstract

Steiner Tree Packing $(\operatorname{\mathsf{STP}})$ is a notoriously hard problem in classical complexity theory, which is of practical relevance to VLSI circuit design. Previous research has approached this problem by providing heuristic or approximate algorithms. In this paper, we show the first $\operatorname{\mathsf{FPT}}$ algorithms for $\operatorname{\mathsf{STP}}$ parameterized by structural parameters of the input graph. In particular, we show that $\operatorname{\mathsf{STP}}$ is fixed-parameter tractable by the tree-cut width as well as the fracture number of the input graph.

To achieve our results, we generalize techniques from Edge-Disjoint Paths ( $\operatorname{\mathsf{EDP}}$ ) to Generalized Steiner Tree Packing ( $\operatorname{\mathsf{GSTP}}$ ), which generalizes both $\operatorname{\mathsf{STP}}$ and $\operatorname{\mathsf{EDP}}$ . First, we derive the notion of the augmented graph for $\operatorname{\mathsf{GSTP}}$ analogous to $\operatorname{\mathsf{EDP}}$ . We then show that $\operatorname{\mathsf{GSTP}}$ is $\operatorname{\mathsf{FPT}}$ by

$\blacksquare$

the tree-cut width of the augmented graph,
$\blacksquare$

the fracture number of the augmented graph,
$\blacksquare$

the slim tree-cut width of the input graph.

The latter two results were previously known for $\operatorname{\mathsf{EDP}}$ ; our results generalize these to $\operatorname{\mathsf{GSTP}}$ and improve the running time for the parameter fracture number. On the other hand, it was open whether $\operatorname{\mathsf{EDP}}$ is $\operatorname{\mathsf{FPT}}$ parameterized by the tree-cut width of the augmented graph, despite extensive research on the structural complexity of the problem. We settle this question affirmatively.

Keywords and phrases:

Steiner tree packing, structural parameters, fixed-parameter tractability

Funding:

Niko Hastrich: This work is part of the project TIPEA that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 850979).

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Fixed parameter tractability ; Theory of computation

\rightarrow

Graph algorithms analysis

Related Version:

Full Version: https://arxiv.org/abs/2505.09250 [18]

Funding:

This work was conducted in part at Hasso Plattner Institute, University of Potsdam.

DOI:

10.4230/LIPIcs.STACS.2026.51

Event:

43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Editors:

Meena Mahajan, Florin Manea, Annabelle McIver, and Nguyễn Kim Thắng

Series and Publisher:

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

1 Introduction

In Steiner tree packing ( $\operatorname{\mathsf{STP}}$ ), we are given a triple $(G,T,d)$ , where $G$ is a graph, $T\subseteq V(G)$ is the terminal set, and $d\in\operatorname{\mathbb{N}}^{+}$ is the demand. The goal is to decide whether there are $d$ edge-disjoint trees $F_{1},F_{2},\dots,F_{d}$ in $G$ which all contain the vertices $T$ . It is easy to see that the problem is polynomial-time solvable if ${\mathchoice{\left|T\right|}{{|T|}}{{|T|}}{{|T|}}}\leq 2$ or $d=1$ . However, even for ${\mathchoice{\left|T\right|}{{|T|}}{{|T|}}{{|T|}}}\geq 3$ or $d\geq 2$ , $\operatorname{\mathsf{STP}}$ is already $\operatorname{\mathsf{NP}\text{-hard}}$ [19, 1]. Despite this obstacle, $\operatorname{\mathsf{STP}}$ – and the related problems $\operatorname{\mathsf{EDP}}$ and $\operatorname{\mathsf{GSTP}}$ , which we introduce shortly – has extensive applications. The problem has been closely studied in the context of VLSI circuit design [22, 5, 7, 23, 25, 17], designing computer networks for multicasting [24, 6, 15], and video-conferencing [28].

From a more theoretical perspective, Steiner Tree Packing has seen a long line of research focusing on the optimal gap between the edge connectivity of the terminal set and the size of the tree packing. On the one hand, if there are $d$ edge-disjoint subgraphs connecting $T$ , $T$ is clearly $d$ -edge-connected. On the other, Kriesell [21] conjectured that if $T$ is $2d$ -edge-connected, then $G$ contains $d$ edge-disjoint trees connecting $T$ . While the conjecture remains open, we know that $(5d+4)$ –edge-connectivity is sufficient [8]. These results are constructive, providing algorithms that approximate the size of a maximum Steiner tree packing within a constant factor in polynomial time. However, even by proving the original conjecture of Kriesell one could only obtain a $2$ -approximate algorithm for $\operatorname{\mathsf{STP}}$ .

The situation with exact polynomial-time algorithms for $\operatorname{\mathsf{STP}}$ is considerably more restrictive. As discussed above, in terms of the size $|T|$ of the terminal set and the demand $d$ , we can only expect polynomial time when both are bounded. In fact, it follows from the celebrated result of Robertson and Seymour [26], that $\operatorname{\mathsf{STP}}$ is fixed-parameter tractable by ${\mathchoice{\left|T\right|}{{|T|}}{{|T|}}{{|T|}}}+d$ . However, this result is non-constructive and the running time as a function of ${\mathchoice{\left|T\right|}{{|T|}}{{|T|}}{{|T|}}}+d$ is enormously fast-growing; in particular, this result has very little practical relevance.

Therefore, it is natural to turn to structural properties of the input graph, in order to identify cases where the problem can be solved efficiently. Specifically, we are interested in $\operatorname{\mathsf{FPT}}$ algorithms for $\operatorname{\mathsf{STP}}$ under the respective parameter. Prior to this work, no such $\operatorname{\mathsf{FPT}}$ algorithms were known. In fact, for treewidth this is highly unlikely. $\operatorname{\mathsf{STP}}$ has Integer 2-Commodity Flow as a special case [1], and this problem has recently been shown to be $\operatorname{\mathsf{W}[1]\text{-hard}}$ parameterized by treewidth [2]. Thus, $\operatorname{\mathsf{STP}}$ is also $\operatorname{\mathsf{W}[1]\text{-hard}}$ parameterized by treewidth, even on instances where the terminal set $T$ contains just three vertices.

To identify regimes where $\operatorname{\mathsf{FPT}}$ algorithms for $\operatorname{\mathsf{STP}}$ are feasible, we first turn our attention to the closely related Edge-Disjoint Paths ( $\operatorname{\mathsf{EDP}}$ ) problem. An $\operatorname{\mathsf{EDP}}$ instance is a tuple $(G,\mathcal{T})$ , where $G$ is a graph and $\mathcal{T}\subseteq\binom{V(G)}{2}$ is a set of terminal pairs in $V(G)$ . The task is to decide whether for each $\{u,v\}\in\mathcal{T}$ there is an $u v$ -path $P_{uv}$ in $G$ such that all $\{P_{uv}\}_{\{u,v\}\in\mathcal{T}}$ are pairwise edge-disjoint. This problem is $\operatorname{\mathsf{FPT}}$ when parameterized by ${\mathchoice{\left|\mathcal{T}\right|}{{|\mathcal{T}|}}{{|\mathcal{T}|}}{{|% \mathcal{T}|}}}$ [26]. However, it is notoriously hard with respect to common structural parameters. In fact, $\operatorname{\mathsf{EDP}}$ is $\operatorname{\mathsf{NP}\text{-hard}}$ even on complete bipartite graphs where one side contains 3 vertices [10]. These graphs have a vertex cover of size 3, which rules out $\operatorname{\mathsf{FPT}}$ algorithms for $\operatorname{\mathsf{EDP}}$ parameterized by any of the following classical structural parameters unless $\operatorname{\mathsf{P}}=\operatorname{\mathsf{NP}}$ : treewidth, fracture number¹¹1Fracture number is equivalent to another parameter called vertex integrity., size of the smallest feedback vertex set, size of the smallest vertex cover.

Still, there are several $\operatorname{\mathsf{FPT}}$ algorithms known for $\operatorname{\mathsf{EDP}}$ . They fall in two categories. The first category are $\operatorname{\mathsf{FPT}}$ algorithms with respect to structural parameters that are based on edge-cuts, like slim tree-cut width, rather than vertex-cuts, like treewidth [13, 12, 3, 14]. The second category of $\operatorname{\mathsf{FPT}}$ algorithms are based on structural parameters, considered not with respect to the host graph $G$ , but rather to the augmented graph $G+\mathcal{T}$ , where an edge is inserted between every terminal pair [14]. Intuitively, this captures the relations between the terminal pairs directly in the graph structure. This allows for positive results. For example, $\operatorname{\mathsf{EDP}}$ is $\operatorname{\mathsf{NP}\text{-hard}}$ for graphs of fracture number 3, but fixed-parameter tractable by fracture number of the augmented graph [14]. However, these results for $\operatorname{\mathsf{EDP}}$ carry little direct implication for $\operatorname{\mathsf{STP}}$ , as there is no simple reduction known between instances of one problem to the other.

In order to provide a unified perspective on both $\operatorname{\mathsf{STP}}$ and $\operatorname{\mathsf{EDP}}$ , we consider the following Generalized Steiner Tree Packing ( $\operatorname{\mathsf{GSTP}}$ ) problem, which can be seen as a version of $\operatorname{\mathsf{STP}}$ with multiple terminal sets. Formally, in $\operatorname{\mathsf{GSTP}}$ we are given a triple $(G,\mathcal{T},d)$ , where $G$ is the underlying graph, $\mathcal{T}\subseteq 2^{V(G)}$ is the set of terminal sets, and $d\colon\mathcal{T}\to\operatorname{\mathbb{N}}^{+}$ gives the demand for each terminal set. Our task is to decide whether there is a set of pairwise edge-disjoint, connected subgraphs $\mathcal{F}$ of $G$ and an assignment function $\pi\colon\mathcal{F}\to\mathcal{T}$ such that every solution subgraph $F\in\mathcal{F}$ is assigned to a terminal set $\pi(F)$ , which is contained in $F$ (i.e., $\pi(F)\subseteq V(F)$ ). Additionally, for every terminal set $T\in\mathcal{T}$ , the assignment function needs to assign $d(T)$ many solution subgraphs to $T$ . The $\operatorname{\mathsf{GSTP}}$ problem is not only a natural generalization of both $\operatorname{\mathsf{STP}}$ and $\operatorname{\mathsf{EDP}}$ , but was also studied directly, e.g., in the area of VLSI design [17, 22, 7]. Note that in the literature both $\operatorname{\mathsf{STP}}$ and $\operatorname{\mathsf{GSTP}}$ are often referred to as “Steiner tree packing”; throughout this work, we stick to the formal definitions of $\operatorname{\mathsf{STP}}$ and $\operatorname{\mathsf{GSTP}}$ as above, in order to avoid ambiguity.

Our contribution.

In this paper, we generalize all known $\operatorname{\mathsf{FPT}}$ algorithms for $\operatorname{\mathsf{EDP}}$ parameterized by structural parameters to $\operatorname{\mathsf{GSTP}}$ , which greatly extends the applicability of the underlying techniques. In particular, this allows us to apply them to $\operatorname{\mathsf{STP}}$ . Moreover, in doing so, we discover new $\operatorname{\mathsf{FPT}}$ algorithms for $\operatorname{\mathsf{EDP}}$ . We positively settle the open question, whether $\operatorname{\mathsf{EDP}}$ is $\operatorname{\mathsf{FPT}}$ with respect to the tree-cut width of the augmented graph in the affirmative. Finally, we also improve the running time of several known $\operatorname{\mathsf{FPT}}$ algorithms for $\operatorname{\mathsf{EDP}}$ . See an overview of our results in comparison to previously known results in Table 1.

Table 1: The parameterized complexity of

\operatorname{\mathsf{STP}}

,

\operatorname{\mathsf{EDP}}

, and

\operatorname{\mathsf{GSTP}}

with respect to structural parameters of the host graph or the augmented graph. See Section 2 for parameter definitions. The value

D

is the sum of demands. New results are highlighted with the symbol

\bigstar

, results where we improve the running time are highlighted with

. We abbreviate -hard with -h.

	$\operatorname{\mathsf{STP}}$		${\operatorname{\mathsf{EDP}}}$		${\operatorname{\mathsf{GSTP}}}$
	Host	Aug.	Host	Aug.	Host	Aug.
$\operatorname{tw}$	$\operatorname{\mathsf{W}[1]\text{-h}}1h$		$\operatorname{\mathsf{paraNP}\text{-h}}$	$\operatorname{\mathsf{W}[1]\text{-h}}1h$	$\operatorname{\mathsf{paraNP}\text{-h}}$	$\operatorname{\mathsf{W}[1]\text{-h}}1h$
	[1, 2]		[10]	[14]	[10]	[14]
$\operatorname{tw}+D$	$\operatorname{\mathsf{FPT}}$ $\bigstar$		$\operatorname{\mathsf{FPT}}$		$\operatorname{\mathsf{FPT}}$ $\bigstar$
	Theorem 30		Theorem 30		Theorem 30
$\operatorname{fn}$	$\operatorname{\mathsf{FPT}}$ $\bigstar$		$\operatorname{\mathsf{paraNP}\text{-h}}$	$\operatorname{\mathsf{FPT}}$	$\operatorname{\mathsf{paraNP}\text{-h}}$	$\operatorname{\mathsf{FPT}}$ $\bigstar$
	Theorem 13		[10]	Theorem 13	[10]	Theorem 13
$\operatorname{tcw}$	$\operatorname{\mathsf{FPT}}$ $\bigstar$		$\operatorname{\mathsf{W}[1]\text{-h}}1h$	$\operatorname{\mathsf{FPT}}$ $\bigstar$	$\operatorname{\mathsf{W}[1]\text{-h}}1h$	$\operatorname{\mathsf{FPT}}$ $\bigstar$
	Corollary 31		[13]	Corollary 28	[13]	Corollary 28
$\operatorname{stcw}$	$\operatorname{\mathsf{FPT}}$ $\bigstar$		$\operatorname{\mathsf{FPT}}$		$\operatorname{\mathsf{FPT}}$ $\bigstar$
	Corollary 21		[12, 3]		Corollary 21

Overview and structure.

This paper is structured as follows. We start in Section 2 by introducing relevant definitions and notation. In Section 3, we extend the notion of augmentation from $\operatorname{\mathsf{EDP}}$ to $\operatorname{\mathsf{GSTP}}$ . To the best of our knowledge, such a generalization was not studied before. We argue that among two natural approaches, one is strictly more general, and we settle on it for the remainder of this paper.

Building on this definition, we show in Section 4 that $\operatorname{\mathsf{GSTP}}$ is $\operatorname{\mathsf{FPT}}$ parameterized by the fracture number of the augmented graph. This result directly applies to $\operatorname{\mathsf{STP}}$ parameterized by the fracture number of the host graph. This is in stark contrast to the fact, that $\operatorname{\mathsf{EDP}}$ , and therefore $\operatorname{\mathsf{GSTP}}$ , is $\operatorname{\mathsf{paraNP}\text{-hard}}$ parameterized by the fracture number of the host graph [10]. The running time we obtain is doubly exponential in the parameter. This improves upon the triply exponential running time obtained by Ganian et al. [14] for $\operatorname{\mathsf{EDP}}$ parameterized by the fracture number of the augmented graph.

We then focus on results using tree-cut decompositions in Section 5. First, we define an additional property for tree-cut decompositions, which we call being simple. We use this property to streamline our algorithms on tree-cut decompositions, which we believe might be of independent interest. Then, we show how to decide an instance of $\operatorname{\mathsf{GSTP}}$ given a simple tree-cut decomposition. For tree-cut decompositions, we are interested in two measures of the decomposition, its width and slim width, where the former is bounded by a function of the latter. We then show how the latter result can be applied to obtain an $\operatorname{\mathsf{FPT}}$ algorithm parameterized by the slim tree-cut width of the host graph and the tree-cut width of the augmented graph. This directly implies that $\operatorname{\mathsf{EDP}}$ is $\operatorname{\mathsf{FPT}}$ by the tree-cut width of the augmented graph, which was not known before.

Augmentation of a single terminal set can increase the tree-cut width arbitrarily. So, the previous result does not directly translate to an $\operatorname{\mathsf{FPT}}$ algorithm for $\operatorname{\mathsf{STP}}$ . In Section 6, we examine this further. We show that we can avoid this hurdle, and provide an $\operatorname{\mathsf{FPT}}$ algorithm for $\operatorname{\mathsf{STP}}$ parameterized by tree-cut width of the host graph. This result combines most of the other results obtained in this paper. To achieve this, we use a win-win strategy by the size of the terminal set. If the size of the terminal set is small, then augmentation does not increase the tree-cut width much, and we apply the result obtained in Section 5. Otherwise, we show that we can assume the demand to be small. We then develop an $\operatorname{\mathsf{FPT}}$ algorithm for $\operatorname{\mathsf{GSTP}}$ parameterized by the sum of treewidth and demand. As treewidth dominates tree-cut width, this $\operatorname{\mathsf{FPT}}$ algorithm can be used to solve the remaining case. Additionally, this $\operatorname{\mathsf{FPT}}$ algorithm directly applies to $\operatorname{\mathsf{EDP}}$ parameterized by the sum of treewidth and the number of terminal pairs improving the previously known running time [29].

Omitted proofs.

Due to space constraints, proofs are omitted from this extended abstract. They were provided to the reviewers and can be found in the full version of this paper [18].

2 Preliminaries

We denote the natural numbers by $\operatorname{\mathbb{N}}=\{0,1,2,\dots\}$ and the positive natural numbers by $\operatorname{\mathbb{N}}^{+}$ . Let $k\in\operatorname{\mathbb{N}}$ , let ${\mathchoice{\left[k\right]}{[k]}{[k]}{[k]}}\coloneqq\{1,2,\dots,k\}$ and ${\mathchoice{\left[k\right]_{0}}{[k]_{0}}{[k]_{0}}{[k]_{0}}}=\{0\}\cup{% \mathchoice{\left[k\right]}{[k]}{[k]}{[k]}}$ . For any set $S$ , we denote with $2^{S}$ its power-set. Let $G$ be a graph. Unless explicitly stated otherwise, we only consider simple graphs. Let $S\subseteq V(G)$ , we refer to the edges with exactly one endpoint in $S$ by ${\mathchoice{\operatorname{\delta}_{G}\left(S\right)}{\operatorname{\delta}_{G% }(S)}{\operatorname{\delta}_{G}(S)}{\operatorname{\delta}_{G}(S)}}$ . Let $uv\in E(G)$ , contracting $u v$ merges $u$ and $v$ into a single vertex, while keeping vertices adjacent to $u$ or $v$ adjacent to the combined vertex. Similarly, contracting a vertex set $S\subseteq V(G)$ merges all the vertices in $S$ into a single vertex, while keeping vertices adjacent to at least one vertex of $S$ adjacent to the new vertex. Let $v\in V(G)$ , suppressing $v$ is the operation of inserting edges between all neighbors of $v$ and removing $v$ . The set of maximally connected subgraphs of $G$ is denoted with ${\mathchoice{\operatorname{comp}\left(G\right)}{\operatorname{comp}(G)}{% \operatorname{comp}(G)}{\operatorname{comp}(G)}}$ . Let $H$ be a hypergraph. $H$ is minimally connected if we can remove no hyperedge while preserving connectivity.

Now, we give the definitions of the structural parameters that we consider. For any parameter that is based on a decomposition, which contains a graph $G^{\prime}$ on vertex-sets of $G$ , we refer to the vertices of $G^{\prime}$ as nodes or bags and to its edges by links.

Fracture Number.

Let $S\subseteq V(G)$ . We call $S$ a fracture modulator if every component in $G-S$ contains at most ${\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}$ vertices. The size of the smallest fracture modulator is called the fracture number ${\mathchoice{\operatorname{fn}\left(G\right)}{\operatorname{fn}(G)}{% \operatorname{fn}(G)}{\operatorname{fn}(G)}}$ of $G$ . Dvorák et al. [9] claim that for any graph $H$ , one can find a fracture modulator of minimal size in time ${\mathchoice{\operatorname{\mathcal{O}}\left(({\mathchoice{\operatorname{fn}% \left(H\right)}{\operatorname{fn}(H)}{\operatorname{fn}(H)}{\operatorname{fn}(% H)}}+1)^{{\mathchoice{\operatorname{fn}\left(H\right)}{\operatorname{fn}(H)}{% \operatorname{fn}(H)}{\operatorname{fn}(H)}}}{\mathchoice{\left|E(H)\right|}{{% |E(H)|}}{{|E(H)|}}{{|E(H)|}}}\right)}{\operatorname{\mathcal{O}}(({\mathchoice% {\operatorname{fn}\left(H\right)}{\operatorname{fn}(H)}{\operatorname{fn}(H)}{% \operatorname{fn}(H)}}+1)^{{\mathchoice{\operatorname{fn}\left(H\right)}{% \operatorname{fn}(H)}{\operatorname{fn}(H)}{\operatorname{fn}(H)}}}{% \mathchoice{\left|E(H)\right|}{{|E(H)|}}{{|E(H)|}}{{|E(H)|}}})}{\operatorname{% \mathcal{O}}(({\mathchoice{\operatorname{fn}\left(H\right)}{\operatorname{fn}(% H)}{\operatorname{fn}(H)}{\operatorname{fn}(H)}}+1)^{{\mathchoice{% \operatorname{fn}\left(H\right)}{\operatorname{fn}(H)}{\operatorname{fn}(H)}{% \operatorname{fn}(H)}}}{\mathchoice{\left|E(H)\right|}{{|E(H)|}}{{|E(H)|}}{{|E% (H)|}}})}{\operatorname{\mathcal{O}}(({\mathchoice{\operatorname{fn}\left(H% \right)}{\operatorname{fn}(H)}{\operatorname{fn}(H)}{\operatorname{fn}(H)}}+1)% ^{{\mathchoice{\operatorname{fn}\left(H\right)}{\operatorname{fn}(H)}{% \operatorname{fn}(H)}{\operatorname{fn}(H)}}}{\mathchoice{\left|E(H)\right|}{{% |E(H)|}}{{|E(H)|}}{{|E(H)|}}})}}$ . We note that their proof suffers from a minor inaccuracy, and present a corrected version that runs in time ${\mathchoice{\operatorname{\mathcal{O}}\left((2{\mathchoice{\operatorname{fn}% \left(H\right)}{\operatorname{fn}(H)}{\operatorname{fn}(H)}{\operatorname{fn}(% H)}}-1)^{{\mathchoice{\operatorname{fn}\left(H\right)}{\operatorname{fn}(H)}{% \operatorname{fn}(H)}{\operatorname{fn}(H)}}}{\mathchoice{\left|V(H)\right|}{{% |V(H)|}}{{|V(H)|}}{{|V(H)|}}}\right)}{\operatorname{\mathcal{O}}((2{% \mathchoice{\operatorname{fn}\left(H\right)}{\operatorname{fn}(H)}{% \operatorname{fn}(H)}{\operatorname{fn}(H)}}-1)^{{\mathchoice{\operatorname{fn% }\left(H\right)}{\operatorname{fn}(H)}{\operatorname{fn}(H)}{\operatorname{fn}% (H)}}}{\mathchoice{\left|V(H)\right|}{{|V(H)|}}{{|V(H)|}}{{|V(H)|}}})}{% \operatorname{\mathcal{O}}((2{\mathchoice{\operatorname{fn}\left(H\right)}{% \operatorname{fn}(H)}{\operatorname{fn}(H)}{\operatorname{fn}(H)}}-1)^{{% \mathchoice{\operatorname{fn}\left(H\right)}{\operatorname{fn}(H)}{% \operatorname{fn}(H)}{\operatorname{fn}(H)}}}{\mathchoice{\left|V(H)\right|}{{% |V(H)|}}{{|V(H)|}}{{|V(H)|}}})}{\operatorname{\mathcal{O}}((2{\mathchoice{% \operatorname{fn}\left(H\right)}{\operatorname{fn}(H)}{\operatorname{fn}(H)}{% \operatorname{fn}(H)}}-1)^{{\mathchoice{\operatorname{fn}\left(H\right)}{% \operatorname{fn}(H)}{\operatorname{fn}(H)}{\operatorname{fn}(H)}}}{% \mathchoice{\left|V(H)\right|}{{|V(H)|}}{{|V(H)|}}{{|V(H)|}}})}}$ , see Appendix A of the full version for details. Fracture number is always at most a factor of two away from another parameter called vertex integrity.

Tree-Cut Width.

The parameter tree-cut width was introduced by Wollan [27].

Definition 1.

A tree-cut decomposition of a graph $G$ is a tuple $\mathcal{D}\coloneqq(T,\mathcal{X})$ , where $T$ is a rooted tree and $\{X_{s}\subseteq V(G)\mid s\in V(T)\}\coloneqq\mathcal{X}$ a near-partition of $V(G)$ .

Here, subsets in a near-partition may be empty, as opposed to a partition. For a node $t\in V(T)$ , let $T_{t}^{\mathcal{D}}$ be the sub-tree rooted at $t$ and we set $Y_{t}^{\mathcal{D}}\coloneqq\bigcup_{s\in T_{t}^{\mathcal{D}}}X_{s}$ to be the vertices contained in the bags of $T_{t}^{\mathcal{D}}$ . Let ${\mathchoice{\operatorname{\partial}_{t}}{\operatorname{\partial}_{t}}{% \operatorname{\partial}_{t}}{\operatorname{\partial}_{t}}}\coloneqq G[{% \mathchoice{\operatorname{\delta}\left(Y^{\mathcal{D}}_{t}\right)}{% \operatorname{\delta}(Y^{\mathcal{D}}_{t})}{\operatorname{\delta}(Y^{\mathcal{% D}}_{t})}{\operatorname{\delta}(Y^{\mathcal{D}}_{t})}}]$ be the graph induced by all edges crossing the link between $t$ and its parent, which we refer to as the boundary at $t$ . The adhesion ${\mathchoice{\operatorname{adh}_{\mathcal{D}}\left(t\right)}{\operatorname{adh% }_{\mathcal{D}}(t)}{\operatorname{adh}_{\mathcal{D}}(t)}{\operatorname{adh}_{% \mathcal{D}}(t)}}$ of $t$ is defined as ${\mathchoice{\left|E({\mathchoice{\operatorname{\partial}_{t}}{\operatorname{% \partial}_{t}}{\operatorname{\partial}_{t}}{\operatorname{\partial}_{t}}})% \right|}{{|E({\mathchoice{\operatorname{\partial}_{t}}{\operatorname{\partial}% _{t}}{\operatorname{\partial}_{t}}{\operatorname{\partial}_{t}}})|}}{{|E({% \mathchoice{\operatorname{\partial}_{t}}{\operatorname{\partial}_{t}}{% \operatorname{\partial}_{t}}{\operatorname{\partial}_{t}}})|}}{{|E({% \mathchoice{\operatorname{\partial}_{t}}{\operatorname{\partial}_{t}}{% \operatorname{\partial}_{t}}{\operatorname{\partial}_{t}}})|}}}$ .

The torso of a tree-cut decomposition at node $t$ , denoted as $H_{t}^{\mathcal{D}}$ , is the graph obtained from $G$ as follows. Consider the connected components of $T-t$ and for each $C\in{\mathchoice{\operatorname{comp}\left(T-t\right)}{\operatorname{comp}(T-t)% }{\operatorname{comp}(T-t)}{\operatorname{comp}(T-t)}}$ , define $Z_{C}\coloneqq\bigcup_{s\in V(C)}X_{s}$ . The torso at $t$ is obtained from $G$ by contracting for all $C\in{\mathchoice{\operatorname{comp}\left(T-t\right)}{\operatorname{comp}(T-t)% }{\operatorname{comp}(T-t)}{\operatorname{comp}(T-t)}}$ the sets $Z_{C}$ into a single vertex $z_{C}$ . Note that this may create parallel edges. Consider the unique graph $\tilde{H}_{t}^{\mathcal{D}}$ , obtained from $H_{t}^{\mathcal{D}}$ , by repeatedly suppressing vertices not in $X_{t}$ of degree at most $2$ and removing loops. $\tilde{H}_{t}^{\mathcal{D}}$ is called the 3-center of $H_{t}^{\mathcal{D}}$ with respect to $X_{t}$ .

Definition 2.

The width of the tree-cut decomposition is

\max\left(\left\{{\mathchoice{\operatorname{adh}\left(s\right)}{\operatorname{% adh}(s)}{\operatorname{adh}(s)}{\operatorname{adh}(s)}}\right\}_{s\in V(T)}% \cup\left\{{\mathchoice{\left|V(\tilde{H}_{s}^{\mathcal{D}})\right|}{{|V(% \tilde{H}_{s}^{\mathcal{D}})|}}{{|V(\tilde{H}_{s}^{\mathcal{D}})|}}{{|V(\tilde% {H}_{s}^{\mathcal{D}})|}}}\right\}_{s\in V(T)}\right).

The tree-cut width ${\mathchoice{\operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{% \operatorname{tcw}(G)}{\operatorname{tcw}(G)}}$ of $G$ is the smallest width of a tree-cut decomposition. We call $t$ empty if $X_{t}=\emptyset$ and we denote with ${\mathchoice{\operatorname{chil}\left(t\right)}{\operatorname{chil}(t)}{% \operatorname{chil}(t)}{\operatorname{chil}(t)}}$ the set of children of $t$ in $T$ . We call $t$ thin if ${\mathchoice{\operatorname{adh}_{\mathcal{D}}\left(t\right)}{\operatorname{adh% }_{\mathcal{D}}(t)}{\operatorname{adh}_{\mathcal{D}}(t)}{\operatorname{adh}_{% \mathcal{D}}(t)}}\leq 2$ and bold otherwise. The set of thin children is denoted by ${\mathchoice{\operatorname{t\text{-}chil}_{\mathcal{D}}\left(t\right)}{% \operatorname{t\text{-}chil}_{\mathcal{D}}(t)}{\operatorname{t\text{-}chil}_{% \mathcal{D}}(t)}{\operatorname{t\text{-}chil}_{\mathcal{D}}(t)}}$ and the set of bold children as ${\mathchoice{\operatorname{b\text{-}chil}_{\mathcal{D}}\left(t\right)}{% \operatorname{b\text{-}chil}_{\mathcal{D}}(t)}{\operatorname{b\text{-}chil}_{% \mathcal{D}}(t)}{\operatorname{b\text{-}chil}_{\mathcal{D}}(t)}}$ . A tree-cut decomposition is nice, if for all thin nodes $t$ the sets $N_{G}(Y_{t})$ and $\bigcup_{s\text{ is a sibling of }t}Y_{s}^{\mathcal{D}}$ are disjoint. Any tree-cut decomposition can be transformed into a nice tree-cut decomposition in cubic time [11]. In all notation we leave off the tree-cut decomposition, if it is clear from context. For every graph $G$ , we can compute a tree-cut decomposition of width at most $2{\mathchoice{\operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{% \operatorname{tcw}(G)}{\operatorname{tcw}(G)}}$ in time $2^{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\operatorname{tcw}% \left(G\right)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)}{\operatorname{% tcw}(G)}}^{2}\log{\mathchoice{\operatorname{tcw}\left(G\right)}{\operatorname{% tcw}(G)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)}}\right)}{\operatorname{% \mathcal{O}}({\mathchoice{\operatorname{tcw}\left(G\right)}{\operatorname{tcw}% (G)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)}}^{2}\log{\mathchoice{% \operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)% }{\operatorname{tcw}(G)}})}{\operatorname{\mathcal{O}}({\mathchoice{% \operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)% }{\operatorname{tcw}(G)}}^{2}\log{\mathchoice{\operatorname{tcw}\left(G\right)% }{\operatorname{tcw}(G)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)}})}{% \operatorname{\mathcal{O}}({\mathchoice{\operatorname{tcw}\left(G\right)}{% \operatorname{tcw}(G)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)}}^{2}\log{% \mathchoice{\operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{% \operatorname{tcw}(G)}{\operatorname{tcw}(G)}})}}{\mathchoice{\left|V(G)\right% |}{{|V(G)|}}{{|V(G)|}}{{|V(G)|}}}^{2}$ [20].

Slim Tree-Cut Width.

The slim tree-cut width is defined similarly to tree-cut width. Consider a tree-cut decomposition $\mathcal{D}=(T,\mathcal{X})$ and $t\in V(T)$ . Define the 2-center $\tilde{H}^{2;\mathcal{D}}_{t}$ of $H^{\mathcal{D}}_{t}$ with respect to $X_{t}$ analogous to the 3-center, while only suppressing vertices of degree at most 1.

Definition 3.

The slim width of $\mathcal{D}$ is defined to be

\max\left(\left\{{\mathchoice{\operatorname{adh}\left(t\right)}{\operatorname{% adh}(t)}{\operatorname{adh}(t)}{\operatorname{adh}(t)}}\right\}_{s\in V(T)}% \cup\left\{{\mathchoice{\left|V(\tilde{H}^{2,\mathcal{D}}_{s})\right|}{{|V(% \tilde{H}^{2,\mathcal{D}}_{s})|}}{{|V(\tilde{H}^{2,\mathcal{D}}_{s})|}}{{|V(% \tilde{H}^{2,\mathcal{D}}_{s})|}}}\right\}_{s\in V(T)}\right).

The slim tree-cut width ${\mathchoice{\operatorname{stcw}\left(G\right)}{\operatorname{stcw}(G)}{% \operatorname{stcw}(G)}{\operatorname{stcw}(G)}}$ of $G$ is the smallest slim width of any tree-cut decomposition of $G$ . Ganian et al. [12] provide an algorithm that, given a graph $G$ , computes a tree-cut decomposition of slim width at most $6({\mathchoice{\operatorname{stcw}\left(G\right)}{\operatorname{stcw}(G)}{% \operatorname{stcw}(G)}{\operatorname{stcw}(G)}}+1)^{3}$ in time $2^{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\operatorname{stcw% }\left(G\right)}{\operatorname{stcw}(G)}{\operatorname{stcw}(G)}{\operatorname% {stcw}(G)}}^{2}\log{\mathchoice{\operatorname{stcw}\left(G\right)}{% \operatorname{stcw}(G)}{\operatorname{stcw}(G)}{\operatorname{stcw}(G)}}\right% )}{\operatorname{\mathcal{O}}({\mathchoice{\operatorname{stcw}\left(G\right)}{% \operatorname{stcw}(G)}{\operatorname{stcw}(G)}{\operatorname{stcw}(G)}}^{2}% \log{\mathchoice{\operatorname{stcw}\left(G\right)}{\operatorname{stcw}(G)}{% \operatorname{stcw}(G)}{\operatorname{stcw}(G)}})}{\operatorname{\mathcal{O}}(% {\mathchoice{\operatorname{stcw}\left(G\right)}{\operatorname{stcw}(G)}{% \operatorname{stcw}(G)}{\operatorname{stcw}(G)}}^{2}\log{\mathchoice{% \operatorname{stcw}\left(G\right)}{\operatorname{stcw}(G)}{\operatorname{stcw}% (G)}{\operatorname{stcw}(G)}})}{\operatorname{\mathcal{O}}({\mathchoice{% \operatorname{stcw}\left(G\right)}{\operatorname{stcw}(G)}{\operatorname{stcw}% (G)}{\operatorname{stcw}(G)}}^{2}\log{\mathchoice{\operatorname{stcw}\left(G% \right)}{\operatorname{stcw}(G)}{\operatorname{stcw}(G)}{\operatorname{stcw}(G% )}})}}{\mathchoice{\left|V(G)\right|}{{|V(G)|}}{{|V(G)|}}{{|V(G)|}}}^{4}$ .

To give perspective on the different parameters considered in this work, we note that treewidth dominates tree-cut width (i.e., bounded tree-cut width implies bounded treewidth) and fracture number, and tree-cut width dominates slim tree-cut width, while (slim) tree-cut width is incomparable with fracture number. We remark that all these parameters model sparse graphs; formally, $n$ -vertex graphs where the parameter is bounded have ${\mathchoice{\operatorname{\mathcal{O}}\left(n\right)}{\operatorname{\mathcal{% O}}(n)}{\operatorname{\mathcal{O}}(n)}{\operatorname{\mathcal{O}}(n)}}$ edges.

3 Augmentation for GSTP

The augmented graph for an instance $(G,\mathcal{T})$ of $\operatorname{\mathsf{EDP}}$ is defined to be $G$ with all terminal pairs connected. That is, the augmented graph ${G}^{\mathcal{T}}$ is exactly $G+\mathcal{T}$ . To extend this notion to an instance $(G,\mathcal{T},d)$ of $\operatorname{\mathsf{GSTP}}$ , we consider two different approaches. The clique-augmented graph $G^{\mathrm{cliq}(\mathcal{T})}$ is obtained from $G$ by adding for all $T\in\mathcal{T}$ an edge between every pair of vertices in $T$ . If an edge, that added this way was already present, we obtain parallel edges. As there is a reduction for $\operatorname{\mathsf{EDP}}$ ensuring that all terminals are unique degree one vertices [10], this definition matches the definition for $\operatorname{\mathsf{EDP}}$ very closely. On the other hand, the vertex-augmented graph $G^{\mathrm{vert}(\mathcal{T})}$ is obtained from $G$ by considering each $T\in\mathcal{T}$ and adding a new vertex ${\mathchoice{\operatorname{aug}\left(T\right)}{\operatorname{aug}(T)}{% \operatorname{aug}(T)}{\operatorname{aug}(T)}}$ to the graph, which is adjacent to all vertices of $T$ .

We compare these two definitions for the parameters treewidth, feedback vertex set number, fracture number, vertex cover number, tree-cut width, slim tree-cut width, feedback edge number, and the sum of treewidth and maximum degree. Let $\kappa$ be any of these parameters except vertex cover number. Then, we can bound $\kappa(G^{\mathrm{vert}(\mathcal{T})})$ by a function of $\kappa(G^{\mathrm{cliq}(\mathcal{T})})$ . For the sum of treewidth and maximum degree, the reverse is possible as well. For the other parameters, the reverse is not possible. For the vertex cover number, there is no function bounding in either direction. In other words, $\operatorname{\mathsf{FPT}}$ algorithms considering the vertex-augmented graph are almost always more general than those considering the clique-augmented graph, with respect to the parameters considered in this paper. Therefore, we focus on the vertex augmented graph, which, from now on, we call simply the augmented graph, and denote this graph by ${G}^{\mathcal{T}}$ .

4 GSTP by Augmented Fracture Number

In this section, we lay out our result that $\operatorname{\mathsf{GSTP}}$ is $\operatorname{\mathsf{FPT}}$ when parameterized by the fracture number of the augmented graph. Let $X$ be a fracture modulator of ${G}^{\mathcal{T}}$ . We achieve this result by showing an equivalence characterization of the components of ${G}^{\mathcal{T}}-X$ , which allows us to construct an equivalent ILP instance where number of variables is bounded by a function of ${\mathchoice{\left|X\right|}{{|X|}}{{|X|}}{{|X|}}}$ . A similar result is known for $\operatorname{\mathsf{EDP}}$ [14]. We generalize this significantly, while improving the running time from triply exponential to doubly exponential.

Consider any $U\subseteq V({G}^{\mathcal{T}})$ , we call the set of all $T\in\mathcal{T}$ with ${\mathchoice{\operatorname{aug}\left(T\right)}{\operatorname{aug}(T)}{% \operatorname{aug}(T)}{\operatorname{aug}(T)}}\in U$ by $\mathcal{T}_{U}$ . Let $C\in{\mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-X\right)}{% \operatorname{comp}({G}^{\mathcal{T}}-X)}{\operatorname{comp}({G}^{\mathcal{T}% }-X)}{\operatorname{comp}({G}^{\mathcal{T}}-X)}}$ . To better assess, which terminal sets might need special attention, we only consider fracture modulators with a particular structure.

Definition 4.

Let $X\subseteq V({G}^{\mathcal{T}})$ be a fracture modulator of ${G}^{\mathcal{T}}$ . We call $X$ nice, if

1.

$G[X]$ is edgeless,
2.

for each terminal set $T\in\mathcal{T}_{X}$ , there exist two distinct components $C,C^{\prime}\in{\mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-X\right% )}{\operatorname{comp}({G}^{\mathcal{T}}-X)}{\operatorname{comp}({G}^{\mathcal% {T}}-X)}{\operatorname{comp}({G}^{\mathcal{T}}-X)}}$ with $V(C)\cap T\neq\emptyset$ and $V(C^{\prime})\cap T\neq\emptyset$ .

Note that even though $G[X]$ is edgeless, ${G}^{\mathcal{T}}[X]$ may contain edges. We show that we can always turn a fracture modulator into a nice fracture modulator of similar size.

Lemma 5.

Let $\mathscr{P}\coloneq(G,\mathcal{T},d)$ be an instance of $\operatorname{\mathsf{GSTP}}$ and $X$ be a fracture modulator of ${G}^{\mathcal{T}}$ . In linear time, one can construct an equivalent instance $\mathscr{P}^{\prime}=(G^{\prime},\mathcal{T},d)$ and a nice fracture modulator $S$ of ${G^{\prime}}^{\mathcal{T}}$ with ${\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}\leq 2{\mathchoice{\left|X% \right|}{{|X|}}{{|X|}}{{|X|}}}$ and ${\mathchoice{\left|V(G^{\prime})\right|}{{|V(G^{\prime})|}}{{|V(G^{\prime})|}}% {{|V(G^{\prime})|}}}\leq{\mathchoice{\left|V(G)\right|}{{|V(G)|}}{{|V(G)|}}{{|% V(G)|}}}+\binom{{\mathchoice{\left|X\right|}{{|X|}}{{|X|}}{{|X|}}}}{2}+2{% \mathchoice{\left|X\right|}{{|X|}}{{|X|}}{{|X|}}}$ .

From now on, we assume that $S$ is a nice fracture modulator for $(G,\mathcal{T},d)$ . Each terminal set $T$ has its augmented vertex ${\mathchoice{\operatorname{aug}\left(T\right)}{\operatorname{aug}(T)}{% \operatorname{aug}(T)}{\operatorname{aug}(T)}}$ either in $S$ , meaning $T\in\mathcal{T}_{S}$ , or in some component $C\in{\mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-S\right)}{% \operatorname{comp}({G}^{\mathcal{T}}-S)}{\operatorname{comp}({G}^{\mathcal{T}% }-S)}{\operatorname{comp}({G}^{\mathcal{T}}-S)}}$ , in which case $T\in\mathcal{T}_{C}$ . We also denote with $\mathcal{T}^{\star}$ the set of all $T\in\mathcal{T}$ satisfying $T\subseteq S$ , note that $\mathcal{T}^{\star}\cap\mathcal{T}_{S}=\emptyset$ by Definition 4. After removing terminal sets $T$ with ${\mathchoice{\left|T\right|}{{|T|}}{{|T|}}{{|T|}}}<2$ , we reject any instance for which there is a $v\in V(G)$ such that ${\mathchoice{\operatorname{deg}_{G}\left(v\right)}{\operatorname{deg}_{G}(v)}{% \operatorname{deg}_{G}(v)}{\operatorname{deg}_{G}(v)}}<\sum_{T\in\mathcal{T}% \colon v\in T}d(T)$ . This implies for each $T\in\mathcal{T}\setminus\mathcal{T}^{\star}$ that $d(T)<2|S|$ , since the degree of any vertex outside of $S$ is less than $2|S|$ .

Component Configurations.

In order to fulfill the connectivity requirements, each component might need to use edges from other components, or other components might need to use edges from this component. Denote with $C^{+}\coloneqq{G}^{\mathcal{T}}[V(C)\cup S]$ the subgraph induced on the component and the fracture modulator. Based on this, we introduce the concept of a component-configuration characterizing how a component $C\in{\mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-S\right)}{% \operatorname{comp}({G}^{\mathcal{T}}-S)}{\operatorname{comp}({G}^{\mathcal{T}% }-S)}{\operatorname{comp}({G}^{\mathcal{T}}-S)}}$ can interact with the remaining instance. Let $u\coloneqq\binom{2{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}}{2}$ , so $C^{+}$ has at most $u$ edges, and define a configuration $\gamma$ of $C$ as a tuple $(\operatorname{dem}_{\gamma},\operatorname{supl}_{\gamma},\operatorname{assign% }_{\gamma})$ with $\operatorname{dem}_{\gamma},\operatorname{supl}_{\gamma}\colon 2^{S\cap V(G)}% \to{\mathchoice{\left[u\right]_{0}}{[u]_{0}}{[u]_{0}}{[u]_{0}}}$ and $\operatorname{assign}_{\gamma}\colon\mathcal{T}_{S}\times{\mathchoice{\left[2{% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}\right]}{[2{\mathchoice{\left% |S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[2{\mathchoice{\left|S\right|}{{|S|}}{{|S|}% }{{|S|}}}]}{[2{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}}\times{% \mathchoice{\left[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}\right]}{[% {\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{\left|S% \right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{% |S|}}}]}}\to 2^{S\cap V(G)}$ (if the configuration is clear from context, we omit the index $\gamma$ ).

Intuitively, the first part (i.e., $\operatorname{dem}$ ) signifies how often each subset of the fracture modulator gets connected by other components and used for the connection requirements of $\mathcal{T}_{C}$ – what is the additional demand for each subset? The second component (i.e., $\operatorname{supl}$ ) signifies how often each subset of the fracture modulator gets connected inside this component, but these connections are not used to satisfy connection requirements of terminal sets in $\mathcal{T}_{C}$ – what is the additional supply for each subset?

For the final part, consider a terminal set $T\in\mathcal{T}_{S}$ . We have $T\notin\mathcal{T}^{\star}$ ; so, $d(T)\leq 2|S|$ . This allows us to explicitly store the contribution of $C$ to every tree in the solution assigned to such a terminal set. This is necessary since $T$ can span an arbitrary number of components in ${G}^{\mathcal{T}}-S$ . For each $i\in{\mathchoice{\left[d(T)\right]}{[d(T)]}{[d(T)]}{[d(T)]}}$ , the information required for the $i$ -th tree assigned to $T$ is stored in ${\mathchoice{\operatorname{assign}\left(T,i,\cdot\right)}{\operatorname{assign% }(T,i,\cdot)}{\operatorname{assign}(T,i,\cdot)}{\operatorname{assign}(T,i,% \cdot)}}$ . Call this tree $F^{i}$ . Let $\sigma\colon{\mathchoice{\left[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|% }}}\right]}{[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{\left|S% \right|}{{|S|}}{{|S|}}{{|S|}}}]}}\to V(C)$ be a surjection. Then, we can imagine for all $j\in{\mathchoice{\left[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}% \right]}{[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{% \left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{\left|S\right|}{{|S|}}{{% |S|}}{{|S|}}}]}}$ that ${\mathchoice{\operatorname{assign}\left(T,i,j\right)}{\operatorname{assign}(T,% i,j)}{\operatorname{assign}(T,i,j)}{\operatorname{assign}(T,i,j)}}$ is a set of vertices in $S$ which $\sigma(j)$ can reach via $F^{i}[V(C^{+})]$ . Note that it might not be all such vertices.

Admitted Configurations.

Not every component can be in any configuration in a valid solution. For example, a component with $k$ edges can not supply more than $k$ connections to other components. To capture this concept, we say a component admits a configuration if it can locally satisfy all the requirements of the configuration and of the terminal sets in $\mathcal{T}_{C}$ . In order to make this rigorous, we construct an auxiliary instance of $\operatorname{\mathsf{GSTP}}$ to help us define when $C$ admits a configuration. For this, let $\sigma\colon{\mathchoice{\left[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|% }}}\right]}{[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{\left|S% \right|}{{|S|}}{{|S|}}{{|S|}}}]}}\to V(C)$ be a surjection, which we use to encode the $\operatorname{assign}$ mapping as explained above. The instance we construct is denoted by ${\mathchoice{\operatorname{confInst}\left(C,\gamma,\sigma\right)}{% \operatorname{confInst}(C,\gamma,\sigma)}{\operatorname{confInst}(C,\gamma,% \sigma)}{\operatorname{confInst}(C,\gamma\sigma)}}$ .

First, we define the host-graph of the instance ${\mathchoice{\operatorname{confInst}\left(C,\gamma,\sigma\right)}{% \operatorname{confInst}(C,\gamma,\sigma)}{\operatorname{confInst}(C,\gamma,% \sigma)}{\operatorname{confInst}(C,\gamma\sigma)}}$ . For this, we start with the graph $C^{+}$ and for each $Q\subseteq S\cap V(G)$ , we add ${\mathchoice{\operatorname{dem}\left(Q\right)}{\operatorname{dem}(Q)}{% \operatorname{dem}(Q)}{\operatorname{dem}(Q)}}$ -many vertices $v$ to the graph with $N(v)=Q$ . Denote this graph with $H$ .

Now, we define the terminal sets, that need to be connected. Denote for all $T\in\mathcal{T}_{S}$ , $i\in{\mathchoice{\left[d(T)\right]}{[d(T)]}{[d(T)]}{[d(T)]}}$ and $U\subseteq S\cap V(G)$ the set $A(T,i,U,\sigma)\coloneqq\{\sigma(j)\mid j\in{\mathchoice{\left[{\mathchoice{% \left|S\right|}{{|S|}}{{|S|}}{{|S|}}}\right]}{[{\mathchoice{\left|S\right|}{{|% S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}};{\mathchoice{% \operatorname{assign}\left(T,i,j\right)}{\operatorname{assign}(T,i,j)}{% \operatorname{assign}(T,i,j)}{\operatorname{assign}(T,i,j)}}=U\}$ the set of vertices in $C$ that is assigned to $U$ to satisfy connections for the $i$ -th tree of $T$ . Now let ${\mathchoice{\operatorname{assignSets}\left(T,i,\sigma\right)}{\operatorname{% assignSets}(T,i,\sigma)}{\operatorname{assignSets}(T,i,\sigma)}{\operatorname{% assignSets}(T,i,\sigma)}}\coloneqq\bigcup_{\emptyset\neq U\subseteq S\cap V(G)% \colon A(T,i,U,\sigma)\neq\emptyset}\{U\cup A(T,i,U,\sigma)\}$ be the subsets of $S\cap V(G)$ that get assigned some vertex unioned with the assigned vertices. Let

	$\displaystyle\mathcal{Q}$	$\displaystyle\coloneqq\{T\in\mathcal{T}_{C}\mid T\cap C\neq\emptyset\},$
	$\displaystyle\mathcal{S}$	$\displaystyle\coloneqq\{X\subseteq S\cap V(G)\mid{\mathchoice{\operatorname{% supl}\left(X\right)}{\operatorname{supl}(X)}{\operatorname{supl}(X)}{% \operatorname{supl}(X)}}>0\},$
	$\displaystyle\mathcal{A}$	$\displaystyle\coloneqq\bigcup_{T\in\mathcal{T}_{S},i\in{\mathchoice{\left[d(T)% \right]}{[d(T)]}{[d(T)]}{[d(T)]}}}{\mathchoice{\operatorname{assignSets}\left(% T,i,\sigma\right)}{\operatorname{assignSets}(T,i,\sigma)}{\operatorname{% assignSets}(T,i,\sigma)}{\operatorname{assignSets}(T,i,\sigma)}}.$

Note that if $C$ consists of exactly one augmented vertex, $\mathcal{Q}$ is empty; otherwise $\mathcal{Q}=\mathcal{T}_{C}$ . Further, the set $\mathcal{A}$ might intersect $Q$ , but one can verify that $\mathcal{S}$ is disjoint from $\mathcal{A}$ and $Q$ . The complete set of terminal sets, for which we need connections, is $\mathcal{U}\coloneqq Q\cup\mathcal{S}\cup\mathcal{A}$ .

Finally, we specify the number of required connections $d^{\prime}\colon\mathcal{U}\to\operatorname{\mathbb{N}}^{+}$ . For this extend $d,$ $\operatorname{supl}$ and $\operatorname{assign}$ to yield 0 or $\emptyset$ on arguments not in their original domain. For all $U\in\mathcal{U}$ let

d^{\prime}(U)\coloneqq d(U)+{\mathchoice{\operatorname{supl}\left(U\right)}{% \operatorname{supl}(U)}{\operatorname{supl}(U)}{\operatorname{supl}(U)}}+\sum_% {T\in\mathcal{T}_{S}}{\mathchoice{\left|\left\{i\in{\mathchoice{\left[d(T)% \right]}{[d(T)]}{[d(T)]}{[d(T)]}}\mid U\in{\mathchoice{\operatorname{% assignSets}\left(T,i,\sigma\right)}{\operatorname{assignSets}(T,i,\sigma)}{% \operatorname{assignSets}(T,i,\sigma)}{\operatorname{assignSets}(T,i,\sigma)}}% \right\}\right|}{{|\left\{i\in{\mathchoice{\left[d(T)\right]}{[d(T)]}{[d(T)]}{% [d(T)]}}\mid U\in{\mathchoice{\operatorname{assignSets}\left(T,i,\sigma\right)% }{\operatorname{assignSets}(T,i,\sigma)}{\operatorname{assignSets}(T,i,\sigma)% }{\operatorname{assignSets}(T,i,\sigma)}}\right\}|}}{{|\left\{i\in{\mathchoice% {\left[d(T)\right]}{[d(T)]}{[d(T)]}{[d(T)]}}\mid U\in{\mathchoice{% \operatorname{assignSets}\left(T,i,\sigma\right)}{\operatorname{assignSets}(T,% i,\sigma)}{\operatorname{assignSets}(T,i,\sigma)}{\operatorname{assignSets}(T,% i,\sigma)}}\right\}|}}{{|\left\{i\in{\mathchoice{\left[d(T)\right]}{[d(T)]}{[d% (T)]}{[d(T)]}}\mid U\in{\mathchoice{\operatorname{assignSets}\left(T,i,\sigma% \right)}{\operatorname{assignSets}(T,i,\sigma)}{\operatorname{assignSets}(T,i,% \sigma)}{\operatorname{assignSets}(T,i,\sigma)}}\right\}|}}},

and define ${\mathchoice{\operatorname{confInst}\left(C,\gamma,\sigma\right)}{% \operatorname{confInst}(C,\gamma,\sigma)}{\operatorname{confInst}(C,\gamma,% \sigma)}{\operatorname{confInst}(C,\gamma\sigma)}}=(H,\mathcal{U},d^{\prime})$ .

Definition 6.

We say a component $C\in{\mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-S\right)}{% \operatorname{comp}({G}^{\mathcal{T}}-S)}{\operatorname{comp}({G}^{\mathcal{T}% }-S)}{\operatorname{comp}({G}^{\mathcal{T}}-S)}}$ admits a configuration $\gamma$ , if there is a surjection $\sigma\colon{\mathchoice{\left[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|% }}}\right]}{[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{\left|S% \right|}{{|S|}}{{|S|}}{{|S|}}}]}}\to V(C)$ such that

1.

for all $T\in\mathcal{T_{S}}$ , $i\in{\mathchoice{\left[d(T)\right]}{[d(T)]}{[d(T)]}{[d(T)]}}$ , and $j\in\sigma^{-1}(T\cap V(C))$ , we have ${\mathchoice{\operatorname{assign}\left(T,i,j\right)}{\operatorname{assign}(T,% i,j)}{\operatorname{assign}(T,i,j)}{\operatorname{assign}(T,i,j)}}\neq\emptyset$ ,
2.
there is a solution $(\mathcal{F},\pi)$ to ${\mathchoice{\operatorname{confInst}\left(C,\gamma,\sigma\right)}{% \operatorname{confInst}(C,\gamma,\sigma)}{\operatorname{confInst}(C,\gamma,% \sigma)}{\operatorname{confInst}(C,\gamma\sigma)}}$ such that
1. (a)
  
  for all $F\in\pi^{-1}(\mathcal{S})$ , we have that $V(F)\subseteq V(C^{+})$ ,
2. (b)
  
  for all $v\in V(H)\setminus V(C^{+})$ where $H$ is the host-graph of ${\mathchoice{\operatorname{confInst}\left(C,\gamma,\sigma\right)}{% \operatorname{confInst}(C,\gamma,\sigma)}{\operatorname{confInst}(C,\gamma,% \sigma)}{\operatorname{confInst}(C,\gamma\sigma)}}$ , there is exactly one $F\in\mathcal{F}$ with $v\in V(F)$ and for this $F$ , we have ${\mathchoice{\operatorname{deg}_{F}\left(v\right)}{\operatorname{deg}_{F}(v)}{% \operatorname{deg}_{F}(v)}{\operatorname{deg}_{F}(v)}}\geq 2$ ,
3. (c)
  
  for all $F\in\mathcal{F}$ , we have $E(C^{+})\cap E(F)\neq\emptyset$ and $F$ is cycle-free.

We say that $(\sigma,\mathcal{F},\pi)$ gives rise to $\gamma$ on $C$ . With Item 1 we ensure for all $T\in\mathcal{T}_{S}$ that every $v\in T\cap V(C)$ is connected to a vertex in $S\cap V(G)$ . Item 2a ensures that the supply claimed by this configuration is satisfied completely inside $C^{+}$ while Item 2b ensures that connections required from the outside are only used for a single solution tree. Item 2c forbids redundant configurations ensuring that the number of admitted configurations stays singly exponential in ${\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}$ .

We call the set of configurations a component admits its signature ${\mathchoice{\operatorname{sig}\left(C\right)}{\operatorname{sig}(C)}{% \operatorname{sig}(C)}{\operatorname{sig}(C)}}$ . We now characterize, whether an instance is solvable solely based on the signatures of its components in ${G}^{\mathcal{T}}-S$ . For this, let $\Gamma$ be a function that assigns each component of $C\in{\mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-S\right)}{% \operatorname{comp}({G}^{\mathcal{T}}-S)}{\operatorname{comp}({G}^{\mathcal{T}% }-S)}{\operatorname{comp}({G}^{\mathcal{T}}-S)}}$ a configuration in ${\mathchoice{\operatorname{sig}\left(C\right)}{\operatorname{sig}(C)}{% \operatorname{sig}(C)}{\operatorname{sig}(C)}}$ . We call $\Gamma$ a configuration selector.

Definition 7.

We call $\Gamma$ valid, if there is a function $\rho\colon 2^{S\cap V(G)}\times\operatorname{\mathbb{N}}\to 2^{2^{S\cap V(G)}}$ such that

1.

for all $U\subseteq S\cap V(G)$ , with $r_{U}\coloneqq{\mathchoice{\left|\{(T,i)\in\mathcal{T}^{\star}\times% \operatorname{\mathbb{N}}\mid U\in\rho(T,i)\}\right|}{{|\{(T,i)\in\mathcal{T}^% {\star}\times\operatorname{\mathbb{N}}\mid U\in\rho(T,i)\}|}}{{|\{(T,i)\in% \mathcal{T}^{\star}\times\operatorname{\mathbb{N}}\mid U\in\rho(T,i)\}|}}{{|\{% (T,i)\in\mathcal{T}^{\star}\times\operatorname{\mathbb{N}}\mid U\in\rho(T,i)\}% |}}}$ we have

$r_{U}+\sum_{C\in{\mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-S% \right)}{\operatorname{comp}({G}^{\mathcal{T}}-S)}{\operatorname{comp}({G}^{% \mathcal{T}}-S)}{\operatorname{comp}({G}^{\mathcal{T}}-S)}}}{\mathchoice{% \operatorname{dem}_{\Gamma(C)}\left(U\right)}{\operatorname{dem}_{\Gamma(C)}(U% )}{\operatorname{dem}_{\Gamma(C)}(U)}{\operatorname{dem}_{\Gamma(C)}(U)}}\leq% \sum_{C\in{\mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-S\right)}{% \operatorname{comp}({G}^{\mathcal{T}}-S)}{\operatorname{comp}({G}^{\mathcal{T}% }-S)}{\operatorname{comp}({G}^{\mathcal{T}}-S)}}}{\mathchoice{\operatorname{% supl}_{\Gamma(C)}\left(U\right)}{\operatorname{supl}_{\Gamma(C)}(U)}{% \operatorname{supl}_{\Gamma(C)}(U)}{\operatorname{supl}_{\Gamma(C)}(U)}},$
2.

for all $T\in\mathcal{T}^{\star}$ and $i\in{\mathchoice{\left[d(T)\right]}{[d(T)]}{[d(T)]}{[d(T)]}}$ , the hypergraph $(T\cup\bigcup\rho(T,i),\rho(T,i))$ is minimally connected,
3.

for all $T\in\mathcal{T}_{S}$ and $i\in[d(T)]$ , denote with

$\mathcal{H}\coloneqq\{{\mathchoice{\operatorname{assign}_{\Gamma(C)}\left(T,i,% j\right)}{\operatorname{assign}_{\Gamma(C)}(T,i,j)}{\operatorname{assign}_{% \Gamma(C)}(T,i,j)}{\operatorname{assign}_{\Gamma(C)}(T,i,j)}}\mid C\in{% \mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-S\right)}{\operatorname% {comp}({G}^{\mathcal{T}}-S)}{\operatorname{comp}({G}^{\mathcal{T}}-S)}{% \operatorname{comp}({G}^{\mathcal{T}}-S)}},j\in{\mathchoice{\left[{\mathchoice% {\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}\right]}{[{\mathchoice{\left|S\right|}{{% |S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[% {\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}}\}$

all subsets of $S$ that are connected for this terminal set. The hypergraph $\left((T\cap S)\cup\bigcup\mathcal{H},\mathcal{H}\right)$ is connected.

In the definition above, the function $\rho$ is used to capture how the requirements of the terminal sets $\mathcal{T}^{\star}$ are fulfilled. For a $T\in\mathcal{T}^{\star}$ and $i\in{\mathchoice{\left[d(T)\right]}{[d(T)]}{[d(T)]}{[d(T)]}}$ , $\rho(T,i)$ gives all connections that are needed for the $i$ -th tree assigned to $T$ and Item 2 ensures that these connections actually connect $T$ . With Item 1 we ensure that there is enough supply to meet the demand. Finally, Item 3 ensures that the stored solutions for the terminal sets $\mathcal{T}_{S}$ are actually connected.

We require minimal connectivity in Item 2 to limit the number of needed variables in our ILP. Note that we cannot require this in Item 3 as this would prevent for any $T\in\mathcal{T}_{S}$ , $i\in d(T)$ , and $j\in{\mathchoice{\left[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}% \right]}{[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{% \left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{\left|S\right|}{{|S|}}{{% |S|}}{{|S|}}}]}}$ that ${\mathchoice{\left|{\mathchoice{\operatorname{assign}\left(T,i,j\right)}{% \operatorname{assign}(T,i,j)}{\operatorname{assign}(T,i,j)}{\operatorname{% assign}(T,i,j)}}\right|}{{|{\mathchoice{\operatorname{assign}\left(T,i,j\right% )}{\operatorname{assign}(T,i,j)}{\operatorname{assign}(T,i,j)}{\operatorname{% assign}(T,i,j)}}|}}{{|{\mathchoice{\operatorname{assign}\left(T,i,j\right)}{% \operatorname{assign}(T,i,j)}{\operatorname{assign}(T,i,j)}{\operatorname{% assign}(T,i,j)}}|}}{{|{\mathchoice{\operatorname{assign}\left(T,i,j\right)}{% \operatorname{assign}(T,i,j)}{\operatorname{assign}(T,i,j)}{\operatorname{% assign}(T,i,j)}}|}}}=1$ , which is required in some instances. We show, that a valid configuration selector for $\mathscr{P}$ exists if and only if $\mathscr{P}$ is a positive instance.

Lemma 8.

Let $S$ be a nice fracture modulator of ${G}^{\mathcal{T}}$ . Assume that for all $v\in V$ we have $\sum_{T\in\mathcal{T}\colon v\in T}d(T)\leq{\mathchoice{\operatorname{deg}_{G}% \left(v\right)}{\operatorname{deg}_{G}(v)}{\operatorname{deg}_{G}(v)}{% \operatorname{deg}_{G}(v)}}$ . Then, the there is a valid configuration selector with respect to $S$ if and only if $\mathscr{P}$ is positive.

Equivalent Configurations.

When building our ILP, we want to treat components with the same signature equally. We call these components equivalent. For each equivalence class, we want to represent all its components by a common set of variables. Now, consider two components $C_{1},C_{2}\in{\mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-S\right)% }{\operatorname{comp}({G}^{\mathcal{T}}-S)}{\operatorname{comp}({G}^{\mathcal{% T}}-S)}{\operatorname{comp}({G}^{\mathcal{T}}-S)}}$ such that there exists a graph isomorphism between $C^{+}_{1}$ and $C^{+}_{2}$ preserving $S$ , whether a vertex is an augmented vertex, and the demand of such vertices. Then, $C_{1}$ and $C_{2}$ are equivalent. Based on this sufficient condition for equivalence, we can calculate that there are no more than $2^{{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\left|S\right|}{{% |S|}}{{|S|}}{{|S|}}}^{2}\right)}{\operatorname{\mathcal{O}}({\mathchoice{\left% |S\right|}{{|S|}}{{|S|}}{{|S|}}}^{2})}{\operatorname{\mathcal{O}}({\mathchoice% {\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^{2})}{\operatorname{\mathcal{O}}({% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^{2})}}}$ non-empty equivalence classes.

Corollary 9.

On ${\mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-S\right)}{% \operatorname{comp}({G}^{\mathcal{T}}-S)}{\operatorname{comp}({G}^{\mathcal{T}% }-S)}{\operatorname{comp}({G}^{\mathcal{T}}-S)}}$ there are at most $2^{{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\left|S\right|}{{% |S|}}{{|S|}}{{|S|}}}^{2}\right)}{\operatorname{\mathcal{O}}({\mathchoice{\left% |S\right|}{{|S|}}{{|S|}}{{|S|}}}^{2})}{\operatorname{\mathcal{O}}({\mathchoice% {\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^{2})}{\operatorname{\mathcal{O}}({% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^{2})}}}$ non-empty equivalence classes.

Additionally, we want to use a variable for each configuration in our ILP. So, we need to bound the number of component configurations that we actually need to consider.

Definition 10.

Let $\gamma$ be a component-configuration. We call $\gamma$ viable, if

\sum_{U\subseteq S\cap V(G)}{\mathchoice{\operatorname{dem}\left(U\right)}{% \operatorname{dem}(U)}{\operatorname{dem}(U)}{\operatorname{dem}(U)}}\leq u{% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}\text{ and }\sum_{U\subseteq S% \cap V(G)}{\mathchoice{\operatorname{supl}\left(U\right)}{\operatorname{supl}(% U)}{\operatorname{supl}(U)}{\operatorname{supl}(U)}}\leq u.

The set of all viable configurations is denoted by $\operatorname{\mathcal{V}}$ .

We can prove that any configuration, that is admitted by a component is indeed viable.

Lemma 11.

For all $C\in{\mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-S\right)}{% \operatorname{comp}({G}^{\mathcal{T}}-S)}{\operatorname{comp}({G}^{\mathcal{T}% }-S)}{\operatorname{comp}({G}^{\mathcal{T}}-S)}}$ , we have ${\mathchoice{\operatorname{sig}\left(C\right)}{\operatorname{sig}(C)}{% \operatorname{sig}(C)}{\operatorname{sig}(C)}}\subseteq\operatorname{\mathcal{% V}}$ .

By counting the number of viable configurations, we get a bound on the number of variables we will need to encode each configuration. Allowing us to compute the signature of a component by brute-force testing whether this component admits a configuration.

Lemma 12.

For all $C\in{\mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-S\right)}{% \operatorname{comp}({G}^{\mathcal{T}}-S)}{\operatorname{comp}({G}^{\mathcal{T}% }-S)}{\operatorname{comp}({G}^{\mathcal{T}}-S)}}$ , we have ${\mathchoice{\left|{\mathchoice{\operatorname{sig}\left(C\right)}{% \operatorname{sig}(C)}{\operatorname{sig}(C)}{\operatorname{sig}(C)}}\right|}{% {|{\mathchoice{\operatorname{sig}\left(C\right)}{\operatorname{sig}(C)}{% \operatorname{sig}(C)}{\operatorname{sig}(C)}}|}}{{|{\mathchoice{\operatorname% {sig}\left(C\right)}{\operatorname{sig}(C)}{\operatorname{sig}(C)}{% \operatorname{sig}(C)}}|}}{{|{\mathchoice{\operatorname{sig}\left(C\right)}{% \operatorname{sig}(C)}{\operatorname{sig}(C)}{\operatorname{sig}(C)}}|}}}\leq{% \mathchoice{\left|\operatorname{\mathcal{V}}\right|}{{|\operatorname{\mathcal{% V}}|}}{{|\operatorname{\mathcal{V}}|}}{{|\operatorname{\mathcal{V}}|}}}\leq 2^% {\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\left|S\right|}{{|S|% }}{{|S|}}{{|S|}}}^{4}\right)}{\operatorname{\mathcal{O}}({\mathchoice{\left|S% \right|}{{|S|}}{{|S|}}{{|S|}}}^{4})}{\operatorname{\mathcal{O}}({\mathchoice{% \left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^{4})}{\operatorname{\mathcal{O}}({% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^{4})}}$ and we can compute ${\mathchoice{\operatorname{sig}\left(C\right)}{\operatorname{sig}(C)}{% \operatorname{sig}(C)}{\operatorname{sig}(C)}}$ in running time $2^{{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\left|S\right|}{{% |S|}}{{|S|}}{{|S|}}}^{4}\log{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}% \right)}{\operatorname{\mathcal{O}}({\mathchoice{\left|S\right|}{{|S|}}{{|S|}}% {{|S|}}}^{4}\log{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}})}{% \operatorname{\mathcal{O}}({\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^% {4}\log{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}})}{\operatorname{% \mathcal{O}}({\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^{4}\log{% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}})}}}$ .

ILP Construction.

To construct our ILP, denote with $\mathfrak{C}$ the set of non-empty equivalence classes. For all $\mathcal{X}\in\mathfrak{C}$ , denote the signature of any component in $\mathcal{X}$ with ${\mathchoice{\operatorname{sig}\left(\mathcal{X}\right)}{\operatorname{sig}(% \mathcal{X})}{\operatorname{sig}(\mathcal{X})}{\operatorname{sig}(\mathcal{X})}}$ . For all $\gamma\in{\mathchoice{\operatorname{sig}\left(\mathcal{X}\right)}{% \operatorname{sig}(\mathcal{X})}{\operatorname{sig}(\mathcal{X})}{% \operatorname{sig}(\mathcal{X})}}$ , we create a variable ${\bf{d}}_{\mathcal{X},\gamma}$ signifying how many components in $\mathcal{X}$ use the configuration $\gamma$ . We ensure for all $\mathcal{X}\in\mathfrak{C}$ that $\sum_{\gamma\in{\mathchoice{\operatorname{sig}\left(\mathcal{X}\right)}{% \operatorname{sig}(\mathcal{X})}{\operatorname{sig}(\mathcal{X})}{% \operatorname{sig}(\mathcal{X})}}}{\bf{d}}_{\mathcal{X},\gamma}={\mathchoice{% \left|\mathcal{X}\right|}{{|\mathcal{X}|}}{{|\mathcal{X}|}}{{|\mathcal{X}|}}}$ . According to Corollaries 9 and 12, This uses $2^{{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\left|S\right|}{{% |S|}}{{|S|}}{{|S|}}}^{4}\right)}{\operatorname{\mathcal{O}}({\mathchoice{\left% |S\right|}{{|S|}}{{|S|}}{{|S|}}}^{4})}{\operatorname{\mathcal{O}}({\mathchoice% {\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^{4})}{\operatorname{\mathcal{O}}({% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^{4})}}}$ variables. Denote with $\Gamma$ a configuration selector that is encoded by these values ${\bf{d}}_{\mathcal{X},\gamma}$ . To check Items 1 and 2 of Definition 7, we create for each $U\subseteq S\cap V(G)$ a variable ${\bf{s}}_{U}$ representing the final value of $r_{U}$ , amounting to at most $2^{{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}}$ many additional variables. First, we ensure that ${\bf{s}}_{U}$ is at most the difference between supply and demand for $U$ . Second, let $T\in\mathcal{T}^{\star}$ , $T\subseteq W\subseteq S\cap V(G)$ , and $\mathcal{M}_{W}$ be the set of minimally-connected hypergraphs on the vertex set $W$ . We use for each $H\in\mathcal{M}_{W}$ a variable ${\bf{p}}_{T,H}$ that signifies how often the hypergraph $H$ is used to fulfill the demand of $T$ . Using this, we can check that each hyper edge $R\subseteq S\cap V(G)$ is used at most ${\bf{s}}_{R}$ times overall while the demand of $T$ is beeing fulfilled. We see that ${\mathchoice{\left|\mathcal{M}_{W}\right|}{{|\mathcal{M}_{W}|}}{{|\mathcal{M}_% {W}|}}{{|\mathcal{M}_{W}|}}}\leq 2^{{\mathchoice{\operatorname{\mathcal{O}}% \left({\mathchoice{\left|W\right|}{{|W|}}{{|W|}}{{|W|}}}^{2}\right)}{% \operatorname{\mathcal{O}}({\mathchoice{\left|W\right|}{{|W|}}{{|W|}}{{|W|}}}^% {2})}{\operatorname{\mathcal{O}}({\mathchoice{\left|W\right|}{{|W|}}{{|W|}}{{|% W|}}}^{2})}{\operatorname{\mathcal{O}}({\mathchoice{\left|W\right|}{{|W|}}{{|W% |}}{{|W|}}}^{2})}}}$ ; meaning, we only introduce $2^{{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\left|S\right|}{{% |S|}}{{|S|}}{{|S|}}}^{2}\right)}{\operatorname{\mathcal{O}}({\mathchoice{\left% |S\right|}{{|S|}}{{|S|}}{{|S|}}}^{2})}{\operatorname{\mathcal{O}}({\mathchoice% {\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^{2})}{\operatorname{\mathcal{O}}({% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^{2})}}}$ additional variables.

To check Item 3 of Definition 7, assume that for all $T\in\mathcal{T}_{S}$ , $i\in{\mathchoice{\left[d(T)\right]}{[d(T)]}{[d(T)]}{[d(T)]}}$ , as well as $U\subseteq S\cap V(G)$ , the variable ${\bf{a}}_{T,i,U}$ corresponds to the binary indicator whether there is a $C\in{\mathchoice{\operatorname{comp}\left({G}^{\mathcal{T}}-S\right)}{% \operatorname{comp}({G}^{\mathcal{T}}-S)}{\operatorname{comp}({G}^{\mathcal{T}% }-S)}{\operatorname{comp}({G}^{\mathcal{T}}-S)}}$ , and $j\in{\mathchoice{\left[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}% \right]}{[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{% \left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{\left|S\right|}{{|S|}}{{% |S|}}{{|S|}}}]}}$ with $U={\mathchoice{\operatorname{assign}_{\Gamma(C)}\left(T,i,j\right)}{% \operatorname{assign}_{\Gamma(C)}(T,i,j)}{\operatorname{assign}_{\Gamma(C)}(T,% i,j)}{\operatorname{assign}_{\Gamma(C)}(T,i,j)}}$ . If $T\cap S\subseteq U\subseteq S\cap V(G)$ , we create the binary variable ${\bf{b}}_{T,i,U}$ . The variable ${\bf{b}}_{T,i,U}$ is an indicator for whether $U$ is the vertex set of the hypergraph $H$ in Item 3 of Definition 7. So, we ensure that there is at most one $T\cap S\subseteq Z\subseteq S\cap V(G)$ with ${\bf{b}}_{T,i,Z}=1$ and that in any valid assignment $Z=\bigcup_{C\in{\mathchoice{\operatorname{comp}\left({G}^{\mathcal{}}-S\right)% }{\operatorname{comp}({G}^{\mathcal{}}-S)}{\operatorname{comp}({G}^{\mathcal{}% }-S)}{\operatorname{comp}({G}^{\mathcal{}}-S)}},j\in{\mathchoice{\left[{% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}\right]}{[{\mathchoice{\left|% S\right|}{{|S|}}{{|S|}}{{|S|}}}]}{[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{% {|S|}}}]}{[{\mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}]}}}{\mathchoice{% \operatorname{assign}\left(T,i,j\right)}{\operatorname{assign}(T,i,j)}{% \operatorname{assign}(T,i,j)}{\operatorname{assign}(T,i,j)}}$ . We ensure that $H$ is connected using a cut based approach.

Overall, we need $2^{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\left|S\right|}{{|% S|}}{{|S|}}{{|S|}}}\right)}{\operatorname{\mathcal{O}}({\mathchoice{\left|S% \right|}{{|S|}}{{|S|}}{{|S|}}})}{\operatorname{\mathcal{O}}({\mathchoice{\left% |S\right|}{{|S|}}{{|S|}}{{|S|}}})}{\operatorname{\mathcal{O}}({\mathchoice{% \left|S\right|}{{|S|}}{{|S|}}{{|S|}}})}}$ variables of type ${\bf{a}}_{T,i,U}$ and ${\bf{b}}_{T,i,U}$ . This shows, that we can represent the instance as an ILP with $2^{{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\left|S\right|}{{% |S|}}{{|S|}}{{|S|}}}^{4}\right)}{\operatorname{\mathcal{O}}({\mathchoice{\left% |S\right|}{{|S|}}{{|S|}}{{|S|}}}^{4})}{\operatorname{\mathcal{O}}({\mathchoice% {\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^{4})}{\operatorname{\mathcal{O}}({% \mathchoice{\left|S\right|}{{|S|}}{{|S|}}{{|S|}}}^{4})}}}$ variables. As we can find a fracture modulator of minimal size in $\operatorname{\mathsf{FPT}}$ time, $\operatorname{\mathsf{GSTP}}$ is $\operatorname{\mathsf{FPT}}$ by the fracture number of the augmented graph. We get thus the main result of this section, stated next.

Theorem 13.

Let $\mathscr{P}=(G,\mathcal{T},d)$ be an instance of $\operatorname{\mathsf{GSTP}}$ . We can decide whether $\mathscr{P}$ is a positive instance in running time $2^{2^{\operatorname{\mathcal{O}}\left(\operatorname{fn}\left({G}^{\mathcal{T}}% \right)^{4}\right)}}{\mathchoice{\left|G\right|}{{|G|}}{{|G|}}{{|G|}}}+{% \mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\left|\mathscr{P}% \right|}{{|\mathscr{P}|}}{{|\mathscr{P}|}}{{|\mathscr{P}|}}}\right)}{% \operatorname{\mathcal{O}}({\mathchoice{\left|\mathscr{P}\right|}{{|\mathscr{P% }|}}{{|\mathscr{P}|}}{{|\mathscr{P}|}}})}{\operatorname{\mathcal{O}}({% \mathchoice{\left|\mathscr{P}\right|}{{|\mathscr{P}|}}{{|\mathscr{P}|}}{{|% \mathscr{P}|}}})}{\operatorname{\mathcal{O}}({\mathchoice{\left|\mathscr{P}% \right|}{{|\mathscr{P}|}}{{|\mathscr{P}|}}{{|\mathscr{P}|}}})}}$ .

5 GSTP by Augmented/Slim Tree-Cut Width

In this section, we present an outline of our proof that $\operatorname{\mathsf{GSTP}}$ is $\operatorname{\mathsf{FPT}}$ by the tree-cut width of the augmented graph as well as the slim tree-cut width of the host graph. Both boil down to solving a dynamic program for a tree-cut decomposition that fulfills some additional assumptions. Note that $\operatorname{\mathsf{GSTP}}$ is $\operatorname{\mathsf{W}[1]\text{-hard}}$ by tree-cut width of the host graph, so these additional assumptions are necessary to achieve an $\operatorname{\mathsf{FPT}}$ algorithm.

Our dynamic program relies on the fact that the number of bold children of any node in our tree-cut decomposition is bounded by a function of its width. Ganian et al. [11] claimed that in a nice tree-cut decomposition the number of bold children of any node is bounded by $w+1$ . In Figure 1, we provide a counter example to this. This shows that in a nice tree-cut decomposition, the number of bold children is actually not bounded by a function of its width. Still, any tree-cut decomposition can be modified in polynomial time to achieve a similar result. The main insight behind this result is that the bold nodes that are not present in the 3-center form a path like the one seen in Figure 1.

(a) A graph family where the bags and links of the tree-cut decomposition are indicated in blue.

(b) The torso at

m

. The 3-center is the graph induced by

z_{c_{1}}

and

z_{c_{2}}

.

Figure 1: A family of graphs with tree-cut width at most 5. In the depicted nice tree-cut decomposition the node

m

has

\ell+2

bold children, where

\ell

can be chosen freely.

Corollary 14.

Any tree-cut decomposition $(S,\mathcal{X})$ can be altered in polynomial time to ensure that it becomes nice and for all $s\in S$ , we have ${\mathchoice{\left|{\mathchoice{\operatorname{b\text{-}chil}\left(s\right)}{% \operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-}chil}(s)}{% \operatorname{b\text{-}chil}(s)}}\right|}{{|{\mathchoice{\operatorname{b\text{% -}chil}\left(s\right)}{\operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-% }chil}(s)}{\operatorname{b\text{-}chil}(s)}}|}}{{|{\mathchoice{\operatorname{b% \text{-}chil}\left(s\right)}{\operatorname{b\text{-}chil}(s)}{\operatorname{b% \text{-}chil}(s)}{\operatorname{b\text{-}chil}(s)}}|}}{{|{\mathchoice{% \operatorname{b\text{-}chil}\left(s\right)}{\operatorname{b\text{-}chil}(s)}{% \operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-}chil}(s)}}|}}}+{% \mathchoice{\left|X_{s}\right|}{{|X_{s}|}}{{|X_{s}|}}{{|X_{s}|}}}\leq w+2$ . We call such a tree-cut decomposition friendly.

Based on this, we give the definition of a simple tree-cut decomposition.

Definition 15.

Consider a tree-cut decomposition $\mathcal{D}\coloneqq(S,\mathcal{X})$ of $G$ and let $s\in V(S)$ . Denote with ${\mathchoice{\operatorname{cross}\left(s\right)}{\operatorname{cross}(s)}{% \operatorname{cross}(s)}{\operatorname{cross}(s)}}\coloneqq\{T\in\mathcal{T}% \mid T\cap Y_{s}\neq\emptyset\land T\setminus Y_{s}\neq\emptyset\}$ the set of terminal sets crossing the link between $s$ and its parent. We call $s$ simple if it is thin, ${\mathchoice{\left|Y_{s}\right|}{{|Y_{s}|}}{{|Y_{s}|}}{{|Y_{s}|}}}=1$ , ${\mathchoice{\operatorname{adh}\left(s\right)}{\operatorname{adh}(s)}{% \operatorname{adh}(s)}{\operatorname{adh}(s)}}=2$ , and ${\mathchoice{\operatorname{cross}\left(s\right)}{\operatorname{cross}(s)}{% \operatorname{cross}(s)}{\operatorname{cross}(s)}}=\emptyset$ . We call $\mathcal{D}$ simple, if it is friendly and all thin nodes are simple.

5.1 GSTP by a Simple Tree-Cut Decomposition

Assume we are given a simple tree-cut decomposition $\mathcal{D}\coloneqq(S,\mathcal{X})$ for $G$ of width $w$ . For all $s\in V(S)$ , the thin children of $s$ mostly act like subdivided edges inside $G[X_{s}]$ . To limit the number of trees that we need to consider crossing ${\mathchoice{\operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}{% \operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}}$ , define ${\mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{d-cross}(s)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}\coloneqq\sum_{T\in{% \mathchoice{\operatorname{cross}\left(s\right)}{\operatorname{cross}(s)}{% \operatorname{cross}(s)}{\operatorname{cross}(s)}}}d(T)$ .

Reduction Rule 16.

If there is a node $s\in V(S)$ with ${\mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{d-cross}(s)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}>{\mathchoice{% \operatorname{adh}\left(s\right)}{\operatorname{adh}(s)}{\operatorname{adh}(s)% }{\operatorname{adh}(s)}}$ , output a trivial negative instance.

If we apply Reduction Rule 16, we can now choose for each $s\in V(S)$ a function $\operatorname{\eta}_{s}\colon{\mathchoice{\left[{\mathchoice{\operatorname{d-% cross}\left(s\right)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}{% \operatorname{d-cross}(s)}}\right]}{[{\mathchoice{\operatorname{d-cross}\left(% s\right)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{% d-cross}(s)}}]}{[{\mathchoice{\operatorname{d-cross}\left(s\right)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s% )}}]}{[{\mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{d-% cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}]}}\to{% \mathchoice{\operatorname{cross}\left(s\right)}{\operatorname{cross}(s)}{% \operatorname{cross}(s)}{\operatorname{cross}(s)}}$ such that for all $T\in{\mathchoice{\operatorname{cross}\left(s\right)}{\operatorname{cross}(s)}{% \operatorname{cross}(s)}{\operatorname{cross}(s)}}$ we have ${\mathchoice{\left|{\mathchoice{\operatorname{\eta}_{s}^{-1}\left(T\right)}{% \operatorname{\eta}_{s}^{-1}(T)}{\operatorname{\eta}_{s}^{-1}(T)}{% \operatorname{\eta}_{s}^{-1}(T)}}\right|}{{|{\mathchoice{\operatorname{\eta}_{% s}^{-1}\left(T\right)}{\operatorname{\eta}_{s}^{-1}(T)}{\operatorname{\eta}_{s% }^{-1}(T)}{\operatorname{\eta}_{s}^{-1}(T)}}|}}{{|{\mathchoice{\operatorname{% \eta}_{s}^{-1}\left(T\right)}{\operatorname{\eta}_{s}^{-1}(T)}{\operatorname{% \eta}_{s}^{-1}(T)}{\operatorname{\eta}_{s}^{-1}(T)}}|}}{{|{\mathchoice{% \operatorname{\eta}_{s}^{-1}\left(T\right)}{\operatorname{\eta}_{s}^{-1}(T)}{% \operatorname{\eta}_{s}^{-1}(T)}{\operatorname{\eta}_{s}^{-1}(T)}}|}}}=d(T)$ . This function gives us the ability to identify the different trees crossing the link between this node and its parent by a number in the set ${\mathchoice{\left[{\mathchoice{\operatorname{d-cross}\left(s\right)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s% )}}\right]}{[{\mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{% d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}]}{[{% \mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{d-cross}(s)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}]}{[{\mathchoice{% \operatorname{d-cross}\left(s\right)}{\operatorname{d-cross}(s)}{\operatorname% {d-cross}(s)}{\operatorname{d-cross}(s)}}]}}\subseteq{\mathchoice{\left[w% \right]}{[w]}{[w]}{[w]}}$ . Based on this, we obtain a dynamic program for deciding the instance in $\operatorname{\mathsf{FPT}}$ time with respect to $w$ .

The Data-Table.

The data-table $D(s)$ at $s$ , is a set of tuples $\tau$ , each consisting of three parts: $\operatorname{pastPart}_{\tau}$ , $\operatorname{pastAssign}_{\tau}$ , and $\operatorname{futPart}_{\tau}$ with $\operatorname{pastAssign}_{\tau}\colon\operatorname{pastPart}_{\tau}\to{% \mathchoice{\left[w\right]}{[w]}{[w]}{[w]}}$ . Each of $\operatorname{pastPart}_{\tau}$ and $\operatorname{futPart}_{\tau}$ are partitions of a (not necessarily proper) subset of $E({\mathchoice{\operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}{% \operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}})$ . If $\bigcup\operatorname{pastPart}_{\tau}$ and $\bigcup\operatorname{futPart}_{\tau}$ are disjoint, we call $\tau$ syntactically valid. Note that we do not assign the partitions in $\operatorname{futPart}_{\tau}$ to indices, since at this point we do not care, whether they are eventually used for the same terminal set.

Intuitively, a tuple $\tau$ gives almost complete information about the part of the final solution that crosses ${\mathchoice{\operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}{% \operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}}$ . Consider a solution $(\mathcal{F},\pi)$ to the whole instance and denote with $\mathcal{F}^{\prime}\subseteq\mathcal{F}$ the trees containing an edge of $E({\mathchoice{\operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}{% \operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}})$ . Set $\mathcal{F}^{\downarrow}\coloneqq\{F\in\mathcal{F}^{\prime}\mid\pi(F)\cap Y_{s% }\neq\emptyset\}$ and $\mathcal{F}^{\uparrow}\coloneqq\mathcal{F}^{\prime}\setminus\mathcal{F}^{\downarrow}$ as the subgraphs crossing the link between $s$ and its parent, which are assigned to terminal set starting below this link and starting above this link, respectively. Let $G_{s}\coloneqq G[Y_{s}]\cup{\mathchoice{\operatorname{\partial}_{s}}{% \operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}{\operatorname{% \partial}_{s}}}$ be the graph edge-induced by all edges with at least one endpoint in $Y_{s}$ . This solution corresponds to a tuple $\tau\in D(s)$ with $\operatorname{pastPart}_{\tau}\coloneqq\{\{E(K)\cap E({\mathchoice{% \operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}{\operatorname{% \partial}_{s}}{\operatorname{\partial}_{s}}})\mid K\in{\mathchoice{% \operatorname{comp}\left(F[E(G_{s})]\right)}{\operatorname{comp}(F[E(G_{s})])}% {\operatorname{comp}(F[E(G_{s})])}{\operatorname{comp}(F[E(G_{s})])}}\}\}_{F% \in\mathcal{F}^{\downarrow}}$ and $\operatorname{futPart}_{\tau}\coloneqq\{\{E(K)\cap E({\mathchoice{% \operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}{\operatorname{% \partial}_{s}}{\operatorname{\partial}_{s}}})\mid K\in{\mathchoice{% \operatorname{comp}\left(F[E(G_{s}))]\right)}{\operatorname{comp}(F[E(G_{s}))]% )}{\operatorname{comp}(F[E(G_{s}))])}{\operatorname{comp}(F[E(G_{s}))])}}\}\}_% {F\in\mathcal{F}^{\uparrow}}$ where we consider the edges in $E({\mathchoice{\operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}{% \operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}})$ per connected component of the trees in $\mathcal{F}^{\prime}$ restricted to the edges incident to $Y_{s}$ . For each $F\in\mathcal{F}^{\downarrow}$ , we choose a distinct $\lambda_{F}\in{\mathchoice{\left[w\right]}{[w]}{[w]}{[w]}}$ such that if $\pi(F)\in{\mathchoice{\operatorname{cross}\left(s\right)}{\operatorname{cross}% (s)}{\operatorname{cross}(s)}{\operatorname{cross}(s)}}$ , we have $\lambda_{F}\in{\mathchoice{\left[{\mathchoice{\operatorname{d-cross}\left(s% \right)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d% -cross}(s)}}\right]}{[{\mathchoice{\operatorname{d-cross}\left(s\right)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s% )}}]}{[{\mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{d-% cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}]}{[{% \mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{d-cross}(s)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}]}}$ and ${\mathchoice{\operatorname{\eta}_{s}\left(\lambda_{F}\right)}{\operatorname{% \eta}_{s}(\lambda_{F})}{\operatorname{\eta}_{s}(\lambda_{F})}{\operatorname{% \eta}_{s}(\lambda_{F})}}=\pi(F)$ and if $\pi(F)\notin{\mathchoice{\operatorname{cross}\left(s\right)}{\operatorname{% cross}(s)}{\operatorname{cross}(s)}{\operatorname{cross}(s)}}$ , we have $\lambda_{F}\in{\mathchoice{\left[w\right]}{[w]}{[w]}{[w]}}\setminus{% \mathchoice{\left[{\mathchoice{\operatorname{d-cross}\left(s\right)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s% )}}\right]}{[{\mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{% d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}]}{[{% \mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{d-cross}(s)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}]}{[{\mathchoice{% \operatorname{d-cross}\left(s\right)}{\operatorname{d-cross}(s)}{\operatorname% {d-cross}(s)}{\operatorname{d-cross}(s)}}]}}$ . Now, we set $\operatorname{pastAssign}_{\tau}$ to $\lambda_{F}$ for each set induced by $F$ .

Consider a syntactically valid tuple $\tau$ . To formally define what $\tau\in D(s)$ is supposed to mean, let $\mathcal{U}_{s}\coloneqq\{T\in\mathcal{T}\mid T\subseteq Y_{s}\}$ . Note that $\mathcal{U}_{s}$ and ${\mathchoice{\operatorname{cross}\left(s\right)}{\operatorname{cross}(s)}{% \operatorname{cross}(s)}{\operatorname{cross}(s)}}$ are disjoint and their union is the set of all terminals $T\in\mathcal{T}$ that are not disjoint from $Y_{s}$ . We add $w$ vertices $\{q_{s,i}\}_{i\in{\mathchoice{\left[w\right]}{[w]}{[w]}{[w]}}}$ to $G_{s}$ such that each has the neighborhood $V({\mathchoice{\operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}{% \operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}})\setminus Y_{s}$ . Call this graph $G_{s}^{*}$ . These additional vertices can be used to simulate that a subgraph gets connected outside $G_{s}$ . Let $i\in{\mathchoice{\left[{\mathchoice{\operatorname{d-cross}\left(s\right)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s% )}}\right]}{[{\mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{% d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}]}{[{% \mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{d-cross}(s)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}]}{[{\mathchoice{% \operatorname{d-cross}\left(s\right)}{\operatorname{d-cross}(s)}{\operatorname% {d-cross}(s)}{\operatorname{d-cross}(s)}}]}}$ and denote with $Q_{s,i}\coloneqq({\mathchoice{\operatorname{\eta}_{s}\left(i\right)}{% \operatorname{\eta}_{s}(i)}{\operatorname{\eta}_{s}(i)}{\operatorname{\eta}_{s% }(i)}}\cap Y_{s})\cup\{q_{s,i}\}$ the vertices in $Y_{s}$ of the terminal set assigned to the $i$ -th subgraph crossing ${\mathchoice{\operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}{% \operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}}$ combined with $q_{s,i}$ . Additionally, define for each $P\in\operatorname{futPart}_{\tau}$ the set $R_{s,P}\coloneqq V(G[P])\setminus Y_{s}$ to be all vertices of edges contained in $P$ that are not in $Y_{s}$ . Finally, define the instance $\mathscr{D}_{s,\tau}\coloneqq(G_{s}^{*},\mathcal{U}_{s}\cup\{Q_{s,i}\}_{i\in{% \mathchoice{\left[{\mathchoice{\operatorname{d-cross}\left(s\right)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s% )}}\right]}{[{\mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{% d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}]}{[{% \mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{d-cross}(s)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}]}{[{\mathchoice{% \operatorname{d-cross}\left(s\right)}{\operatorname{d-cross}(s)}{\operatorname% {d-cross}(s)}{\operatorname{d-cross}(s)}}]}}}\cup\{R_{s,P}\}_{P\in% \operatorname{futPart}_{\tau}},d^{\prime})$ , where for all $T\in\mathcal{U}_{s}$ we have $d^{\prime}(T)=d(T)$ , for all $i\in{\mathchoice{\left[{\mathchoice{\operatorname{d-cross}\left(s\right)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s% )}}\right]}{[{\mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{% d-cross}(s)}{\operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}]}{[{% \mathchoice{\operatorname{d-cross}\left(s\right)}{\operatorname{d-cross}(s)}{% \operatorname{d-cross}(s)}{\operatorname{d-cross}(s)}}]}{[{\mathchoice{% \operatorname{d-cross}\left(s\right)}{\operatorname{d-cross}(s)}{\operatorname% {d-cross}(s)}{\operatorname{d-cross}(s)}}]}}$ , we have $d^{\prime}(Q_{s,i})=1$ , and for all $P\in\operatorname{futPart}_{\tau}$ , we have $d^{\prime}(R_{s,P})={\mathchoice{\left|\{P^{\prime}\in\operatorname{futPart}_{% \tau}\mid R_{s,P^{\prime}}=R_{s,P}\}\right|}{{|\{P^{\prime}\in\operatorname{% futPart}_{\tau}\mid R_{s,P^{\prime}}=R_{s,P}\}|}}{{|\{P^{\prime}\in% \operatorname{futPart}_{\tau}\mid R_{s,P^{\prime}}=R_{s,P}\}|}}{{|\{P^{\prime}% \in\operatorname{futPart}_{\tau}\mid R_{s,P^{\prime}}=R_{s,P}\}|}}}$ .

Definition 17.

For each $s\in V(S)$ the data-table $D(s)$ is the set of syntactically valid tuples $\tau$ at $s$ where the instance $\mathscr{D}_{s,\tau}$ has a solution $(\mathcal{F},\pi)$ such that

1.

we have $E({\mathchoice{\operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}{% \operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}})\cap\bigcup E(% \mathcal{F})\subseteq\bigcup\operatorname{pastPart}_{\tau}\cup\bigcup% \operatorname{futPart}_{\tau}$ ,
2.

for all $P\in\operatorname{futPart}_{\tau}$ and $F\in\pi^{-1}(R_{s,P})$ , the set $V(F)$ is disjoint from $\{q_{s,i}\}_{i\in{\mathchoice{\left[w\right]}{[w]}{[w]}{[w]}}}$ ,
3.

for all $P\in\operatorname{futPart}_{\tau}$ , there is a $F\in\pi^{-1}(R_{s,P})$ with $E(F)\cap E({\mathchoice{\operatorname{\partial}_{S}}{\operatorname{\partial}_{% S}}{\operatorname{\partial}_{S}}{\operatorname{\partial}_{S}}})=P$ ,
4.
for all $i\in{\mathchoice{\left[w\right]}{[w]}{[w]}{[w]}}$ , let $\mathcal{P}_{i}\coloneqq{\mathchoice{\operatorname{pastAssign}_{\tau}^{-1}% \left(i\right)}{\operatorname{pastAssign}_{\tau}^{-1}(i)}{\operatorname{% pastAssign}_{\tau}^{-1}(i)}{\operatorname{pastAssign}_{\tau}^{-1}(i)}}$ , then
- $\blacksquare$
  
  if $\mathcal{P}_{i}=\emptyset$ , we have $q_{s,i}\notin\bigcup V(\mathcal{F})$ ,
- $\blacksquare$
  
  otherwise, there is exactly one $F\in\mathcal{F}$ with $q_{s,i}\in V(F)$ and this $F$ additionally satisfies that $E(F-q_{s,i})$ can be partitioned into $\{E_{P}\}_{P\in\mathcal{P}_{i}}$ such that for all $P\in\mathcal{P}_{i}$ , the graph $F[E_{P}]$ is connected and $E_{P}\cap E({\mathchoice{\operatorname{\partial}_{s}}{\operatorname{\partial}_% {s}}{\operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}})=P$ .

With Item 1 we ensure that the edges used in the solution are accounted for in $\operatorname{pastPart}_{\tau}$ and $\operatorname{futPart}_{\tau}$ . We want to be able to assume that for every $P\in\operatorname{futPart}_{\tau}$ there is a subgraph completely contained in $G_{s}$ connecting all edges of $P$ . So, in Item 2 we ensure that the vertices $\{q_{s,i}\}_{i\in{\mathchoice{\left[w\right]}{[w]}{[w]}{[w]}}}$ – that are used to simulate that a subgraph gets connected outside of this graph – are not included in the subgraphs connecting the edges in $P$ . These subgraphs should also use exactly the edge-set $P$ in $E({\mathchoice{\operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}{% \operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}})$ , which we ensure with Item 3. Finally, consider Item 4 and $i\in{\mathchoice{\left[w\right]}{[w]}{[w]}{[w]}}$ . If $\mathcal{P}_{i}=\emptyset$ , that is, no edges are assigned to the $i$ -th subgraph, the vertex $q_{s,i}$ , which is used to mark the $i$ -th subgraph crossing ${\mathchoice{\operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}{% \operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}}$ , is not used in any subgraph. Otherwise, we again ensure that for each $P\in\mathcal{P}_{i}$ there is a subgraph in this solution that connects the edges of $P$ inside $G_{s}$ . Notice that we can combine Items 1, 3, and 4 to show, that for any $F\in\mathcal{F}$ with $E(F)\cap E({\mathchoice{\operatorname{\partial}_{s}}{\operatorname{\partial}_{% s}}{\operatorname{\partial}_{s}}{\operatorname{\partial}_{s}}})\neq\emptyset$ there is a $P\in\operatorname{pastPart}_{\tau}\cup\operatorname{futPart}_{\tau}$ with $P\subseteq E(F)$ .

Immediately, we observe that this dynamic program can indeed be used to determine whether $\mathscr{P}$ is a positive instance, by checking for the root $r$ of $S$ whether $D(r)\neq\emptyset$ .

Computing the Data-Table.

To compute this dynamic program, we assume that for all bold children $b\in{\mathchoice{\operatorname{b\text{-}chil}\left(s\right)}{\operatorname{b% \text{-}chil}(s)}{\operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-}chil% }(s)}}$ of $s$ , we have already computed the data-table $D(b)$ . We now outline how to compute $D(s)$ in $\operatorname{\mathsf{FPT}}$ -time. As the number of syntactically valid tuples is in $2^{{\mathchoice{\operatorname{\mathcal{O}}\left(w\log w\right)}{\operatorname{% \mathcal{O}}(w\log w)}{\operatorname{\mathcal{O}}(w\log w)}{\operatorname{% \mathcal{O}}(w\log w)}}}$ , it is enough to decide in $\operatorname{\mathsf{FPT}}$ -time for a given syntactically valid tuple $\tau$ whether $\tau\in D(s)$ . For this we iterate over all simultaneous choices of $\tau_{b}\in D(b)$ for $b\in{\mathchoice{\operatorname{b\text{-}chil}\left(s\right)}{\operatorname{b% \text{-}chil}(s)}{\operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-}chil% }(s)}}$ and check whether the solutions witnessing $\tau_{b}\in D(b)$ can be extended to solutions witnessing $\tau\in D(s)$ .

Assume for all $b\in{\mathchoice{\operatorname{b\text{-}chil}\left(s\right)}{\operatorname{b% \text{-}chil}(s)}{\operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-}chil% }(s)}}$ a $\tau_{b}\in D(b)$ is fixed. To combine the subgraphs of the sub-solutions witnessing $\tau_{b}\in D(b)$ to a solution witnessing $\tau\in D(s)$ , we need to translate the local numberings of the solution subgraphs into a numbering shared across all solution subgraphs not fully contained in one connected component of $S-s$ . When dealing with a shared mapping, we need to avoid that we map solution subgraphs assigned to different terminal sets to the same index. Let $A\coloneqq\{s\}\cup{\mathchoice{\operatorname{b\text{-}chil}\left(s\right)}{% \operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-}chil}(s)}{% \operatorname{b\text{-}chil}(s)}}$ and denote with $\mathcal{T}^{\star}_{s}\coloneqq\{T\in\mathcal{T}\mid T\subseteq X_{s}\}$ the set of terminal sets completely contained in $X_{s}$ , and with $\mathcal{X}\coloneqq\mathcal{T}^{\star}_{s}\cup\bigcup_{a\in A}{\mathchoice{% \operatorname{cross}\left(a\right)}{\operatorname{cross}(a)}{\operatorname{% cross}(a)}{\operatorname{cross}(a)}}$ the set of all terminal sets, which are not completely contained in one sub-tree of $S-s$ . Note that this claim holds for $\mathcal{T}^{\star}_{s}$ as none of their terminal vertices occur in any sub-tree of $S-s$ . As $\mathcal{D}$ is simple, $s$ has at most $w+2$ bold children. So, $w(w+3)$ is an upper bound on the total demand of all terminal sets crossing the links between $s$ and its parent or any of its bold children. It is also an upper bound on the number of edges crossing bold links adjacent to $s$ . So, we need at most $w(w+3)$ shared indices for the crossing subgraphs. Based on these observations, we can carefully construct a mapping from the local numberings to a shared numbering. Given such a mapping, we can construct $2^{{\mathchoice{\operatorname{\mathcal{O}}\left(w^{3}\right)}{\operatorname{% \mathcal{O}}(w^{3})}{\operatorname{\mathcal{O}}(w^{3})}{\operatorname{\mathcal% {O}}(w^{3})}}}$ $\operatorname{\mathsf{GSTP}}$ instances with augmented fracture number at most ${\mathchoice{\operatorname{\mathcal{O}}\left(w^{2}\right)}{\operatorname{% \mathcal{O}}(w^{2})}{\operatorname{\mathcal{O}}(w^{2})}{\operatorname{\mathcal% {O}}(w^{2})}}$ to decide whether this mapping gives a viable extension.

Theorem 18.

Given a simple tree-cut decomposition of width $w$ , we can decide whether the instance is positive in time $2^{2^{{\mathchoice{\operatorname{\mathcal{O}}\left(w^{8}\right)}{\operatorname% {\mathcal{O}}(w^{8})}{\operatorname{\mathcal{O}}(w^{8})}{\operatorname{% \mathcal{O}}(w^{8})}}}}{\mathchoice{\left|V(G)\right|}{{|V(G)|}}{{|V(G)|}}{{|V% (G)|}}}$ .

However, we can not assume, in general, that $\mathcal{D}$ is simple. If $\mathcal{D}$ is already close to simple everywhere, we can make $\mathcal{D}$ simple without increasing its width too much. Let $s\in V(S)$ and denote with $N_{s}\subseteq{\mathchoice{\operatorname{t\text{-}chil}\left(s\right)}{% \operatorname{t\text{-}chil}(s)}{\operatorname{t\text{-}chil}(s)}{% \operatorname{t\text{-}chil}(s)}}$ the set of thin and non-simple children of $s$ . If for all $s$ both ${\mathchoice{\left|N_{s}\right|}{{|N_{s}|}}{{|N_{s}|}}{{|N_{s}|}}}$ and ${\mathchoice{\left|{\mathchoice{\operatorname{b\text{-}chil}\left(s\right)}{% \operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-}chil}(s)}{% \operatorname{b\text{-}chil}(s)}}\right|}{{|{\mathchoice{\operatorname{b\text{% -}chil}\left(s\right)}{\operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-% }chil}(s)}{\operatorname{b\text{-}chil}(s)}}|}}{{|{\mathchoice{\operatorname{b% \text{-}chil}\left(s\right)}{\operatorname{b\text{-}chil}(s)}{\operatorname{b% \text{-}chil}(s)}{\operatorname{b\text{-}chil}(s)}}|}}{{|{\mathchoice{% \operatorname{b\text{-}chil}\left(s\right)}{\operatorname{b\text{-}chil}(s)}{% \operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-}chil}(s)}}|}}}+{% \mathchoice{\left|X_{s}\right|}{{|X_{s}|}}{{|X_{s}|}}{{|X_{s}|}}}-w$ are small, we obtain a simple tree-cut decomposition of only slightly increased width. The main idea is to treat non-simple thin children like bold children.

Lemma 19.

Let $\Delta_{s}\coloneqq{\mathchoice{\left|N_{s}\right|}{{|N_{s}|}}{{|N_{s}|}}{{|N_% {s}|}}}+{\mathchoice{\left|{\mathchoice{\operatorname{b\text{-}chil}_{\mathcal% {D}}\left(s\right)}{\operatorname{b\text{-}chil}_{\mathcal{D}}(s)}{% \operatorname{b\text{-}chil}_{\mathcal{D}}(s)}{\operatorname{b\text{-}chil}_{% \mathcal{D}}(s)}}\right|}{{|{\mathchoice{\operatorname{b\text{-}chil}_{% \mathcal{D}}\left(s\right)}{\operatorname{b\text{-}chil}_{\mathcal{D}}(s)}{% \operatorname{b\text{-}chil}_{\mathcal{D}}(s)}{\operatorname{b\text{-}chil}_{% \mathcal{D}}(s)}}|}}{{|{\mathchoice{\operatorname{b\text{-}chil}_{\mathcal{D}}% \left(s\right)}{\operatorname{b\text{-}chil}_{\mathcal{D}}(s)}{\operatorname{b% \text{-}chil}_{\mathcal{D}}(s)}{\operatorname{b\text{-}chil}_{\mathcal{D}}(s)}% }|}}{{|{\mathchoice{\operatorname{b\text{-}chil}_{\mathcal{D}}\left(s\right)}{% \operatorname{b\text{-}chil}_{\mathcal{D}}(s)}{\operatorname{b\text{-}chil}_{% \mathcal{D}}(s)}{\operatorname{b\text{-}chil}_{\mathcal{D}}(s)}}|}}}+{% \mathchoice{\left|X_{s}\right|}{{|X_{s}|}}{{|X_{s}|}}{{|X_{s}|}}}-w-1$ . We can compute in linear time an equivalent instance $(G^{\prime},\mathcal{T},d)$ and a simple tree-cut decomposition $\mathcal{C}$ of $G^{\prime}$ with width

w+4+\max(0,\max_{s\in V(S)}\Delta_{s}).

5.2 GSTP by Slim Tree-Cut Width

We now show that $\operatorname{\mathsf{GSTP}}$ is $\operatorname{\mathsf{FPT}}$ by the slim tree-cut width of $G$ . This is a direct application of Lemma 19. For this, denote with $\overline{w}\geq w$ the slim width of $\mathcal{D}$ . We mostly need to take care of thin links with adhesion one.

Reduction Rule 20.

Assume that Reduction Rule 16 was applied. Let $s\in V(S)$ with ${\mathchoice{\operatorname{adh}\left(s\right)}{\operatorname{adh}(s)}{% \operatorname{adh}(s)}{\operatorname{adh}(s)}}=1$ and consider $\{uv\}\coloneqq{\mathchoice{\operatorname{\delta}\left(Y_{s}\right)}{% \operatorname{\delta}(Y_{s})}{\operatorname{\delta}(Y_{s})}{\operatorname{% \delta}(Y_{s})}}$ with $u\in Y_{s}$ and $v\notin Y_{s}$ . Remove $u v$ from $G$ and if there is a $T\in{\mathchoice{\operatorname{cross}\left(s\right)}{\operatorname{cross}(s)}{% \operatorname{cross}(s)}{\operatorname{cross}(s)}}$ , increase the demand of $(T\cap Y_{s})\cup\{u\}$ and $(T\setminus Y_{s})\cup\{v\}$ by 1 while removing $T$ from $\mathcal{T}$ (if necessary, add $(T\cap Y_{s})\cup\{u\}$ and $(T\setminus Y_{s})\cup\{v\}$ to $\mathcal{T}$ ).

After applying Reduction Rules 16 and 20 exhaustively and considering connected components separately, all links have adhesion at least two. This can be used to prove that for all $s\in V(S)$ , we have ${\mathchoice{\left|{\mathchoice{\operatorname{chil}\left(s\right)}{% \operatorname{chil}(s)}{\operatorname{chil}(s)}{\operatorname{chil}(s)}}\right% |}{{|{\mathchoice{\operatorname{chil}\left(s\right)}{\operatorname{chil}(s)}{% \operatorname{chil}(s)}{\operatorname{chil}(s)}}|}}{{|{\mathchoice{% \operatorname{chil}\left(s\right)}{\operatorname{chil}(s)}{\operatorname{chil}% (s)}{\operatorname{chil}(s)}}|}}{{|{\mathchoice{\operatorname{chil}\left(s% \right)}{\operatorname{chil}(s)}{\operatorname{chil}(s)}{\operatorname{chil}(s% )}}|}}}+{\mathchoice{\left|X_{s}\right|}{{|X_{s}|}}{{|X_{s}|}}{{|X_{s}|}}}\leq% \overline{w}$ . As $N_{s}\subseteq{\mathchoice{\operatorname{t\text{-}chil}\left(s\right)}{% \operatorname{t\text{-}chil}(s)}{\operatorname{t\text{-}chil}(s)}{% \operatorname{t\text{-}chil}(s)}}$ , we have $\Delta_{s}\leq{\mathchoice{\left|{\mathchoice{\operatorname{chil}\left(s\right% )}{\operatorname{chil}(s)}{\operatorname{chil}(s)}{\operatorname{chil}(s)}}% \right|}{{|{\mathchoice{\operatorname{chil}\left(s\right)}{\operatorname{chil}% (s)}{\operatorname{chil}(s)}{\operatorname{chil}(s)}}|}}{{|{\mathchoice{% \operatorname{chil}\left(s\right)}{\operatorname{chil}(s)}{\operatorname{chil}% (s)}{\operatorname{chil}(s)}}|}}{{|{\mathchoice{\operatorname{chil}\left(s% \right)}{\operatorname{chil}(s)}{\operatorname{chil}(s)}{\operatorname{chil}(s% )}}|}}}+{\mathchoice{\left|X_{s}\right|}{{|X_{s}|}}{{|X_{s}|}}{{|X_{s}|}}}-w-1% \leq\overline{w}-w-1$ . This allows us to apply Lemma 19 and obtain a simple tree-cut decomposition of width at most $\overline{w}+4$ . There is an algorithm that computes a tree-cut decomposition of slim width at most $6({\mathchoice{\operatorname{stcw}\left(G\right)}{\operatorname{stcw}(G)}{% \operatorname{stcw}(G)}{\operatorname{stcw}(G)}}+1)^{3}$ in time $2^{{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\operatorname{% stcw}\left(G\right)}{\operatorname{stcw}(G)}{\operatorname{stcw}(G)}{% \operatorname{stcw}(G)}}^{2}\log{\mathchoice{\operatorname{stcw}\left(G\right)% }{\operatorname{stcw}(G)}{\operatorname{stcw}(G)}{\operatorname{stcw}(G)}}% \right)}{\operatorname{\mathcal{O}}({\mathchoice{\operatorname{stcw}\left(G% \right)}{\operatorname{stcw}(G)}{\operatorname{stcw}(G)}{\operatorname{stcw}(G% )}}^{2}\log{\mathchoice{\operatorname{stcw}\left(G\right)}{\operatorname{stcw}% (G)}{\operatorname{stcw}(G)}{\operatorname{stcw}(G)}})}{\operatorname{\mathcal% {O}}({\mathchoice{\operatorname{stcw}\left(G\right)}{\operatorname{stcw}(G)}{% \operatorname{stcw}(G)}{\operatorname{stcw}(G)}}^{2}\log{\mathchoice{% \operatorname{stcw}\left(G\right)}{\operatorname{stcw}(G)}{\operatorname{stcw}% (G)}{\operatorname{stcw}(G)}})}{\operatorname{\mathcal{O}}({\mathchoice{% \operatorname{stcw}\left(G\right)}{\operatorname{stcw}(G)}{\operatorname{stcw}% (G)}{\operatorname{stcw}(G)}}^{2}\log{\mathchoice{\operatorname{stcw}\left(G% \right)}{\operatorname{stcw}(G)}{\operatorname{stcw}(G)}{\operatorname{stcw}(G% )}})}}}{\mathchoice{\left|V(G)\right|}{{|V(G)|}}{{|V(G)|}}{{|V(G)|}}}^{4}$ [12]. Combined with Theorem 18, we obtain that $\operatorname{\mathsf{GSTP}}$ is $\operatorname{\mathsf{FPT}}$ by the slim tree-cut width of the host graph.

Corollary 21.

Let $\mathscr{P}\coloneq(G,\mathcal{T},d)$ be an instance of $\operatorname{\mathsf{GSTP}}$ . We can decide whether $\mathscr{P}$ is positive in time $2^{2^{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\operatorname{% stcw}\left(G\right)}{\operatorname{stcw}(G)}{\operatorname{stcw}(G)}{% \operatorname{stcw}(G)}}^{24}\right)}{\operatorname{\mathcal{O}}({\mathchoice{% \operatorname{stcw}\left(G\right)}{\operatorname{stcw}(G)}{\operatorname{stcw}% (G)}{\operatorname{stcw}(G)}}^{24})}{\operatorname{\mathcal{O}}({\mathchoice{% \operatorname{stcw}\left(G\right)}{\operatorname{stcw}(G)}{\operatorname{stcw}% (G)}{\operatorname{stcw}(G)}}^{24})}{\operatorname{\mathcal{O}}({\mathchoice{% \operatorname{stcw}\left(G\right)}{\operatorname{stcw}(G)}{\operatorname{stcw}% (G)}{\operatorname{stcw}(G)}}^{24})}}}{\mathchoice{\operatorname{poly}\left({% \mathchoice{\left|\mathscr{P}\right|}{{|\mathscr{P}|}}{{|\mathscr{P}|}}{{|% \mathscr{P}|}}}\right)}{\operatorname{poly}({\mathchoice{\left|\mathscr{P}% \right|}{{|\mathscr{P}|}}{{|\mathscr{P}|}}{{|\mathscr{P}|}}})}{\operatorname{% poly}({\mathchoice{\left|\mathscr{P}\right|}{{|\mathscr{P}|}}{{|\mathscr{P}|}}% {{|\mathscr{P}|}}})}{\operatorname{poly}({\mathchoice{\left|\mathscr{P}\right|% }{{|\mathscr{P}|}}{{|\mathscr{P}|}}{{|\mathscr{P}|}}})}}$ .

5.3 GSTP by Tree-Cut Width of the Augmented Graph

Solving $\operatorname{\mathsf{GSTP}}$ parameterized by the tree-cut width of the augmented graph also boils down to solving instances of $\operatorname{\mathsf{GSTP}}$ with a simple tree-cut decomposition. From now on, assume that $\mathcal{D}=(S,\mathcal{X})$ is a tree-cut decomposition of ${G}^{\mathcal{T}}$ with width $w$ . Set $X_{s}^{\prime}\coloneqq X_{s}\cap V(G)$ and let $\mathcal{X}^{\prime}\coloneqq\{X^{\prime}_{s}\}_{s\in V(S)}$ for all $s\in V(S)$ . Then, $\mathcal{D}^{\prime}\coloneqq(S,\mathcal{X}^{\prime})$ is a tree-cut decomposition of $G$ with width at most $w$ . When we refer to Reduction Rules 16 and 20, we mean that they are applied with respect to $\mathcal{D}^{\prime}$ while keeping $\mathcal{D}$ in sync. These reduction rules already bring us quite close to $\mathcal{D}^{\prime}$ being simple with respect to the nodes that are thin in $\mathcal{D}$ .

Lemma 22.

After exhaustively applying Reduction Rules 16 and 20 with respect to $\mathcal{D}^{\prime}$ , removing nodes that are empty in $\mathcal{D}$ and $\mathcal{D}^{\prime}$ and splitting the instance by connected components, we have for all $s\in V(S)\setminus\{r\}$ that are thin in $\mathcal{D}$ that ${\mathchoice{\operatorname{adh}_{\mathcal{D}}\left(s\right)}{\operatorname{adh% }_{\mathcal{D}}(s)}{\operatorname{adh}_{\mathcal{D}}(s)}{\operatorname{adh}_{% \mathcal{D}}(s)}}=2$ and ${\mathchoice{\operatorname{cross}_{\mathcal{D^{\prime}}}\left(s\right)}{% \operatorname{cross}_{\mathcal{D^{\prime}}}(s)}{\operatorname{cross}_{\mathcal% {D^{\prime}}}(s)}{\operatorname{cross}_{\mathcal{D^{\prime}}}(s)}}=\emptyset$ . In particular, ${\mathchoice{\operatorname{\delta}_{{G}^{\mathcal{T}}}\left(Y^{\mathcal{D}}_{s% }\right)}{\operatorname{\delta}_{{G}^{\mathcal{T}}}(Y^{\mathcal{D}}_{s})}{% \operatorname{\delta}_{{G}^{\mathcal{T}}}(Y^{\mathcal{D}}_{s})}{\operatorname{% \delta}_{{G}^{\mathcal{T}}}(Y^{\mathcal{D}}_{s})}}$ does not contain an augmented and a non-augmented edge. Additionally, the tree-cut decompositions can be maintained efficiently while not increasing the width of $\mathcal{D}$ and keeping $\mathcal{D}$ friendly if it was friendly before.

There are two obstacles remaining before we can show that $\operatorname{\mathsf{GSTP}}$ is $\operatorname{\mathsf{FPT}}$ by the tree-cut width of the augmented graph. First, we need to ensure for all thin nodes $s\in V(S)\setminus\{r\}$ that ${\mathchoice{\left|Y^{\mathcal{D^{\prime}}}_{s}\right|}{{|Y^{\mathcal{D^{% \prime}}}_{s}|}}{{|Y^{\mathcal{D^{\prime}}}_{s}|}}{{|Y^{\mathcal{D^{\prime}}}_% {s}|}}}\leq 1$ . We call nodes $s\in V(S)\setminus\{r\}$ that are thin in $\mathcal{D}$ , but have ${\mathchoice{\left|Y^{\mathcal{D^{\prime}}}_{s}\right|}{{|Y^{\mathcal{D^{% \prime}}}_{s}|}}{{|Y^{\mathcal{D^{\prime}}}_{s}|}}{{|Y^{\mathcal{D^{\prime}}}_% {s}|}}}\geq 2$ cluttered. Second, we need to take care of all nodes that are bold in $\mathcal{D}$ , but thin in $\mathcal{D}^{\prime}$ . As $\mathcal{D}$ is friendly, for each $s\in V(S)$ the number of such children is bounded by the number of bold children. So, this task can be taken care of rather quickly by applying Lemma 19.

Lemma 23.

Assume $\mathcal{D}$ is friendly, has no cluttered nodes, that Reduction Rule 20 was applied exhaustively, and that the instance is split by connected components. We can compute in linear time an equivalent instance $(G^{\prime},\mathcal{T},d)$ and a simple tree-cut decomposition $\mathcal{C}$ of $G^{\prime}$ of width at most $w+5$ .

To tackle the cluttered nodes, we solve sub-instances of $\operatorname{\mathsf{GSTP}}$ . The reduction rules we present now, are no reduction rules in the classical sense (i.e., they do not run in polynomial time), but rather recursion rules. We later show, how to apply these rules in a way, that we only solve simple sub-instances and mostly preserve the running time obtained in Theorem 18.

The crux of why this problem is $\operatorname{\mathsf{FPT}}$ by the tree-cut width of the augmented graph, but $\operatorname{\mathsf{W}[1]\text{-hard}}$ by the tree-cut width of the host-graph [13] lies in the fact, that for a cluttered node $s\in V(S)$ , we have for all $T\in\mathcal{T}$ that either $T\cap Y^{\mathcal{D^{\prime}}}_{s}$ or $T\setminus Y^{\mathcal{D^{\prime}}}_{s}$ is empty. This means that no terminal set crosses $Y^{\mathcal{D^{\prime}}}_{s}$ . Therefore, we can mostly disregard how the instance looks on $V(G)\setminus Y^{\mathcal{D^{\prime}}}_{s}$ for deciding how terminal sets contained in $Y^{\mathcal{D^{\prime}}}_{s}$ are solved in a solution of the whole instance. Let $u,x\in Y_{s}$ and $v,y\in V(G)\setminus Y_{s}$ be such, that $\{uv,xy\}={\mathchoice{\operatorname{\delta}_{{G}^{\mathcal{T}}}\left(Y^{% \mathcal{D}^{\prime}}_{s}\right)}{\operatorname{\delta}_{{G}^{\mathcal{T}}}(Y^% {\mathcal{D}^{\prime}}_{s})}{\operatorname{\delta}_{{G}^{\mathcal{T}}}(Y^{% \mathcal{D}^{\prime}}_{s})}{\operatorname{\delta}_{{G}^{\mathcal{T}}}(Y^{% \mathcal{D}^{\prime}}_{s})}}$ , and let $\mathcal{U}\coloneqq\{T\in\mathcal{T}\mid T\subseteq Y_{s}\}$ be the terminal sets contained in $Y^{\mathcal{D^{\prime}}}_{s}$ . Note that $uv,xy\in E(G)$ . First, we consider the case, where we can satisfy the requirements of $\mathcal{U}$ , while supplying an additional connection for $v y$ to $V(G)\setminus Y^{\mathcal{D^{\prime}}}_{s}$ , while solving the requirements of $\mathcal{U}$ .

Reduction Rule 24.

Consider the instance $\mathscr{X}_{s}\coloneqq(G[Y^{\mathcal{D^{\prime}}}_{s}],\mathcal{U}\cup\{u,x% \},d^{\prime})$ where $d^{\prime}$ is $d|_{\mathcal{U}\cup\{u,x\}}$ increased by one for the argument $\{u,x\}$ . If $\mathscr{X}_{s}$ is positive, remove all $\mathcal{U}$ from $\mathcal{T}$ and contract $Y^{\mathcal{D^{\prime}}}_{s}$ in the original instance $\mathscr{P}$ .

If Reduction Rule 24 is not applicable, we know that we cannot use $u v$ and $x y$ in a tree for terminals contained in $V(G)\setminus Y^{\mathcal{D^{\prime}}}_{s}$ . So, we check, whether the terminal sets $\mathcal{U}$ can be solved only using edges of $G[Y^{\mathcal{D^{\prime}}}_{s}]$ .

Reduction Rule 25.

Assume that Reduction Rule 24 is not applicable to $s$ . Consider the instance $\mathscr{Y}_{s}\coloneqq(G[Y^{\mathcal{D^{\prime}}}_{s}],\mathcal{U},d|_{% \mathcal{U}})$ . If $\mathscr{Y}_{s}$ is positive, remove $\mathcal{U}$ from $\mathcal{T}$ and $Y_{s}^{\mathcal{D}^{\prime}}$ from $G$ in the original instance $\mathscr{P}$ .

Finally, we need to take care of the case, where the terminal sets $\mathcal{U}$ cannot be solved using only edges of $G[Y^{\mathcal{D^{\prime}}}_{s}]$ .

Reduction Rule 26.

Assume both Reduction Rules 24 and 25 are not applicable to $s$ . Consider the instance $\mathscr{Z}_{s}\coloneqq(G/(V(G)\setminus Y^{\mathcal{D^{\prime}}}_{s}),% \mathcal{U},d|_{\mathcal{U}})$ . If $\mathscr{Z}_{s}$ is positive, we remove $\mathcal{U}$ from $\mathcal{T}$ , $Y^{\mathcal{D^{\prime}}}_{s}$ from $G$ , and add 1 demand to the terminal set $\{v,y\}$ in the remaining instance (if necessary, add $\{v,y\}$ to $\mathcal{T}$ ). Otherwise, output a trivial negative instance.

The tree-cut width of the augmented graphs of $\mathscr{X}_{s},\mathscr{Y}_{s}$ , and $\mathscr{Z}_{s}$ is at most $w$ and applying any of Reduction Rules 24, 25, and 26 does not increase the tree-cut width of the augmented graph. Together, these reduction rules can be used to remove a cluttered node – or at least make it non-cluttered. To solve $\operatorname{\mathsf{GSTP}}$ parameterized by the tree-cut width of the augmented graph, we solve multiple sub-instances of $\operatorname{\mathsf{GSTP}}$ with respect to simple tree-cut decompositions. The basic idea is to consider a cluttered node $s\in V(S)$ with ${\mathchoice{\left|Y_{s}^{\mathcal{D}}\right|}{{|Y_{s}^{\mathcal{D}}|}}{{|Y_{s% }^{\mathcal{D}}|}}{{|Y_{s}^{\mathcal{D}}|}}}<\frac{{\mathchoice{\left|V(G)% \right|}{{|V(G)|}}{{|V(G)|}}{{|V(G)|}}}}{2}$ . If such a node does not exist, we either re-root, or we are able to directly find a simple tree-cut decomposition of width $w+12$ . Now, we check recursively which of Reduction Rules 24, 25, and 26 is applicable. By choice of $s$ , we can ensure that overall at most ${\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\left|V(G)\right|}{{% |V(G)|}}{{|V(G)|}}{{|V(G)|}}}^{2}\right)}{\operatorname{\mathcal{O}}({% \mathchoice{\left|V(G)\right|}{{|V(G)|}}{{|V(G)|}}{{|V(G)|}}}^{2})}{% \operatorname{\mathcal{O}}({\mathchoice{\left|V(G)\right|}{{|V(G)|}}{{|V(G)|}}% {{|V(G)|}}}^{2})}{\operatorname{\mathcal{O}}({\mathchoice{\left|V(G)\right|}{{% |V(G)|}}{{|V(G)|}}{{|V(G)|}}}^{2})}}$ many simple instances are solved.

Theorem 27.

Assume $\operatorname{\mathsf{GSTP}}$ can be solved in time $r(g,k)$ , given a graph of size at most $g$ and a simple tree-cut decomposition of width at most $k$ . Let $\mathscr{P}\coloneqq(G,\mathcal{T},d)$ be an instance of $\operatorname{\mathsf{GSTP}}$ . Given a tree-cut decomposition of width $w$ for ${G}^{\mathcal{T}}$ , we can decide whether $\mathscr{P}$ is positive in time $r({\mathchoice{\left|G\right|}{{|G|}}{{|G|}}{{|G|}}},w+12)\cdot{\mathchoice{% \operatorname{poly}\left({\mathchoice{\left|\mathscr{P}\right|}{{|\mathscr{P}|% }}{{|\mathscr{P}|}}{{|\mathscr{P}|}}}\right)}{\operatorname{poly}({\mathchoice% {\left|\mathscr{P}\right|}{{|\mathscr{P}|}}{{|\mathscr{P}|}}{{|\mathscr{P}|}}}% )}{\operatorname{poly}({\mathchoice{\left|\mathscr{P}\right|}{{|\mathscr{P}|}}% {{|\mathscr{P}|}}{{|\mathscr{P}|}}})}{\operatorname{poly}({\mathchoice{\left|% \mathscr{P}\right|}{{|\mathscr{P}|}}{{|\mathscr{P}|}}{{|\mathscr{P}|}}})}}$ .

Kim et al. [20] proved that for all graphs $H$ we can compute a tree-cut decomposition of width $2{\mathchoice{\operatorname{tcw}\left(H\right)}{\operatorname{tcw}(H)}{% \operatorname{tcw}(H)}{\operatorname{tcw}(H)}}$ in time $2^{{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\operatorname{tcw% }\left(H\right)}{\operatorname{tcw}(H)}{\operatorname{tcw}(H)}{\operatorname{% tcw}(H)}}^{2}\log{\mathchoice{\operatorname{tcw}\left(H\right)}{\operatorname{% tcw}(H)}{\operatorname{tcw}(H)}{\operatorname{tcw}(H)}}\right)}{\operatorname{% \mathcal{O}}({\mathchoice{\operatorname{tcw}\left(H\right)}{\operatorname{tcw}% (H)}{\operatorname{tcw}(H)}{\operatorname{tcw}(H)}}^{2}\log{\mathchoice{% \operatorname{tcw}\left(H\right)}{\operatorname{tcw}(H)}{\operatorname{tcw}(H)% }{\operatorname{tcw}(H)}})}{\operatorname{\mathcal{O}}({\mathchoice{% \operatorname{tcw}\left(H\right)}{\operatorname{tcw}(H)}{\operatorname{tcw}(H)% }{\operatorname{tcw}(H)}}^{2}\log{\mathchoice{\operatorname{tcw}\left(H\right)% }{\operatorname{tcw}(H)}{\operatorname{tcw}(H)}{\operatorname{tcw}(H)}})}{% \operatorname{\mathcal{O}}({\mathchoice{\operatorname{tcw}\left(H\right)}{% \operatorname{tcw}(H)}{\operatorname{tcw}(H)}{\operatorname{tcw}(H)}}^{2}\log{% \mathchoice{\operatorname{tcw}\left(H\right)}{\operatorname{tcw}(H)}{% \operatorname{tcw}(H)}{\operatorname{tcw}(H)}})}}}{\mathchoice{\left|V(H)% \right|}{{|V(H)|}}{{|V(H)|}}{{|V(H)|}}}^{2}$ . Combined with Theorem 18, we know that $\operatorname{\mathsf{GSTP}}$ is FPT by the tree-cut width of the augmented graph.

Corollary 28.

Let $\mathscr{P}\coloneqq(G,\mathcal{T},d)$ be an instance of $\operatorname{\mathsf{GSTP}}$ . We can decide whether this instance is positive in time $2^{2^{\operatorname{\mathcal{O}}\left(\operatorname{tcw}\left({G}^{\mathcal{T}% }\right)^{8}\right)}}{\mathchoice{\operatorname{poly}\left({\mathchoice{\left|% \mathscr{P}\right|}{{|\mathscr{P}|}}{{|\mathscr{P}|}}{{|\mathscr{P}|}}}\right)% }{\operatorname{poly}({\mathchoice{\left|\mathscr{P}\right|}{{|\mathscr{P}|}}{% {|\mathscr{P}|}}{{|\mathscr{P}|}}})}{\operatorname{poly}({\mathchoice{\left|% \mathscr{P}\right|}{{|\mathscr{P}|}}{{|\mathscr{P}|}}{{|\mathscr{P}|}}})}{% \operatorname{poly}({\mathchoice{\left|\mathscr{P}\right|}{{|\mathscr{P}|}}{{|% \mathscr{P}|}}{{|\mathscr{P}|}}})}}$ .

6 STP by Tree-Cut Width

To show, how to decide an instance $\mathscr{P}\coloneqq(G,T,d)$ of $\operatorname{\mathsf{STP}}$ parameterized by ${\mathchoice{\operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{% \operatorname{tcw}(G)}{\operatorname{tcw}(G)}}$ , let $\mathcal{D}=(S,\mathcal{X})$ be a friendly tree-cut decomposition of width $w$ . If ${\mathchoice{\left|T\right|}{{|T|}}{{|T|}}{{|T|}}}\leq w$ , we interpret $\mathscr{P}$ as an instance of $\operatorname{\mathsf{GSTP}}$ . Consider the tree-cut decomposition $\mathcal{D}^{\prime}=(S^{\prime},\mathcal{X}^{\prime})$ for $G^{\{T\}}$ , obtained by adding a new root $r^{\prime}$ containing ${{\mathchoice{\operatorname{aug}\left(T\right)}{\operatorname{aug}(T)}{% \operatorname{aug}(T)}{\operatorname{aug}(T)}}}$ to $S$ , and making the old root a child of $r^{\prime}$ . The adhesion of $\mathcal{D}^{\prime}$ is bounded by $2w$ . Let $s\in V(S)$ . Any $t\in{\mathchoice{\operatorname{t\text{-}chil}_{\mathcal{D}}\left(s\right)}{% \operatorname{t\text{-}chil}_{\mathcal{D}}(s)}{\operatorname{t\text{-}chil}_{% \mathcal{D}}(s)}{\operatorname{t\text{-}chil}_{\mathcal{D}}(s)}}$ with $Y_{t}^{\mathcal{D}}\cap T\neq\emptyset$ is also a thin child of $s^{\prime}$ in $\mathcal{D}^{\prime}$ . Thus, ${\mathchoice{\left|\tilde{H}^{\mathcal{D}^{\prime}}_{s}\right|}{{|\tilde{H}^{% \mathcal{D}^{\prime}}_{s}|}}{{|\tilde{H}^{\mathcal{D}^{\prime}}_{s}|}}{{|% \tilde{H}^{\mathcal{D}^{\prime}}_{s}|}}}\leq 1+{\mathchoice{\left|T\right|}{{|% T|}}{{|T|}}{{|T|}}}+{\mathchoice{\left|{\mathchoice{\operatorname{b\text{-}% chil}\left(s\right)}{\operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-}% chil}(s)}{\operatorname{b\text{-}chil}(s)}}\right|}{{|{\mathchoice{% \operatorname{b\text{-}chil}\left(s\right)}{\operatorname{b\text{-}chil}(s)}{% \operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-}chil}(s)}}|}}{{|{% \mathchoice{\operatorname{b\text{-}chil}\left(s\right)}{\operatorname{b\text{-% }chil}(s)}{\operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-}chil}(s)}}|% }}{{|{\mathchoice{\operatorname{b\text{-}chil}\left(s\right)}{\operatorname{b% \text{-}chil}(s)}{\operatorname{b\text{-}chil}(s)}{\operatorname{b\text{-}chil% }(s)}}|}}}+{\mathchoice{\left|X_{s}\right|}{{|X_{s}|}}{{|X_{s}|}}{{|X_{s}|}}}% \leq 2w+3$ . Note that the torso at $r^{\prime}$ in $\mathcal{D}^{\prime}$ consists of 2 vertices. Thus, the width of $\mathcal{D}^{\prime}$ is bounded by $2w+3$ and we can use Corollary 28 to decide whether the instance is positive in $\operatorname{\mathsf{FPT}}$ -time.

(a) The host graph is a path of length

n

with 3 leaves attached to each vertex.

(b) The augmented graph, augmented edges and vertices are drawn in orange.

Figure 2: A family of instances where the tree-cut width of the augmented graph is unbounded.

The same approach does not work for the case ${\mathchoice{\left|T\right|}{{|T|}}{{|T|}}{{|T|}}}>w$ , as in this case, the tree-cut width of the augmented graph is not necessarily bounded by a function of the tree-cut width of the host graph. For this consider as the host graph a path of length $n$ where we attach to each vertex of the path 3 leaves. This graph is a tree, has tree-cut width 1, and is depicted in Figure 2. If we take all leaves to be the terminal set, the augmented graph, depicted in Figure 2, has tree-cut width at least $\Omega(\sqrt[4]{n})$ [27].

$\blacktriangleright$ Remark 29.

There exists a family of $\operatorname{\mathsf{STP}}$ instances such that the host-graph of every instance has tree-cut width 1, but the tree-cut width of the augmented graph of the instances is not bounded.

In this case (i.e., ${\mathchoice{\left|T\right|}{{|T|}}{{|T|}}{{|T|}}}>w$ ), we observe that $T$ is not contained in a single bag. By Reduction Rule 16, we can assume that $d(T)\leq w$ . As ${\mathchoice{\operatorname{tw}\left(G\right)}{\operatorname{tw}(G)}{% \operatorname{tw}(G)}{\operatorname{tw}(G)}}={\mathchoice{\operatorname{% \mathcal{O}}\left(w^{2}\right)}{\operatorname{\mathcal{O}}(w^{2})}{% \operatorname{\mathcal{O}}(w^{2})}{\operatorname{\mathcal{O}}(w^{2})}}$ , the parameter ${\mathchoice{\operatorname{tw}\left(G\right)}{\operatorname{tw}(G)}{% \operatorname{tw}(G)}{\operatorname{tw}(G)}}+d(T)$ is bounded by a function of $w$ . So, if we can solve $\operatorname{\mathsf{STP}}$ parameterized by this parameter, we obtain an $\operatorname{\mathsf{FPT}}$ algorithm for $\operatorname{\mathsf{STP}}$ parameterized by tree-cut width of the original graph. As it turns out, we can even solve $\operatorname{\mathsf{GSTP}}$ by a similar parameter using a dynamic program on the tree decomposition.

Theorem 30.

Let $(G,\mathcal{T},d)$ be an instance of the $\operatorname{\mathsf{GSTP}}$ problem and set $\Sigma_{D}\coloneqq\sum_{T\in\mathcal{T}}d(T)$ . In time $2^{{\mathchoice{\operatorname{\mathcal{O}}\left(\Sigma_{D}\cdot{\mathchoice{% \operatorname{tw}\left(G\right)}{\operatorname{tw}(G)}{\operatorname{tw}(G)}{% \operatorname{tw}(G)}}\log{\mathchoice{\operatorname{tw}\left(G\right)}{% \operatorname{tw}(G)}{\operatorname{tw}(G)}{\operatorname{tw}(G)}}\right)}{% \operatorname{\mathcal{O}}(\Sigma_{D}\cdot{\mathchoice{\operatorname{tw}\left(% G\right)}{\operatorname{tw}(G)}{\operatorname{tw}(G)}{\operatorname{tw}(G)}}% \log{\mathchoice{\operatorname{tw}\left(G\right)}{\operatorname{tw}(G)}{% \operatorname{tw}(G)}{\operatorname{tw}(G)}})}{\operatorname{\mathcal{O}}(% \Sigma_{D}\cdot{\mathchoice{\operatorname{tw}\left(G\right)}{\operatorname{tw}% (G)}{\operatorname{tw}(G)}{\operatorname{tw}(G)}}\log{\mathchoice{% \operatorname{tw}\left(G\right)}{\operatorname{tw}(G)}{\operatorname{tw}(G)}{% \operatorname{tw}(G)}})}{\operatorname{\mathcal{O}}(\Sigma_{D}\cdot{% \mathchoice{\operatorname{tw}\left(G\right)}{\operatorname{tw}(G)}{% \operatorname{tw}(G)}{\operatorname{tw}(G)}}\log{\mathchoice{\operatorname{tw}% \left(G\right)}{\operatorname{tw}(G)}{\operatorname{tw}(G)}{\operatorname{tw}(% G)}})}}}{\mathchoice{\left|V(G)\right|}{{|V(G)|}}{{|V(G)|}}{{|V(G)|}}}$ , we can decide whether this instance is positive.

We remark that this algorithm directly improves upon the known algorithm for EDP with respect to the parameter ${\mathchoice{\operatorname{tw}\left(G\right)}{\operatorname{tw}(G)}{% \operatorname{tw}(G)}{\operatorname{tw}(G)}}+{\mathchoice{\left|T\right|}{{|T|% }}{{|T|}}{{|T|}}}$ [29].

Combined with the case distinction for $\operatorname{\mathsf{STP}}$ , that in time $2^{{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\operatorname{tcw% }\left(G\right)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)}{\operatorname{% tcw}(G)}}^{2}\log{\mathchoice{\operatorname{tcw}\left(G\right)}{\operatorname{% tcw}(G)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)}}\right)}{\operatorname{% \mathcal{O}}({\mathchoice{\operatorname{tcw}\left(G\right)}{\operatorname{tcw}% (G)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)}}^{2}\log{\mathchoice{% \operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)% }{\operatorname{tcw}(G)}})}{\operatorname{\mathcal{O}}({\mathchoice{% \operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)% }{\operatorname{tcw}(G)}}^{2}\log{\mathchoice{\operatorname{tcw}\left(G\right)% }{\operatorname{tcw}(G)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)}})}{% \operatorname{\mathcal{O}}({\mathchoice{\operatorname{tcw}\left(G\right)}{% \operatorname{tcw}(G)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)}}^{2}\log{% \mathchoice{\operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{% \operatorname{tcw}(G)}{\operatorname{tcw}(G)}})}}}{\mathchoice{\left|V(G)% \right|}{{|V(G)|}}{{|V(G)|}}{{|V(G)|}}}^{2}$ we can find a tree-cut decomposition of width $2{\mathchoice{\operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{% \operatorname{tcw}(G)}{\operatorname{tcw}(G)}}$ [20], and Corollary 28 we get that $\operatorname{\mathsf{STP}}$ is $\operatorname{\mathsf{FPT}}$ by the parameter ${\mathchoice{\operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{% \operatorname{tcw}(G)}{\operatorname{tcw}(G)}}$ .

Corollary 31.

Let $(G,T,d)$ be an instance of $\operatorname{\mathsf{STP}}$ . In time $2^{2^{{\mathchoice{\operatorname{\mathcal{O}}\left({\mathchoice{\operatorname{% tcw}\left(G\right)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)}{% \operatorname{tcw}(G)}}^{8}\right)}{\operatorname{\mathcal{O}}({\mathchoice{% \operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)% }{\operatorname{tcw}(G)}}^{8})}{\operatorname{\mathcal{O}}({\mathchoice{% \operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)% }{\operatorname{tcw}(G)}}^{8})}{\operatorname{\mathcal{O}}({\mathchoice{% \operatorname{tcw}\left(G\right)}{\operatorname{tcw}(G)}{\operatorname{tcw}(G)% }{\operatorname{tcw}(G)}}^{8})}}}}{\mathchoice{\operatorname{poly}\left({% \mathchoice{\left|\mathcal{G}\right|}{{|\mathcal{G}|}}{{|\mathcal{G}|}}{{|% \mathcal{G}|}}}\right)}{\operatorname{poly}({\mathchoice{\left|\mathcal{G}% \right|}{{|\mathcal{G}|}}{{|\mathcal{G}|}}{{|\mathcal{G}|}}})}{\operatorname{% poly}({\mathchoice{\left|\mathcal{G}\right|}{{|\mathcal{G}|}}{{|\mathcal{G}|}}% {{|\mathcal{G}|}}})}{\operatorname{poly}({\mathchoice{\left|\mathcal{G}\right|% }{{|\mathcal{G}|}}{{|\mathcal{G}|}}{{|\mathcal{G}|}}})}}$ , we can decide whether this instance is positive.

7 Conclusion and Outlook

In this paper, we provide the first fixed-parameter tractable algorithm for Steiner Tree Packing ( $\operatorname{\mathsf{STP}}$ ) parameterized by a structural parameter. Concretely, we show that $\operatorname{\mathsf{STP}}$ is $\operatorname{\mathsf{FPT}}$ when parameterized by fracture number as well as tree-cut width. This significantly extends the number of instances for which we know an exact polynomial time algorithm. Previously known polynomial time algorithms are typically based on heuristics or approximations. In case of the result that $\operatorname{\mathsf{STP}}$ is $\operatorname{\mathsf{FPT}}$ by ${\mathchoice{\left|T\right|}{{|T|}}{{|T|}}{{|T|}}}+d$ , we do not even know a concrete algorithm, but only that one exists [26].

To achieve this goal, we generalize the notion of the augmented graph from Edge-Disjoint Paths ( $\operatorname{\mathsf{EDP}}$ ) to Generalized Steiner Tree Packing ( $\operatorname{\mathsf{GSTP}}$ ) and $\operatorname{\mathsf{STP}}$ . This is the first result utilizing this tool on a problem where the terminals are arbitrary sets and not pairs of vertices. The notion of augmentation has been used extensively for $\operatorname{\mathsf{EDP}}$ , but was originally introduced for Multicut [16]. Despite the fact that many parameterized complexity results for the generalized version of this problem (Steiner Multicut) are known [4], the augmented graph has not yet been considered in this setting. We think that augmentation will also prove to be a valuable tool for Steiner Multicut and other similar problems in future research.

Further, we extend all known $\operatorname{\mathsf{FPT}}$ algorithms for $\operatorname{\mathsf{EDP}}$ parameterized by a structural parameter to $\operatorname{\mathsf{GSTP}}$ . In addition, we provide a novel $\operatorname{\mathsf{FPT}}$ algorithm for $\operatorname{\mathsf{GSTP}}$ parameterized by the tree-cut width of the augmented graph. This settles whether $\operatorname{\mathsf{GSTP}}$ is $\operatorname{\mathsf{FPT}}$ or $\operatorname{\mathsf{W}[1]\text{-hard}}$ parameterized by all eight commonly used structural parameters described in Section 2 with respect to the augmented graph as well as the host graph. As all these results coincide between $\operatorname{\mathsf{EDP}}$ and $\operatorname{\mathsf{GSTP}}$ , this also completes such a complexity classification for $\operatorname{\mathsf{EDP}}$ , where previously the result that $\operatorname{\mathsf{EDP}}$ is $\operatorname{\mathsf{FPT}}$ by the tree-cut width of the augmented graph was not known.

For $\operatorname{\mathsf{STP}}$ the established results are almost as complete. We prove for six of these eight parameters that $\operatorname{\mathsf{STP}}$ is $\operatorname{\mathsf{FPT}}$ . It is known, that $\operatorname{\mathsf{STP}}$ is $\operatorname{\mathsf{W}[1]\text{-hard}}$ parameterized by treewidth, even if ${\mathchoice{\left|T\right|}{{|T|}}{{|T|}}{{|T|}}}=3$ [2, 1]. So, the only question remaining here is whether $\operatorname{\mathsf{STP}}$ is $\operatorname{\mathsf{FPT}}$ parameterized by feedback vertex set number. As $\operatorname{\mathsf{EDP}}$ is $\operatorname{\mathsf{W}[1]\text{-hard}}$ parameterized by the feedback vertex set number of the augmented graph [14], the approach employed in this paper – generalizing results from $\operatorname{\mathsf{EDP}}$ to $\operatorname{\mathsf{GSTP}}$ and applying them to $\operatorname{\mathsf{STP}}$ – is not suited to decide this questions. Also, the techniques used by Bodlaender et al. [2] to obtain the $\operatorname{\mathsf{W}[1]\text{-hard}}$ ness result for Integer 2-Commodity Flow parameterized by treewidth, which generalizes to $\operatorname{\mathsf{STP}}$ with ${\mathchoice{\left|T\right|}{{|T|}}{{|T|}}{{|T|}}}=3$ [1], do not easily apply with respect to the feedback vertex set number. We leave answering this question to future research.

References

[1] Ashkan Aazami, Joseph Cheriyan, and Krishnam Raju Jampani. Approximation algorithms and hardness results for packing element-disjoint steiner trees in planar graphs. Algorithmica, 63(1-2):425–456, 2012. doi:10.1007/S00453-011-9540-3.
[2] Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen, Sukanya Pandey, and Erik Jan van Leeuwen. The parameterised complexity of integer multicommodity flow. In 18th International Symposium on Parameterized and Exact Computation, IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands, pages 6:1–6:19, 2023. doi:10.4230/LIPIcs.IPEC.2023.6.
[3] Cornelius Brand, Esra Ceylan, Robert Ganian, Christian Hatschka, and Viktoriia Korchemna. Edge-cut width: An algorithmically driven analogue of treewidth based on edge cuts. In Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers, pages 98–113, 2022. doi:10.1007/978-3-031-15914-5_8.
[4] Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen. Parameterized complexity dichotomy for steiner multicut. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, pages 157–170, 2015. doi:10.4230/LIPIcs.STACS.2015.157.
[5] Michael Burstein and Richard N. Pelavin. Hierarchical wire routing. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2(4):223–234, 1983. doi:10.1109/TCAD.1983.1270040.
[6] S. Chen, O. Gunluk, and B. Yener. Optimal packing of group multicastings. In Proceedings. IEEE INFOCOM ’98, the Conference on Computer Communications. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Gateway to the 21st Century (Cat. No.98, volume 3, pages 980–987 vol.3, 1998. doi:10.1109/INFCOM.1998.662907.
[7] James P. Cohoon and Patrick L. Heck. BEAVER: a computational-geometry-based tool for switchbox routing. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 7(6):684–697, 1988. doi:10.1109/43.3208.
[8] Matt DeVos, Jessica McDonald, and Irene Pivotto. Packing steiner trees. J. Comb. Theory B, 119:178–213, 2016. doi:10.1016/J.JCTB.2016.02.002.
[9] Pavel Dvorák, Eduard Eiben, Robert Ganian, Dusan Knop, and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints. Artif. Intell., 300:103561, 2021. doi:10.1016/J.ARTINT.2021.103561.
[10] Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase. New algorithms for maximum disjoint paths based on tree-likeness. Math. Program., 171(1):433–461, September 2018. doi:10.1007/s10107-017-1199-3.
[11] Robert Ganian, Eun Jung Kim, and Stefan Szeider. Algorithmic applications of tree-cut width. SIAM J. Discret. Math., 36(4):2635–2666, 2022. doi:10.1137/20M137478X.
[12] Robert Ganian and Viktoriia Korchemna. Slim tree-cut width. In 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7-9, 2022, Potsdam, Germany, pages 15:1–15:18, 2022. doi:10.4230/LIPIcs.IPEC.2022.15.
[13] Robert Ganian and Sebastian Ordyniak. The power of cut-based parameters for computing edge-disjoint paths. Algorithmica, 83(2):726–752, October 2020. doi:10.1007/s00453-020-00772-w.
[14] Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan. On structural parameterizations of the edge disjoint paths problem. Algorithmica, 83(6):1605–1637, 2021. doi:10.1007/s00453-020-00795-3.
[15] Naveen Garg, Rohit Khandekar, Keshav Kunal, and Vinayaka Pandit. Bandwidth maximization in multicasting. In Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings, pages 242–253, 2003. doi:10.1007/978-3-540-39658-1_24.
[16] Georg Gottlob and Stephanie Tien Lee. A logical approach to multicut problems. Inf. Process. Lett., 103(4):136–141, 2007. doi:10.1016/J.IPL.2007.03.005.
[17] Martin Grötschel, Alexander Martin, and Robert Weismantel. The steiner tree packing problem in VLSI design. Math. Program., 77:265–281, 1997. doi:10.1007/BF02614374.
[18] Niko Hastrich and Kirill Simonov. Structural parameterization of steiner tree packing. CoRR, abs/2505.09250, 2025. doi:10.48550/arXiv.2505.09250.
[19] Petteri Kaski. Packing steiner trees with identical terminal sets. Inf. Process. Lett., 91(1):1–5, 2004. doi:10.1016/j.ipl.2004.03.006.
[20] Eun Jung Kim, Sang-il Oum, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos. An FPT 2-approximation for tree-cut decomposition. Algorithmica, 80(1):116–135, 2018. doi:10.1007/S00453-016-0245-5.
[21] Matthias Kriesell. Edge-disjoint trees containing some given vertices in a graph. J. Comb. Theory B, 88(1):53–65, 2003. doi:10.1016/S0095-8956(02)00013-8.
[22] W. K. Luk. A greedy switch-box router. Integr., 3(2):129–149, 1985. doi:10.1016/0167-9260(85)90029-X.
[23] A. Martin and R. Weismantel. Packing paths and steiner trees: routing of electronic circuits. CWI Quarterly, 6(3):185–204, September 1993.
[24] Yoram Ofek and Bülent Yener. Reliable concurrent multicast from bursty sources. IEEE J. Sel. Areas Commun., 15(3):434–444, 1997. doi:10.1109/49.564140.
[25] William R. Pulleyblank. Two steiner tree packing problems (extended abstract). In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA, pages 383–387, 1995. doi:10.1145/225058.225163.
[26] Neil Robertson and Paul D. Seymour. Graph minors .xiii. the disjoint paths problem. J. Comb. Theory, Ser. B, 63(1):65–110, 1995. doi:10.1006/JCTB.1995.1006.
[27] Paul Wollan. The structure of graphs not admitting a fixed immersion. J. Comb. Theory, Ser. B, 110:47–66, 2015. doi:10.1016/J.JCTB.2014.07.003.
[28] Miao Zhao, Bin Jia, Mingquan Wu, Heather Yu, and Yang Xu. Software defined network-enabled multicast for multi-party video conferencing systems. In 2014 IEEE International Conference on Communications (ICC), pages 1729–1735, 2014. doi:10.1109/ICC.2014.6883572.
[29] Xiao Zhou, Syurei Tamura, and Takao Nishizeki. Finding edge-disjoint paths in partial k-trees. Algorithmica, 26(1):3–30, 2000. doi:10.1007/s004539910002.

[bib.bib1] [1] Ashkan Aazami, Joseph Cheriyan, and Krishnam Raju Jampani. Approximation algorithms and hardness results for packing element-disjoint steiner trees in planar graphs. Algorithmica, 63(1-2):425–456, 2012. doi:10.1007/S00453-011-9540-3.

[bib.bib2] [2] Hans L. Bodlaender, Isja Mannens, Jelle J. Oostveen, Sukanya Pandey, and Erik Jan van Leeuwen. The parameterised complexity of integer multicommodity flow. In 18th International Symposium on Parameterized and Exact Computation, IPEC 2023, September 6-8, 2023, Amsterdam, The Netherlands, pages 6:1–6:19, 2023. doi:10.4230/LIPIcs.IPEC.2023.6.

[bib.bib3] [3] Cornelius Brand, Esra Ceylan, Robert Ganian, Christian Hatschka, and Viktoriia Korchemna. Edge-cut width: An algorithmically driven analogue of treewidth based on edge cuts. In Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers, pages 98–113, 2022. doi:10.1007/978-3-031-15914-5_8.

[bib.bib4] [4] Karl Bringmann, Danny Hermelin, Matthias Mnich, and Erik Jan van Leeuwen. Parameterized complexity dichotomy for steiner multicut. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, pages 157–170, 2015. doi:10.4230/LIPIcs.STACS.2015.157.

[bib.bib5] [5] Michael Burstein and Richard N. Pelavin. Hierarchical wire routing. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2(4):223–234, 1983. doi:10.1109/TCAD.1983.1270040.

[bib.bib6] [6] S. Chen, O. Gunluk, and B. Yener. Optimal packing of group multicastings. In Proceedings. IEEE INFOCOM ’98, the Conference on Computer Communications. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Gateway to the 21st Century (Cat. No.98, volume 3, pages 980–987 vol.3, 1998. doi:10.1109/INFCOM.1998.662907.

[bib.bib7] [7] James P. Cohoon and Patrick L. Heck. BEAVER: a computational-geometry-based tool for switchbox routing. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 7(6):684–697, 1988. doi:10.1109/43.3208.

[bib.bib8] [8] Matt DeVos, Jessica McDonald, and Irene Pivotto. Packing steiner trees. J. Comb. Theory B, 119:178–213, 2016. doi:10.1016/J.JCTB.2016.02.002.

[bib.bib9] [9] Pavel Dvorák, Eduard Eiben, Robert Ganian, Dusan Knop, and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP: programs with few global variables and constraints. Artif. Intell., 300:103561, 2021. doi:10.1016/J.ARTINT.2021.103561.

[bib.bib10] [10] Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase. New algorithms for maximum disjoint paths based on tree-likeness. Math. Program., 171(1):433–461, September 2018. doi:10.1007/s10107-017-1199-3.

[bib.bib11] [11] Robert Ganian, Eun Jung Kim, and Stefan Szeider. Algorithmic applications of tree-cut width. SIAM J. Discret. Math., 36(4):2635–2666, 2022. doi:10.1137/20M137478X.

[bib.bib12] [12] Robert Ganian and Viktoriia Korchemna. Slim tree-cut width. In 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, September 7-9, 2022, Potsdam, Germany, pages 15:1–15:18, 2022. doi:10.4230/LIPIcs.IPEC.2022.15.

[bib.bib13] [13] Robert Ganian and Sebastian Ordyniak. The power of cut-based parameters for computing edge-disjoint paths. Algorithmica, 83(2):726–752, October 2020. doi:10.1007/s00453-020-00772-w.

[bib.bib14] [14] Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan. On structural parameterizations of the edge disjoint paths problem. Algorithmica, 83(6):1605–1637, 2021. doi:10.1007/s00453-020-00795-3.

[bib.bib15] [15] Naveen Garg, Rohit Khandekar, Keshav Kunal, and Vinayaka Pandit. Bandwidth maximization in multicasting. In Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings, pages 242–253, 2003. doi:10.1007/978-3-540-39658-1_24.

[bib.bib16] [16] Georg Gottlob and Stephanie Tien Lee. A logical approach to multicut problems. Inf. Process. Lett., 103(4):136–141, 2007. doi:10.1016/J.IPL.2007.03.005.

[bib.bib17] [17] Martin Grötschel, Alexander Martin, and Robert Weismantel. The steiner tree packing problem in VLSI design. Math. Program., 77:265–281, 1997. doi:10.1007/BF02614374.

[bib.bib18] [18] Niko Hastrich and Kirill Simonov. Structural parameterization of steiner tree packing. CoRR, abs/2505.09250, 2025. doi:10.48550/arXiv.2505.09250.

[bib.bib19] [19] Petteri Kaski. Packing steiner trees with identical terminal sets. Inf. Process. Lett., 91(1):1–5, 2004. doi:10.1016/j.ipl.2004.03.006.

[bib.bib20] [20] Eun Jung Kim, Sang-il Oum, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos. An FPT 2-approximation for tree-cut decomposition. Algorithmica, 80(1):116–135, 2018. doi:10.1007/S00453-016-0245-5.

[bib.bib21] [21] Matthias Kriesell. Edge-disjoint trees containing some given vertices in a graph. J. Comb. Theory B, 88(1):53–65, 2003. doi:10.1016/S0095-8956(02)00013-8.

[bib.bib22] [22] W. K. Luk. A greedy switch-box router. Integr., 3(2):129–149, 1985. doi:10.1016/0167-9260(85)90029-X.

[bib.bib23] [23] A. Martin and R. Weismantel. Packing paths and steiner trees: routing of electronic circuits. CWI Quarterly, 6(3):185–204, September 1993.

[bib.bib24] [24] Yoram Ofek and Bülent Yener. Reliable concurrent multicast from bursty sources. IEEE J. Sel. Areas Commun., 15(3):434–444, 1997. doi:10.1109/49.564140.

[bib.bib25] [25] William R. Pulleyblank. Two steiner tree packing problems (extended abstract). In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA, pages 383–387, 1995. doi:10.1145/225058.225163.

[bib.bib26] [26] Neil Robertson and Paul D. Seymour. Graph minors .xiii. the disjoint paths problem. J. Comb. Theory, Ser. B, 63(1):65–110, 1995. doi:10.1006/JCTB.1995.1006.

[bib.bib27] [27] Paul Wollan. The structure of graphs not admitting a fixed immersion. J. Comb. Theory, Ser. B, 110:47–66, 2015. doi:10.1016/J.JCTB.2014.07.003.

[bib.bib28] [28] Miao Zhao, Bin Jia, Mingquan Wu, Heather Yu, and Yang Xu. Software defined network-enabled multicast for multi-party video conferencing systems. In 2014 IEEE International Conference on Communications (ICC), pages 1729–1735, 2014. doi:10.1109/ICC.2014.6883572.

[bib.bib29] [29] Xiao Zhou, Syurei Tamura, and Takao Nishizeki. Finding edge-disjoint paths in partial k-trees. Algorithmica, 26(1):3–30, 2000. doi:10.1007/s004539910002.

Structural Parameterization of Steiner Tree Packing

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our contribution.

Overview and structure.

Omitted proofs.

2 Preliminaries

Fracture Number.

Tree-Cut Width.

Definition 1.

Definition 2.

Slim Tree-Cut Width.

Definition 3.

3 Augmentation for GSTP

4 GSTP by Augmented Fracture Number

Definition 4.

Lemma 5.

Component Configurations.

Admitted Configurations.

Definition 6.

Definition 7.

Lemma 8.

Equivalent Configurations.

Corollary 9.

Definition 10.

Lemma 11.

Lemma 12.

ILP Construction.

Theorem 13.

5 GSTP by Augmented/Slim Tree-Cut Width

Corollary 14.

Definition 15.

5.1 GSTP by a Simple Tree-Cut Decomposition

Reduction Rule 16.

The Data-Table.

Definition 17.

Computing the Data-Table.

Theorem 18.

Lemma 19.

5.2 GSTP by Slim Tree-Cut Width

Reduction Rule 20.

Corollary 21.

5.3 GSTP by Tree-Cut Width of the Augmented Graph

Lemma 22.

Lemma 23.

Reduction Rule 24.

Reduction Rule 25.

Reduction Rule 26.

Theorem 27.

Corollary 28.

6 STP by Tree-Cut Width

▶ Remark 29.

Theorem 30.

Corollary 31.

7 Conclusion and Outlook

References

$\blacktriangleright$ Remark 29.