# Fast Combinatorial Algorithms for Efficient Sortation

Madison Van Dyk This work was partially supported by the NSERC Discovery Grant
Program, grant number RGPIN-03956-2017 and by an Amazon Post-Internship
Fellowship. The work presented here does not relate to the authors’ positions
at Amazon Kim Klause Faculty of Mathematics and Computer Science, University
of Bremen Jochen Koenemann∗ Modeling and Optimization, Amazon.com Nicole
Megow†

###### Abstract

Modern parcel logistic networks are designed to ship demand between given
origin, destination pairs of nodes in an underlying directed network.
Efficiency dictates that volume needs to be consolidated at intermediate nodes
in typical hub-and-spoke fashion. In practice, such consolidation requires
parcel sortation. In this work, we propose a mathematical model for the
physical requirements, and limitations of parcel sortation. We then show that
it is NP-hard to determine whether a feasible sortation plan exists. We
discuss several settings, where (near-)feasibility of a given sortation
instance can be determined efficiently. The algorithms we propose are fast and
build on combinatorial witness set type lower bounds that are reminiscent and
extend those used in earlier work on degree-bounded spanning trees and
arborescences.

##  1 Introduction

In modern parcel logistics operations, one broadly faces the problem of
finding an optimal way to ship a given input demand between source-sink node
pairs within an underlying fulfillment network, typically represented as a
directed graph ${D=(N,A)}$. The input demand is given as a collection of
commodities $\\{(s_{k},t_{k})\\}_{k\in\mathcal{K}}$, consisting of pairs of
source and sink nodes in $N$. In this work, we assume each commodity $k$ comes
with a directed $s_{k},t_{k}$-path, $P_{k}$, along which all packages
associated with commodity $k$ must travel. This assumption is often made in
practical applications, as discussed in [16].

Figure 1: Sortation introduction

This paper focuses on parcel sortation, an aspect of routing that has
previously been left unaddressed from a theory perspective. In the simplest
setting, each package that travels from $s_{k}$ to $t_{k}$ via some internal
node $u$ must be sorted at $u$ for its subsequent downstream node. In Figure
1, packages arrive at node $u$ from nodes $s_{1},\ldots s_{i}$ and travel on
to downstream nodes $v_{1},\ldots,v_{j}$. This requires sortation at node $u$
to sub-divide the stream of incoming parcels between the $j$ possible next
stops. We refer to the physical device tasked with packages destined for one
specific downstream node as a sort point. If the vast majority of the traffic
on arc $(u,v_{1})$ arrives at $u$ from $s_{1}$, then we could sort
$s_{1},v_{1}$ volume at $s_{1}$ to $v_{1}$ instead of to $u$. In practice this
entails containerizing $s_{1},v_{1}$ volume at $s_{1}$. These containers are
not opened and sorted at intermediate node $u$, instead, they are cross-
docked, an operation that is significantly faster and less costly than the
process of sorting all individual parcels [24, 27].

Figure 1 illustrates the containerization of $s_{1},v_{1}$ volume at $s_{1}$
by replacing the two dashed arcs $(s_{1},u)$ and $(u,v_{1})$ by one red dashed
arc $(s_{1},v_{1})$. Sort points are required at each node, for each outgoing
arc. Hence, the arc replacement operation in Figure 1 reduces the number of
required sort points at node $u$, but increases the number of sort points
required at $s_{1}$ by 1. Note that sort point capacity is often limited, and
determining the maximum number of sort points required at any warehouse to
route all commodities is important in both short- and long-term planning.

A formal model for sortation. Let $\mathcal{K}$ be a set of commodities, where
each commodity $k\in\mathcal{K}$ has a source $s_{k}$, sink $t_{k}$, and a
designated directed path $P_{k}$ in $D$. Let the _transitive closure_ of
digraph $D$, denoted $\mathtt{cl}(D)$, be the graph obtained by introducing
short-cut arcs $(i,j)$ whenever $j$ can be reached from $i$ through a directed
path in $D$. An example is shown in Figure 2.

Figure 2: Digraph $D$ and its transitive closure $\mathtt{cl}(D)$.

We say that a subgraph $H$ of $\mathtt{cl}(D)$ is _feasible_ if for each
commodity $k\in\mathcal{K}$, there is an $s_{k},t_{k}$-dipath in
$H\cap\mathtt{cl}(P_{k})$. We define the min-degree sort point problem as
follows. $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$: given a directed
graph $D$ and commodity set $\mathcal{K}$, find a feasible subgraph $H$ of
$\mathtt{cl}(D)$ with minimum max out-degree.

Given a graph $H$, let $\Delta^{+}(H)$ denote the maximum out-degree of a node
in $H$. Let $\Delta^{*}$ denote the minimum max out-degree in any feasible
subgraph. In the corresponding decision version of the problem, we are given a
positive integer _target_ , $T$, and the problem is to determine whether or
not $\Delta^{*}\leq T$.

Let $\mathcal{S}=\\{s_{1},s_{2},\cdots,s_{k_{s}}\\}$ be the set of sources,
and $\mathcal{T}=\\{t_{1},t_{2},\cdots,t_{k_{t}}\\}$ be the set of sinks. For
each $s\in\mathcal{S}$, let
$\mathcal{T}(s)=\\{t_{k}:(s,t_{k})\in\mathcal{K}\\}$ and for each
$t\in\mathcal{T}$, let $\mathcal{S}(t)=\\{s_{k}:(s_{k},t)\in\mathcal{K}\\}$.

We assume w.l.o.g. that $D$ is connected, the commodity set is non-empty
($\Delta^{*}\geq 1$), all commodities are non-trivial ($s_{k}\neq t_{k})$ and
unique, and all nodes with no out-arcs in $D$ serve as the sink for some
commodity. Any instance can be reduced to a (set of) equivalent instances that
satisfy these assumptions.

###  1.1 Our results

We say that an instance $\mathcal{I}=(D,\mathcal{K})$ of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ is a _tree instance_ (_star
instance_) if the underlying undirected graph of $D$ is a tree (a star). We
prove that $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ is NP-hard, even
when we restrict to the set of star instances.

######  Theorem 1.

$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ is NP-hard, even when
restricted to star instances.

Henceforth, we focus on tree instances of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$. Note that in this class of
instances, any $s_{k},t_{k}$-dipath in $\mathtt{cl}(D)$ can only use arcs in
$\mathtt{cl}(P_{k})$, where $P_{k}$ is the unique $s_{k},t_{k}$-dipath in
$D=(N,A)$.

First, we construct combinatorial lower bounds that are motivated by the
witness set construction for undirected min-degree spanning trees [7].
Specifically, we define a function $\mathtt{LB}$ such that for all $W\subseteq
N$ and $\mathcal{K}^{\prime}\subseteq\mathcal{K}$,
$\mathtt{LB}(W,\mathcal{K}^{\prime})\leq\Delta^{*}$. We show that in instances
with a single source, this construction is the best possible. We develop an
exact polynomial-time local search algorithm for single-source instances and
certify its optimality by determining values of $W$ and $\mathcal{K}^{\prime}$
such that $\mathtt{LB}(W,\mathcal{K}^{\prime})=\Delta^{+}(H)$ for the graph
$H$ returned. Note that the single-source setting reduces to the problem of
finding a min-degree arborescence in a directed acyclic graph. This problem
can be solved via matroid intersection in $O(n^{3}\log n)$ time [22, 2] or by
a combinatorial algorithm in $O(nm\log n)$ time [26]. Our approach uses the
structure of the transitive closure, and allows us to obtain a very simple
algorithm that beats the runtime of previous results by a quadratic factor.
Moreover, it motivates our other algorithms in more complex settings that
cannot be modeled as min-degree arborescence problems.

######  Theorem 2.

There is an $O(n\log^{2}n)$-time exact algorithm for tree instances of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ with a single source.

When there is a single source and the undirected graph of $D$ is a tree, each
node has at most one entering arc in $D$. We refer to such instances as _out-
tree_ instances. We prove that $\max_{W\subseteq
N,\mathcal{K}^{\prime}\subseteq\mathcal{K}}\mathtt{LB}(W,\mathcal{K}^{\prime})\geq\Delta^{*}-1$
for out-tree instances, by showing that there is a polynomial-time algorithm
that returns a solution with out-degree at most one greater than the best
lower bound. We also show that there are out-tree instances where
$\max_{W\subseteq
N,\mathcal{K}^{\prime}\subseteq\mathcal{K}}\mathtt{LB}(W,\mathcal{K}^{\prime})=\Delta^{*}-1$.

Our polytime algorithm for multi-source out-tree instances is again
combinatorial in nature, but the details are significantly more involved. In
the algorithm for the single-source setting, in each iteration an arc $vw$ is
exchanged for an arc $uw$, where $u$ is on the path between the root (the
unique source) and $v$ in $D$. However, in the multi-source setting, the same
action is not sufficient to ensure a high-quality solution is found. We
instead define an algorithm for
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ on out-trees which takes as
input a target $T$, and returns a feasible solution $H$ with
$\Delta^{+}(H)\leq T$ whenever $\Delta^{*}\leq T-1$. The additional input of
the target as well as a careful selection of which arcs to select in each
iteration prevent the need to backtrack. In the proof of the performance of
this algorithm, we provide an explicit construction of the lower bound
certificate with value at least $\Delta^{*}-1$.

######  Theorem 3.

There is a polynomial-time additive $1$-approximation algorithm for out-tree
instances of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$.

The analysis of the out-tree algorithm is _tight_ , in that there are
instances of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ where the
algorithm does not produce an optimal solution. Moreover, the performance of
the algorithm is bounded against a lower bound that has an inherent gap
matching the proven performance. The algorithmic approach for the out-tree
setting cannot easily be extended to more complex graph structures, such as
stars, since an optimal solution is no longer guaranteed to be acyclic and our
current algorithm heavily relies on this fact. Furthermore, the lower bound
construction weakens significantly for star instances.

We also give a framework for obtaining approximation results for arbitrary
tree instances. As a first step, we give an efficient 2-approximation when $D$
is a star.

######  Theorem 4.

There is a polynomial-time 2-approximation for star instances of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$, and for any $\epsilon>0$
there is a star instance of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$
where $\max_{W\subseteq
N,\mathcal{K}^{\prime}\subseteq\mathcal{K}}\mathtt{LB}(W,\mathcal{K}^{\prime})=\frac{2}{3}\Delta^{*}+\epsilon$.

A generalization of the class of star instances is the class of junction
trees. A tree instance of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ is a
_junction tree instance_ if there is some node $r$ in $D$ such that $r$ is a
node in $P_{k}$ for all $k\in\mathcal{K}$. Our framework for obtaining an
approximation result for general tree instances builds on the approximability
of junction tree instances.

######  Theorem 5.

Given a polytime $\alpha$-approximation algorithm for junction tree instances,
there is a polytime $\alpha\log n$-approximation algorithm for tree instances
of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$.

###  1.2 Related work

Degree-bounded network design problems are fundamental and well-studied
combinatorial optimization problems. A prominent example is the _minimum-
degree spanning tree problem_ which asks, given an undirected, unweighted
graph, for a spanning tree with minimum maximum degree. Fürer and Raghavachari
[7] introduced the problem and presented a local-search based polynomial-time
algorithm for computing a spanning tree with maximum degree which is at most
$1$ larger than the optimal maximum degree. Their combinatorial arguments rely
on _witness sets_ chosen from a family of carefully-constructed lower bounds
[5, 25].

Various techniques have been employed in subsequent work on the weighted
setting, e.g., [9, 11, 13, 20, 4, 3, 21], culminating in the result that one
can compute a spanning tree of minimum cost that exceeds the degree bound by
at most $1$ [23]. Since then, also generalizations have been studied such as
the degree-bounded Steiner tree problem [12, 18], survivable network design
with higher connectivity requirements [17, 18] and the group Steiner tree
problem [6, 10, 14].

Directed (degree-bounded) network design problems are typically substantially
harder than their undirected counterparts. Among the few nontrivial
approximation results are quasipolynomial-time bicriteria approximations (with
respect to cost and maximum out- or in-degree) [10] for the degree-bounded
directed Steiner tree problem and approximation results for problems with
intersecting or crossing supermodular connectivity requirements [1, 19].

A special case in directed degree-bounded network design is the _min-degree
arborescence problem_ where, given a directed graph and root $r$, the goal is
to find a spanning tree rooted at $r$ with minimum max out-degree. This
problem is NP-hard [1, 7, 17] in general, and polytime solvable in directed
acyclic graphs [26].

##  2 Hardness

In this section we prove that $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$
is NP-hard, even in the setting where the underlying undirected graph of $D$
forms a star. To prove this result, we will exhibit a reduction from the NP-
hard problem of $\mathtt{Hitting}$-$\mathtt{set}$ [8], defined as follows.

$\mathtt{Hitting}$-$\mathtt{set}$: Let $\Sigma=\\{e_{1},e_{2},\ldots,e_{m}\\}$
be a set of $m$ elements, let $\mathcal{S}=\\{S_{1},S_{2},\ldots,S_{n}\\}$ be
a set of $n$ non-empty subsets of $\Sigma$, and let $b\in\mathbb{N}$ be a
budget. The hitting set problem asks if there is a subset $R\subset\Sigma$ of
cardinality at most $b$ such that $R\cap S_{i}\neq\emptyset$ for all
$i\in[n]$.

See 1

  * Proof.Let $\mathcal{H}=(\Sigma,\mathcal{S},b)$ be an instance of $\mathtt{Hitting}$-$\mathtt{set}$, where $b\in\mathbb{N}$, and $\Sigma=\\{e_{1},e_{2},\ldots,e_{m}\\}$, and $\mathcal{S}=\\{S_{1},S_{2},\ldots,S_{n}\\}$ is a set of $n$ non-empty subsets of $\Sigma$. The hitting set problem asks if there is a subset $R\subset\Sigma$ of cardinality at most $b$ such that $R\cap S_{i}\neq\emptyset$ for all $i\in[n]$. We will construct a corresponding instance $\mathcal{I}=(D,\mathcal{K})$ of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ such that $\mathcal{H}$ is a $\mathtt{YES}$ instance if and only if $\Delta^{*}\leq c$, for some fixed integer $c$, where $\mathcal{I}$ and $c$ are polynomial in the size of $\mathcal{H}$.

First, we construct a digraph $D^{\prime}=(N^{\prime},A^{\prime})$ with node
and arc sets

$\displaystyle N^{\prime}$
$\displaystyle=\\{s_{i}:i\in[n]\\}\cup\\{v\\}\cup\\{t_{j}:j\in[m]\\},$
$\displaystyle A^{\prime}$
$\displaystyle=\\{s_{i}v:i\in[n]\\}\cup\\{vt_{j}:j\in[m]\\},$

as shown in Figure 3(a). For each $i\in[n]$ and $e_{j}\in S_{i}$, we add a
commodity with source $s_{i}$ and sink $t_{j}$ to form a set
$\mathcal{K}^{\prime}$. That is,
$\mathcal{K}^{\prime}=\\{(s_{i},t_{j}):i\in[n],e_{j}\in S_{i}\\}.$

(a)

(b)

Figure 3: Digraphs $D^{\prime}$ and $D$.

We build on the instance
$\mathcal{I}^{\prime}=(D^{\prime},\mathcal{K}^{\prime})$ to form instance
$\mathcal{I}=(D,\mathcal{K})$. Let $c=\max\\{b,\max_{i}|S_{i}|\\}$. For each
$i\in[n]$, we add a set of nodes, denoted $T_{i}$, of cardinality $c-|S_{i}|$
to $N^{\prime}$. Additionally, we add a set of nodes $T_{v}$ with cardinality
$c-b$. The arc set $A$ is formed by adding an arc from $v$ to all the nodes in
$N\setminus N^{\prime}$. That is,

$\displaystyle N$ $\displaystyle=N^{\prime}\cup T_{v}\cup\\{T_{i}:i\in[n]\\}$
$\displaystyle A$ $\displaystyle=A^{\prime}\cup\\{vt:t\in N^{\prime}\setminus
N\\}.$

The digraph $D$ is given in Figure 3(b), where the square nodes indicate a set
of nodes rather than a single node. Additionally, arcs entering a square node
denote a set of arcs with same shared tail and differing heads – one for each
node in the set represented by the square node.

We add commodities to $\mathcal{K}^{\prime}$ to form the set $\mathcal{K}$.
For each $i\in[n]$, we add the commodity $(s_{i},t)$ for all $t\in T_{i}$, and
the commodity $(s_{i},v)$. Additionally, for each node $t\in T_{v}$ we define
a commodity $(v,t)$. Specifically,

$\displaystyle\mathcal{K}$
$\displaystyle=\mathcal{K}^{\prime}\cup\\{(s_{i},v):i\in[n]\\}\cup\\{(s_{i},t):t\in
T_{i},i\in[n]\\}\cup\\{(v,t):t\in T_{v}\\}.$

Observe that $\mathcal{I}$ and $c$ are polynomial in the input of
$\mathcal{H}$. Furthermore, there are $c+1$ distinct commodities with source
$s_{i}$ for each $i\in[n]$, and any feasible subgraph $H$ must contain the arc
set $E=\\{s_{i}v:i\in[n]\\}\cup\\{vt:t\in T_{v}\\}$ (the red dashed arcs in
Figure 3(b)). We now claim that the hitting set instance $\mathcal{H}$ is a
$\mathtt{YES}$ instance if and only if $\Delta^{*}\leq c$.

First, suppose the hitting set instance $\mathcal{H}$ is a $\mathtt{YES}$
instance. Let $R$ be a set of at most $b$ elements such that $R\cap
S_{i}\neq\emptyset$ for all $i\in[n]$. Up to reordering, we may assume that
$R=\\{e_{1},e_{2},\ldots,e_{p}\\}$ where $p\leq b$. We form a feasible
solution $H$ as follows. First, let $H_{1}$ be the subgraph containing the
edge set $E$ along with the set $\\{vt_{i}:i\in[p]\\}$, as shown in Figure 4.
We define the digraph $H_{2}$ as the subgraph of $\mathtt{cl}(D)$ with arc set
$\\{s_{i}t:t\in T_{i},i\in[n]\\}\cup\\{s_{i}t_{j}:e_{j}\in S_{i}\setminus
R,i\in[n]\\}$. See Figure 4 for an example of $H_{2}$.

Figure 4: Digraphs $H_{1}$ and $H_{2}$.

Let $H=H_{1}\cup H_{2}$. We claim that $H$ is feasible and $\Delta^{+}(H)\leq
c$. Let $k\in\mathcal{K}$. If $s_{k}=v$, then $t_{k}\in T_{v}$ and $H_{1}$
contains an $s_{k},t_{k}$-dipath. Otherwise, $s_{k}=s_{i}$ for some $i\in[n]$.
If $t_{k}=t_{j}$ for some $e_{j}\in S_{i}\cap R$ or $t_{k}=v$, then similarly,
$H_{1}$ contains an $s_{k},t_{k}$-dipath. The final case is if $t_{k}=t_{j}$
for some $e_{j}\in S_{i}\setminus R$ or $t_{k}\in T_{i}$, in which case
$H_{2}$ contains an $s_{k},t_{k}$-dipath. Thus, $H$ is feasible.

It remains to argue that $\Delta^{+}(H)\leq c$. For each $i\in[n]$,

$\displaystyle\deg^{+}_{H}(s_{i})=1+\deg^{+}_{H_{2}}(s_{i})=1+|T_{i}|+|S_{i}\setminus
R|=1+c-|S_{i}|+|S_{i}\setminus R|\leq c,$

where the inequality follows since $R\cap S_{i}\neq\emptyset$ for all
$i\in[n]$. Additionally, we have

$\deg^{+}_{H}(v)=p+|T_{v}|\leq b+(c-b)=c.$

We now prove the reverse direction. Suppose $H\subseteq\mathtt{cl}(D)$ is a
feasible subgraph for instance $\mathcal{I}$, with $\Delta^{+}(H)\leq c$. We
may assume that $H$ is minimal in the sense that removing any arc results in
an infeasible solution. This minimality ensures that for each $i\in[n]$, the
heads of arcs with tail $s_{i}$ in $H$ must be in the set ${v\cup
T_{i}\cup\\{t_{j}:e_{j}\in S_{i}\\}}$, which has cardinality $c+1$.

Let $B$ be the set of arcs in $H$ from $v$ to some node in
$\\{T_{i}:i\in[n]\\}$. We will argue that we may assume this set is empty.
Suppose $B\neq\emptyset$. That is, $H$ contains an arc $vt$ for some $t\in
T_{i}$ for some $i\in[n]$. By minimality, ${H-vt}$ is infeasible, and so $H$
does not contain the arc $s_{i}t$. If $\deg^{+}_{H}(s_{i})<c$, then
${H-vt+s_{i}t}$ is a minimal feasible solution with one fewer node in $B$.
Otherwise, $\deg^{+}_{H}(s_{i})=c$. This implies that $H$ contains an arc
$st_{j}$ for some $e_{j}\in S_{i}$, since the set $S_{i}$ is non-empty. Then
$H^{\prime}=H-vt-s_{i}t_{j}+s_{i}t+vt_{j}$ is a minimal feasible solution with
one fewer arc in $B$. By repeating this argument, we see that we may assume
$B=\emptyset$.

Since $H$ must contain the arc set $E$, and $\deg_{E}^{+}(v)=|T_{v}|=c-b$, $H$
contains at most $b$ arcs from the set $\\{vt_{j}:j\in[m]\\}$. Furthermore,
for each $i\in[n]$ there are $c+1$ commodities (each with a distinct sink)
which have $s_{i}$ as the source. Since $\deg_{H}(s_{i})\leq c$, at least one
of these commodities must be routed by a path of length two. That is, for each
$s_{i}$ there is some commodity with source $s_{i}$ and sink $t$ where $vt$ is
an arc in $H$. Since $B=\emptyset$, $H$ must contain an arc $vt_{j}$ for some
$e_{j}\in S_{i}$. Therefore, $R=\\{e_{j}:vt_{j}\in H,j\in[m]\\}$ forms a
hitting set of $\mathcal{S}$ of cardinality at most $b$. ∎

##  3 Combinatorial lower bounds

In this section we present a family of lower bounds, defined by a set of nodes
$W$ and set of commodities $\mathcal{K}^{\prime}$, which we refer to as a
_witness set_.

Let $D=(N,A)$ be a digraph, and consider a subset $U\subseteq N$. We define
$\delta^{+}_{D}(U)$ as the set of arcs in $D$ leaving $U$. That is,
$\delta^{+}_{D}(U):=\\{vw\in E:v\in U,w\notin U\\}$.

Consider a subset $W\subseteq N$ such that $s_{k}\in W$ and $t_{k}\notin W$
for some $k\in\mathcal{K}$. It follows that any feasible subgraph $H$ must
contain some arc in $\delta^{+}_{\mathtt{cl}(D)}(W)$. Specifically, due to the
given-path structure, we know that $H$ must contain some arc in
$\delta^{+}_{\mathtt{cl}(P_{k})}(W)$. In Figure 5, consider the node set
$W=\\{s,v\\}$ along with the commodity with source $s$ and sink $t_{1}$. On
the left is the base graph $D$, and on the right is the transitive closure.
Since $s\in W$ and $t_{1}\notin W$, it follows that any feasible solution $H$
must have a non-empty intersection with the set $\\{st_{1},vt_{1}\\}$.

Figure 5: A tree instance with $k$ commodities $\\{(s,t_{i}):i\in[k]\\}$.

We combine disjoint cuts for a fixed node set $W$ to obtain lower bounds on
the value of $\Delta^{*}$. To simplify the set of cuts considered, we prove
the following lemma to work with cuts in $D$ rather than in its closure.

######  Lemma 6.

Let $\mathcal{I}=(D,\mathcal{K})$ be a tree instance and $W\subseteq N$. For
any $k,j\in\mathcal{K}$,

$\delta^{+}_{P_{k}}(W)\cap\delta^{+}_{P_{j}}(W)=\emptyset\mbox{ if and only if
}\delta^{+}_{\mathtt{cl}(P_{k})}(W)\cap\delta^{+}_{\mathtt{cl}(P_{j})}(W)=\emptyset.$

  * Proof.Suppose $\delta^{+}_{P_{k}}(W)\cap\delta^{+}_{P_{j}}(W)=\emptyset$ and for a contradiction, suppose there is an arc $vw\in\delta^{+}_{\mathtt{cl}(P_{k})}(W)\cap\delta^{+}_{\mathtt{cl}(P_{j})}(W)$. Then $v\in W$, $w\notin W$, and both $P_{k}$ and $P_{j}$ contain a $v,w$-dipath. Since the underlying undirected graph of $D$ is a tree, it follows that $P_{k}$ and $P_{j}$ contain the _unique_ $v,w$-dipath in $D$. Furthermore, since $v\in W$ and $w\notin W$, there is some arc $xy$ on the $v,w$-dipath where $x\in W$ and $y\notin W$. As a result, $xy\in\delta^{+}_{P_{k}}(W)\cap\delta^{+}_{P_{j}}(W)$, a contradiction.

The reverse direction immediately follows from the observation that
${\delta^{+}_{F}\subseteq\delta^{+}_{\mathtt{cl}(F)}}$ for any directed graph
$F$. Thus,
$\delta^{+}_{P_{k}}(W)\cap\delta^{+}_{P_{j}}(W)\subseteq\delta^{+}_{\mathtt{cl}(P_{k})}(W)\cap\delta^{+}_{\mathtt{cl}(P_{j})}(W)$.
∎

As is standard in proving bounds on the min-max degree [7, 25], we observe the
following: if $\ell$ distinct arcs must leave a set $W$ of nodes in any
feasible solution, then $\Delta^{*}\geq\lceil\ell/|W|\rceil$. The following
lower bound construction shows that we can argue that such a disjoint arc set
can be derived by looking at disjoint cuts of the form $\delta^{+}_{P_{k}}(W)$
for some $k\in\mathcal{K}$. Further, we show that this lower bound can be
strengthened since we must also have connectivity _within_ $W$ in order to
allocate the arcs departing $W$ to different nodes in $W$.

######  Lemma 7.

Let $\mathcal{I}=(D,\mathcal{K})$ be a tree instance of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$. Let $W\subseteq N$ such that
$D[W]$ is connected and suppose
$\emptyset\neq\mathcal{K}^{\prime}\subseteq\mathcal{K}$ such that $s_{k}\in W$
and $t_{k}\notin W$ for all $k\in\mathcal{K}^{\prime}$, and
$\delta^{+}_{P_{k}}(W)\cap\delta^{+}_{P_{j}}(W)=\emptyset$ for all distinct
$k,j\in\mathcal{K}^{\prime}$. Then

$\Delta^{*}\geq\left\lceil\frac{|\mathcal{K}^{\prime}|+|W|-|\mathcal{S}(\mathcal{K}^{\prime})|}{|W|}\right\rceil,$

where $\mathcal{S}(\mathcal{K}^{\prime})$ denotes the set of sources for
commodities in $\mathcal{K}^{\prime}$.

  * Proof.Let $F$ be a feasible subgraph of $\mathtt{cl}(D)$, and let $W,\mathcal{K}^{\prime}$ be given as in the statement. Let $H$ be the subgraph of $F$ where arcs are removed from $F$ if the remaining subgraph remains feasible for the commodity set $\mathcal{K}^{\prime}$. That is, $H$ is a minimal subgraph of $F$ that contains an $s_{k},t_{k}$-dipath for each commodity $k\in\mathcal{K}^{\prime}$.

Since $s_{k}\in W$ and $t_{k}\notin W$, for each $k\in\mathcal{K}^{\prime}$ it
follows ${\delta^{+}_{\mathtt{cl}(P_{k})}(W)\cap H\neq\emptyset}$. Since
$\delta^{+}_{P_{k}}(W)\cap\delta^{+}_{P_{j}}(W)=\emptyset$ for all distinct
$k,j\in\mathcal{K}^{\prime}$, Lemma 6 implies that for all distinct
$k,j\in\mathcal{K}^{\prime}$,
$\delta^{+}_{\mathtt{cl}(P_{k})}(W)\cap\delta^{+}_{\mathtt{cl}(P_{j})}(W)=\emptyset$.
Thus, any feasible subgraph must have at least $|\mathcal{K}^{\prime}|$ arcs
in $\delta^{+}_{\mathtt{cl}(D)}(W)$, and so

$\Delta^{*}\geq\left\lceil\frac{|\mathcal{K}^{\prime}|}{|W|}\right\rceil.$

If any of the $|\mathcal{K}^{\prime}|$ arcs in
$\delta^{+}_{\mathtt{cl}(D)}(W)\cap H$ depart a node $v\in
W\setminus\mathcal{S}(\mathcal{K}^{\prime})$, then $H$ contains an
$s,v$-dipath for some source $s\in\mathcal{S}(\mathcal{K}^{\prime})$, as
otherwise $H$ was not minimal. Since $D[W]$ is connected and $\mathcal{I}$ is
a tree instance, this $s,v$-dipath only uses arcs between nodes in $W$. Thus,
if there are $\ell\geq 1$ nodes in $W$ with departing arcs in
$\delta^{+}_{\mathtt{cl}(D)}(W)\cap H$, $H$ contains at least
$\ell-|\mathcal{S}(\mathcal{K}^{\prime})|$ arcs with both endpoints in $W$.
Therefore,

$\Delta^{*}\geq\min_{\begin{subarray}{c}|\mathcal{S}(\mathcal{K}^{\prime})|\leq\ell\leq|W|\end{subarray}}\left\lceil\frac{|\mathcal{K}^{\prime}|+\ell-|\mathcal{S}(\mathcal{K}^{\prime})|}{\ell}\right\rceil=\left\lceil\frac{|\mathcal{K}^{\prime}|+|W|-|\mathcal{S}(\mathcal{K}^{\prime})|}{|W|}\right\rceil.$

For completeness, the above equality holds by the following argument. First we
rewrite the inequality by letting
$a=\ell-|\mathcal{S}(\mathcal{K}^{\prime})|$.

$\min_{\begin{subarray}{c}|\mathcal{S}(\mathcal{K}^{\prime})|\leq\ell\leq|W|\end{subarray}}\left\lceil\frac{|\mathcal{K}^{\prime}|+\ell-|\mathcal{S}(\mathcal{K}^{\prime})|}{\ell}\right\rceil=\min_{\begin{subarray}{c}0\leq
a\leq|W|-|\mathcal{S}(\mathcal{K}^{\prime})|\end{subarray}}\left\lceil\frac{|\mathcal{K}^{\prime}|+a}{a+|\mathcal{S}(\mathcal{K}^{\prime})|}\right\rceil.$

Let
$f(x)=\frac{|\mathcal{K}^{\prime}|+x}{x+|\mathcal{S}(\mathcal{K}^{\prime})|}$.
Observe that for any $x\geq 0$, $f(x+1)\leq f(x)$, since

$\displaystyle|\mathcal{S}(\mathcal{K}^{\prime})|\leq|\mathcal{K}^{\prime}|$
$\displaystyle\Rightarrow~{}$
$\displaystyle(|\mathcal{K}^{\prime}|+x+1)(x+|\mathcal{S}(\mathcal{K}^{\prime})|)\leq(|\mathcal{K}^{\prime}|+x)(x+1+|\mathcal{S}(\mathcal{K}^{\prime})|)$
$\displaystyle\Rightarrow~{}$
$\displaystyle\frac{|\mathcal{K}^{\prime}|+x+1}{x+1+|\mathcal{S}(\mathcal{K}^{\prime})|}\leq\frac{|\mathcal{K}^{\prime}|+x}{x+|\mathcal{S}(\mathcal{K}^{\prime})|}.$

Thus, the expression is minimized when $\ell=|W|$. ∎

We define the functions $\mathtt{LB}$ and $\mathtt{LB}^{w}$, where for each
$W\subseteq N$ and $\mathcal{K}^{\prime}\subseteq\mathcal{K}$,

$\displaystyle\mathtt{LB}_{\mathcal{I}}(W,\mathcal{K}^{\prime})$
$\displaystyle:=\begin{cases}\left\lceil\frac{|\mathcal{K}^{\prime}|+|W|-|\mathcal{S}(\mathcal{K}^{\prime})|}{|W|}\right\rceil&\mbox{if
$W,\mathcal{K}^{\prime}$ satisfy conditions of Lemma \ref{lemma:LB_multi} for
$\mathcal{I}$}\\\ 0&\mbox{otherwise}\end{cases}$
$\displaystyle\mathtt{LB}_{\mathcal{I}}^{w}(W,\mathcal{K}^{\prime})$
$\displaystyle:=\begin{cases}\left\lceil\frac{|\mathcal{K}^{\prime}|}{|W|}\right\rceil&\mbox{if
$W,\mathcal{K}^{\prime}$ satisfy conditions of Lemma \ref{lemma:LB_multi} for
$\mathcal{I}$}\\\ 0&\mbox{otherwise}\end{cases}$

We will drop the subscript $\mathcal{I}$ when the instance is clear from
context. Note that $\mathtt{LB}^{w}$ is a weaker bound, in that it does not
include any arcs due to connectivity within $W$. Since it holds
${|W|-|\mathcal{S}(\mathcal{K}^{\prime})|\geq 0}$ for all inputs $W$ and
$\mathcal{K}^{\prime}$, we have the following corollary.

######  Corollary 8.

Suppose $\mathcal{I}=(D,\mathcal{K})$ is a tree instance. For all $W\subseteq
N$ and $\mathcal{K}^{\prime}\subseteq\mathcal{K}$,

$\Delta^{*}\geq\mathtt{LB}^{w}(W,\mathcal{K}^{\prime}).$

In the single-source setting, we will prove that for each instance
$\mathcal{I}$, $\Delta^{*}$ is equal to $\max_{W\subseteq
N,\mathcal{K}^{\prime}\subseteq\mathcal{K}}\mathtt{LB}(W,\mathcal{K}^{\prime})$.
A natural next step is to ask if the lower bound construction is also exact
for multi-source out-tree instances. However, this is not the case, since
there are instances of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ on out-
trees where $\max_{W\subseteq
N,\mathcal{K}^{\prime}\subseteq\mathcal{K}}\mathtt{LB}(W,\mathcal{K}^{\prime})=\Delta^{*}-1$.
Consider the out-tree instance on the right, where there are two sources
$s_{1}$ and $s_{2}$. The remaining nodes are sinks labelled with each of the
corresponding indices of sources that are matched to it. That is, a node $v$
labelled with $\\{1,2\\}$ indicates that there are commodities $(s_{1},v)$ and
$(s_{2},v)$. In this instance, $\Delta^{*}=3$, whereas $\max_{W\subseteq
N,\mathcal{K}^{\prime}\subseteq\mathcal{K}}\mathtt{LB}(W,\mathcal{K}^{\prime})=2$.

While the witness set construction is not exact, it remains strong for out-
tree instances. We prove in Section 4 that for any (multi-source) out-tree
instance, even the weaker bound has a gap of at most one:

$\max_{W\subseteq
N,\mathcal{K}^{\prime}\subseteq\mathcal{K}}\mathtt{LB}^{w}(W,\mathcal{K}^{\prime})\geq\Delta^{*}-1.$

##  4 (Near-)optimal algorithms for out-trees

We first present a simple combinatorial algorithm that solves single-source
tree instances. (With a single source, $D$ necessarily forms an out-tree with
root $s$.) We then present a polynomial-time algorithm for out-trees with
multiple sources that returns a feasible solution with max out-degree at most
one more than optimal. The algorithms are purely combinatorial and the
analysis relies on bounds via the witness sets introduced in Section 3.

###  4.1 Simple algorithm for single-source setting

We show that for each single-source instance $\mathcal{I}$,
$\Delta^{*}=\max_{W\subseteq
N,\mathcal{K}^{\prime}\subseteq\mathcal{K}}\mathtt{LB}(W,\mathcal{K}^{\prime})$.
We prove this result by presenting a simple and efficient local search
algorithm that returns an optimal solution, $H$, as well as a witness set
$W,\mathcal{K}^{\prime}$ such that
$\Delta^{+}(H)=\mathtt{LB}(W,\mathcal{K}^{\prime})$. We then present a more
efficient implementation of Algorithm 1 that runs in $O(n\log^{2}n)$ time,
beating previous results by a quadratic factor. We state the results here and
defer all details on the analysis to Appendix A.

1 Start with the feasible solution $D$.

2 Select a max out-degree node $v^{*}$, and move an arbitrary arc departing
$v^{*}$ to the nearest predecessor $u$ of $v^{*}$ (in $D$) with
$\deg^{+}(u)\leq\deg^{+}(v^{*})$.

Repeat Step 2 until no such predecessor exists.

Algorithm 1 Local search algorithm for the single-source setting.

Figure 6 demonstrates the steps of the algorithm when the base graph $D$ is as
provided in Figure 6(a), and $\mathcal{T}$ is the set of leaves. The square
node is the selected max out-degree node, $v^{*}$, in each iteration and the
nearest predecessor with degree at least two less than $v^{*}$ is $u$. Observe
that in iteration 3, no such predecessor exists and so the algorithm
terminates.

(a) $H=D$

(b) Iteration 1: $v^{*}$ identified.

(c) Iteration 1: $v^{*}w$ shifted.

(d) Iteration 2: $v^{*}$ identified.

(e) Iteration 2: $v^{*}w$ shifted.

(f) Iteration 3: $v^{*}$ identified.

Figure 6: Execution of local search algorithm for single-source setting.

We prove that this algorithm returns an optimal solution, $H$, by constructing
a witness set $W,\mathcal{K}^{\prime}$ such that
$\mathtt{LB}(W,\mathcal{K}^{\prime})=\Delta^{+}(H)$.

See 2

###  4.2 Additive 1-approximation algorithm for out-trees

First, we describe how the multi-source setting differs from the single-source
setting, making an extension of Algorithm 1 non-trivial. Consider the instance
given in Figure 7(a). The sinks are the set of leaves, and each sink $t$ is
labelled with the set of indices of sources for which there is a commodity
with that source and sink $t$. Observe that we can no longer select departing
arcs to shift arbitrarily: the arc $vw$ cannot be shifted since there is a
commodity with source $v$ and sink $w$, while the other arcs departing $v$ can
be shifted. Furthermore, it is no longer the case that in order to decrease
the degree of the highest node, we only need to shift a single arc. In Figure
7(b) we see that in the potential second iteration of Algorithm 1, no arc can
be moved from $v$ since $s_{2}$ has out-degree 3, and all arcs departing $v$
serve commodities with source $s_{2}$.

(a) Out-tree instance

(b) Terminal stage for alg.

(c) Solution ($\Delta^{*}=3$).

Figure 7: Challenges in extending the single-source algorithm to multiple
sources.

######  Definition 9 ($\mathcal{S}(a)$).

Let $D=(N,A)$ be an out-tree, and let $a\in A$. The _set of sources that
require $a$_, denoted $\mathcal{S}(a)$, is the set of sources $s_{k}$ for
which $a$ is on the unique $s_{k},t_{k}$-dipath in $D$. That is,
$\mathcal{S}(a):=\\{s_{k}:a\in A(P_{k}),k\in\mathcal{K}\\}.$

######  Definition 10 (Blocking source).

Let $D=(N,A)$ be an out-tree and let $a=vw$ be an arc in $A$. The _blocking
source_ of $a$, denoted $b(a)$, is the unique source $s$ in $S(a)$ such that
the $s,v$-dipath in $D$ has the fewest arcs.

Consider the instance in Figure 8, where nodes $w_{i}$ for $i\in[5]$ are
sinks, and each is labelled with the corresponding set of indices of sources.
For each arc $a$ in $D$, the chart on the right indicates the set
$\mathcal{S}(a)$ and value of $b(a)$.

$a$ | $\mathcal{S}(a)$ | $b(a)$
---|---|---
$ru$ | $\\{s_{1}\\}$ | $s_{1}$
$uv$ | $\\{s_{1},s_{2}\\}$ | $s_{2}$
$vw_{1}$ | $\\{s_{1},s_{2}\\}$ | $s_{2}$
$vw_{2}$ | $\\{s_{1},s_{3}\\}$ | $s_{3}$
$vw_{3}$ | $\\{s_{3}\\}$ | $s_{3}$
$vw_{4}$ | $\\{s_{3}\\}$ | $s_{3}$
$vw_{5}$ | $\\{s_{2}\\}$ | $s_{2}$

Figure 8: Example of blocking sources

We will present an algorithm that takes as input a target, $T$, and returns a
feasible solution $H$ with $\Delta^{+}(H)\leq T$ whenever $T\geq\Delta^{*}+1$.
We now define the contraction subroutine used to generate sub-instances of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$.

####  4.2.1 Contraction of an instance for target T

Let $\mathcal{I}=(D,\mathcal{K})$ be a feasible out-tree instance of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ with root $r$, and let
$T\in\mathbb{Z}_{>0}$. For any node ${v\in N}$, let $N^{+}_{D}(v)$ be the set
of nodes reached by arcs departing $v$ in $D$.

Suppose there is more than one non-leaf node. Let $v$ be a non-leaf node where
all nodes in $N^{+}_{D}(v)$ are leaves. That is, the subgraph of $D$ rooted at
$v$ is a claw, denoted $C_{v}$. Such a node can be found efficiently by
starting at $r$ and moving to a descendant that is not a leaf. Breaking ties
arbitrarily, let $A^{T}_{v}$ denote the $\max\\{T,|\delta^{+}_{D}(v)|\\}$ arcs
$a\in\delta^{+}_{D}(v)$ with the values of $b(a)$ with the fewest edges to
$v$. Let $B^{T}_{v}=\delta^{+}_{D}(v)\setminus A^{T}_{v}$. We write $A_{v}$
and $B_{v}$ when $T$ is clear from context. In the example in Figure 8, we see
that $C_{v}$ is a claw, and when $T=3$, $A_{v}=\\{vw_{2},vw_{3},vw_{4}\\}$ and
$B_{v}=\\{vw_{1},vw_{5}\\}$ since $b(vw_{2}),b(vw_{3}),b(vw_{4})=s_{3}=v$ and
$b(vw_{1}),b(vw_{5})=s_{2}$ which is further from $v$.

By definition, for any pair of arcs $a\in A_{v}$ and $a^{\prime}\in B_{v}$,
$b(a)$ is on the unique path in $D$ between $b(a^{\prime})$ and $v$. Let
$V(A_{v})$ denote the heads of the arcs in $A_{v}$ and let $V(B_{v})$ denote
the heads of the arcs in $B_{v}$. For the same example and target,
$V(A_{v})=\\{w_{2},w_{3},w_{4}\\}$ and $V(B_{v})=\\{w_{1},w_{5}\\}$.

We define the instance obtained from $\mathcal{I}$ by _contracting $v$ for
target $T$_, denoted $\mathcal{I}^{T}_{v}=(D^{T}_{v},\mathcal{K}^{T}_{v})$ as
follows. For all $v\neq r$, let $p(v)$ denote the parent node of $v$ in $D$.

######  Definition 11.

The instance obtained from $\mathcal{I}$ by contracting $v$ for target $T$ is
$\mathcal{I}^{T}_{v}=(D^{T}_{v},\mathcal{K}^{T}_{v})$, where

$\displaystyle E$ $\displaystyle:=\\{p(v)w:vw\in B_{v}\\},$ $\displaystyle
D^{T}_{v}$ $\displaystyle:=\left(D\setminus\delta^{+}_{D}(v)\right)\cup E,$

and the commodity set is
$\mathcal{K}^{T}_{v}=\\{(s_{k},t^{\prime}_{k}):k\in\mathcal{K}\\}$ where

$\displaystyle t^{\prime}_{k}$ $\displaystyle=\begin{cases}v,\quad~{}\mbox{if
}t_{k}\in V(A_{v})\\\ t_{k},\quad\mbox{otherwise.}\end{cases}$

An example of this contraction process is given in Figure 9. The instance is
given on the left, where the sinks are only labelled for the nodes in the claw
$C_{v}$, since this is the only set of commodities impacted by the contraction
of $v$. $\mathcal{I}^{3}_{v}$ is given on the right.

Figure 9: Example for contraction process.

Recall that for a node $v\in N$, $\mathcal{T}(v)$ denotes the set of sinks
among commodities with source $v$. That is,
$\mathcal{T}(v)=\\{t_{k}:s_{k}=v,k\in\mathcal{K}\\}$.

######  Lemma 12.

If $T\geq|\mathcal{T}(v)|$, then $\mathcal{I}^{T}_{v}$ is a feasible instance
of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$.

  * Proof.We need to show that for each commodity $k\in\mathcal{K}^{T}_{v}$, there is an $s_{k},t^{\prime}_{k}$-dipath in $D^{T}_{v}$. If $t^{\prime}_{k}\notin V(C_{v})$, then $t^{\prime}_{k}=t_{k}$, and $(s_{k},t_{k})$ was a commodity in $\mathcal{I}$. The $s_{k},t_{k}$-dipath in $D$ did not use any nodes in $C_{v}$ and so it remains in $D^{T}_{v}$.

If $t^{\prime}_{k}=v$, then there is some commodity $(s_{k},t_{k})$ in
$\mathcal{I}$ where $t_{k}\in V(C_{v})$. Since $s_{k}\neq t_{k}$, the
$s_{k},t_{k}$-dipath in $D$ consists of an $s,v$-dipath as a subpath. This
dipath is unchanged in $D_{v}^{T}$.

Finally, suppose $t^{\prime}_{k}\in V(C_{v})\setminus v$. By construction,
$t_{k}\in V(B_{v})$. Then $t^{\prime}_{k}=t_{k}$, and $(s_{k},t_{k})$ is a
commodity in $\mathcal{I}$, and $D$ contains an $s_{k},t_{k}$-dipath
consisting of an $s_{k},v$-dipath along with the arc $vt_{k}$. However, when
forming $D_{v}^{T}$ we remove the arc $vt_{k}$ and replace it with the arc
$ut_{k}$, and so the same dipath will not suffice. However, since
$T\geq|\mathcal{T}(v)|$, it follows that $s_{k}\neq v$. Thus, the
$s_{k},v$-dipath is non-trivial and consists of an $s_{k},u$-dipath along with
the arc $uv$. Then, the ${s_{k},u}$-dipath along with the arc $ut_{k}$ forms
an $s_{k},t_{k}$-dipath in $D_{v}^{T}$ as required. ∎

####  4.2.2 Algorithm

For a given a target $T$, our algorithm returns a feasible solution $H$ with
$\Delta^{+}(H)\leq T$ whenever $T\geq\Delta^{*}+1$. To guarantee the
performance of the algorithm if no such solution is produced (the algorithm
outputs the empty set), we show that in this case there is a witness set
$W,\mathcal{K}^{\prime}$ such that $\mbox{LB}^{w}(W,\mathcal{K}^{\prime})\geq
T$.

When there is a single non-leaf node, $r$, either the graph itself is the
desired solution with max out-degree at most $T$, or the set
$W=\\{r\\},\mathcal{K}^{\prime}=\mathcal{K}$ is a witness set certifying that
$\Delta^{*}\geq T$. Otherwise, we find a node, $v$, with only leaves as
descendants. Then either the subtree rooted at $v$ already provides a witness
set, or we apply the target algorithm to the instance $\mathcal{I}_{v}^{T}$.
If the algorithm produces a feasible solution $H_{v}$ to $\mathcal{I}_{v}^{T}$
with $\Delta^{+}(H_{v})\leq T$, we then extend this subgraph to a feasible
solution $H$ for $\mathcal{I}$ with $\Delta^{+}(H)\leq T$ by simply adding
back the arcs in the set $A_{v}$. The pseudocode is presented in Algorithm 2.

Input: A target $T\in\mathbb{Z}_{\geq 1}$, and an out-tree instance of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$, $\mathcal{I}=(D,\mathcal{K})$

1 $L\leftarrow\\{v\in N:\delta^{+}_{D}(v)=\emptyset\\}$

2 $I\leftarrow N\setminus L$

3 if  _$|I|=1$_ then

4 if  _$|L| >T$_ then

5 return $\emptyset$

6 return $D$

7Let $v$ be a non-leaf where $N^{+}_{D}(v)\subseteq L$

8 if  _$|\mathcal{T}(v)| >T$_ then

9 return $\emptyset$

10$H_{v}\leftarrow\mathtt{out}$-$\mathtt{tree}(\mathcal{I}^{T}_{v},T)$

11 if  _$H_{v}=\emptyset$_ then

12 return $\emptyset$

13else

14 return $H_{v}\cup A_{v}$

Algorithm 2 $\mathtt{out}$-$\mathtt{tree}(\mathcal{I},T)$

If Algorithm 2 returns the empty set, we argue by induction that there is a
witness set $W_{v},\mathcal{K}^{\prime}_{v}$ for the instance
$\mathcal{I}^{T}_{v}$ such that
$\mbox{LB}_{\mathcal{I}_{v}^{T}}^{w}(W_{v},\mathcal{K}^{\prime}_{v})\geq T$.
We then extend this pair to a witness set $W,\mathcal{K}^{\prime}$ for
$\mathcal{I}$ such that
$\mbox{LB}_{\mathcal{I}}^{w}(W,\mathcal{K}^{\prime})\geq T$. Note that we
cannot necessarily set $W=W_{v}$ and
$\mathcal{K}^{\prime}=\mathcal{K}^{\prime}_{v}$, since the commodity paths may
differ in $\mathcal{I}$ and $\mathcal{I}_{v}^{T}$. For each commodity $k$, the
corresponding source-sink pair is $(s_{k},t_{k})$ in $\mathcal{I}$ and
$(s_{k},t^{\prime}_{k})$ in $\mathcal{I}_{v}^{T}$. Let $Q_{k}$ denote the
unique $s_{k},t_{k}^{\prime}$-dipath in $D_{v}^{T}$, and recall that $P_{k}$
denotes the unique $s_{k},t_{k}$-dipath in $D$. The following lemmas relate
the cut sets in $\mathcal{I}$ and $\mathcal{I}_{v}^{T}$ for a fixed commodity
and node set.

######  Lemma 13.

Let $X\subseteq N\setminus\\{v\\}$ such that $D[X]$ is connected, and let
$k\in\mathcal{K}$. If $s_{k}\in X$ and $t^{\prime}_{k}\notin V(B_{v})$, then
$\delta^{+}_{P_{k}}(X)=\delta^{+}_{Q_{k}}(X)$.

  * Proof.If $t_{k}=v$, then $t_{k}^{\prime}=t_{k}$ and $P_{k}$ did not contain any arc from $A_{v}$ or $B_{v}$. Therefore, $P_{k}$ and $Q_{k}$ are the same, and so $\delta^{+}_{P_{k}}(X)=\delta^{+}_{Q_{k}}(X)$. The same argument holds when $t^{\prime}_{k}\neq v$.

Otherwise, $t^{\prime}_{k}=v$ and $t_{k}\neq v$. It follows that $t_{k}\in
V(A_{v})$ and so $Q_{k}$ is a subpath of $P_{k}$, giving
$\delta^{+}_{Q_{k}}(X)\subseteq\delta^{+}_{P_{k}}(X)$. Since $v\notin X$ and
$s_{k}\in X$, $\delta^{+}_{Q_{k}}(X)\neq\emptyset$. Moreover,
$|\delta^{+}_{P_{k}}(X)|\leq 1$ in general, so
$\delta^{+}_{P_{k}}(X)=\delta^{+}_{Q_{k}}(X)$. ∎

######  Lemma 14.

Suppose $|\mathcal{T}(v)|\leq T$. Let $X\subseteq N$ such that $D[X]$ is
connected, and let $k\in\mathcal{K}$. If $s_{k}\in X$, $t^{\prime}_{k}\in
V(B_{v})$, and $t^{\prime}_{k}\notin X$, then either
$\delta^{+}_{P_{k}}(X)=\delta^{+}_{Q_{k}}(X)$ or
$\delta^{+}_{Q_{k}}(X)=p(v)t^{\prime}_{k}$.

  * Proof.Since $|\mathcal{T}(v)|\leq T$ and $t_{k}^{\prime}\in V(B_{v})$, $s_{k}$ cannot be equal to $v$. Therefore, each of $P_{k}$ and $Q_{k}$ contain the same $s_{k},p(v)$-dipath in $D$, denoted $R$, as a subpath. An example is shown in Figure 10, for the commodity with source $r$ and sink $w_{1}$. The solid edges form $P_{k}$, and the dashed lines form $Q_{k}$. The subpath $R$ is the dipath that is shared by $P_{k}$ and $Q_{k}$ (the single arc $ru$ in this case).

(a) $\delta^{+}_{R}(X)\neq\emptyset$

(b) $\delta^{+}_{R}(X)=\emptyset$

Figure 10: Comparison of $\delta^{+}_{Q_{k}}(X)$ and $\delta^{+}_{P_{k}}(X)$.

If $\delta^{+}_{R}(X)\neq\emptyset$, then
$\delta^{+}_{Q_{k}}(X)=\delta^{+}_{R}(X)=\delta^{+}_{P_{k}}(X)$. So suppose
$\delta^{+}_{R}(X)=\emptyset$. Since $t^{\prime}_{k}\notin X$, it follows that
$\delta^{+}_{Q_{k}}(X)\neq\emptyset$. The only arc in $Q_{k}\setminus R$ is
the arc $p(v)t^{\prime}_{k}$. ∎

######  Proposition 15.

For each $T\in\mathbb{Z}_{>0}$, Algorithm 2 either returns a solution, $H$, to
instance $\mathcal{I}$ with $\Delta^{+}(H)\leq T$, or there is a witness set
$W,\mathcal{K}^{\prime}$ such that $\mbox{LB}^{w}(W,\mathcal{K}^{\prime})\geq
T$, certifying that $\Delta^{*}\geq T$.

  * Proof.Let $\mathcal{I}=(D,\mathcal{K})$ denote an instance of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ where $D$ is an out-tree with root $r$. Let $T$ be a positive integer. We prove the result by induction on the number of non-leaf nodes in $D$. Recall that we may assume that we are working with minimal, non-trivial instances, in the sense that all $k\in\mathcal{K}$ have $s_{k}\neq t_{k}$, $\mathcal{K}\neq\emptyset$, and any leaf node $l$ must be a sink for some commodity.

Suppose there is a single non-leaf node, $r$, as in Figure 11. Then each node
in $\delta^{+}_{D}(r)$ is a leaf. If $|\delta^{+}_{D}(r)|\leq T$, then the
graph $D$ is a solution with $\Delta^{+}(D)\leq T$. Otherwise,
${|\mathcal{T}(r)|=|N^{+}_{D}(r)|>T}$, and the witness set $W=\\{r\\}$,
$\mathcal{K}^{\prime}=\mathcal{K}$ gives the lower bound
$\mbox{LB}^{w}(W,\mathcal{K}^{\prime})=\left\lceil|\mathcal{T}(r)|/1\right\rceil\geq
T$.

Figure 11: Single non-leaf node.

Suppose the result holds for all out-tree instances with at most $d$ non-leaf
nodes, and consider an instance with $d+1$ non-leaf nodes. Let $v$ be a non-
leaf node where all nodes in $N^{+}_{D}(v)$ are leaves.

If $|\mathcal{T}(v)|>T$, then setting $W=\\{v\\}$ and
$\mathcal{K}^{\prime}=\\{k\in\mathcal{K}:s_{k}=v\\}$ gives
$\mbox{LB}^{w}(W,\mathcal{K}^{\prime})>T$, so suppose ${|\mathcal{T}(v)|\leq
T}$. Let $A_{v}$, $B_{v}$, $E$, and
$\mathcal{I}_{v}^{T}=(D_{v}^{T},\mathcal{K}_{v}^{T})$ be defined as above,
where ${A_{v}\cup B_{v}=\delta^{+}_{D}(v)}$ and for any pair $a\in A_{v}$ and
$a^{\prime}\in B_{v}$, $b(a)$ is on the unique path in $D$ between
$b(a^{\prime})$ and $v$. By Lemma 12, it follows that $\mathcal{I}^{T}_{v}$ is
a feasible out-tree instance with at most $d$ non-leaf nodes. Let
$\Delta^{*}_{v}$ denote the min-max degree of a feasible subgraph of
$\mathtt{cl}(D_{v})$ for instance $\mathcal{I}^{T}_{v}$. By induction, the
algorithm either returns a feasible subgraph
$H_{v}\subseteq\mathtt{cl}(D_{v})$ for $\mathcal{I}_{v}^{T}$ with
$\Delta^{+}(H_{v})\leq T$, or there is a witness set
$W_{v},\mathcal{K}^{\prime}_{v}$ certifying that $\Delta^{*}_{v}\geq T$.

Suppose the algorithm returns a feasible subgraph
$H_{v}\subseteq\mathtt{cl}(D_{v})$ for $\mathcal{I}^{T}_{v}$ with
$\Delta^{+}(H_{v})\leq T$. Let $H=H_{v}\cup A_{v}$, as in the example in
Figure 12. We claim that $H$ is a feasible solution for $\mathcal{I}$ with
$\Delta^{+}(H)\leq T$. Observe that $\deg^{+}_{H_{v}}(v)=0$ and $|A_{v}|\leq
T$, so $\Delta^{+}(H)\leq T$. It remains to argue that $H$ is feasible. Let
$k\in\mathcal{K}$. If $t_{k}\notin V(A_{v})$, then $(s_{k},t_{k})$ is a
commodity in $\mathcal{I}^{T}_{v}$, and so an $s_{k},t_{k}$-dipath is present
in $H_{v}\subseteq H$. Otherwise $t_{k}\in V(A_{v})$, and so there is a
commodity $(s_{k},v)$ in $\mathcal{K}^{T}_{v}$. By feasibility of $H_{v}$, $H$
contains an $s_{k},v$-dipath. With the addition of arc $vt_{k}$ in $A_{v}$ we
obtain an $s_{k},t_{k}$-dipath in $H$. Therefore, $H$ is feasible and
$\Delta^{+}(H)\leq T$.

Figure 12: Extending feasible $H_{v}$ for $\mathcal{I}_{v}^{3}$ to a feasible
solution $H$ for $\mathcal{I}$.

Suppose instead, there is a witness set $W_{v},\mathcal{K}^{\prime}_{v}$ with
$\mbox{LB}^{w}_{\mathcal{I}_{v}^{T}}(W_{v},\mathcal{K}^{\prime}_{v})\geq T$.
That is, $D_{v}^{T}[W_{v}]$ is connected,
$\emptyset\neq\mathcal{K}^{\prime}_{v}\subseteq\mathcal{K}_{v}^{T}$ such that
$s_{k}\in W_{v}$ and $t^{\prime}_{k}\notin W_{v}$ for all
$k\in\mathcal{K}^{\prime}_{v}$. Moreover, for all distinct
$k,j\in\mathcal{K}_{v}^{\prime}$,
$\delta^{+}_{Q_{k}}(W)\cap\delta^{+}_{Q_{j}}(W)=\emptyset$. Note that we may
assume $W_{v}$ does not contain any leaves in $D_{v}^{T}$, since removing a
leaf from $W_{v}$ can only increase the lower bound. So, $W_{v}\subseteq
N\setminus\\{v\\}$.

We now construct a witness set $W,\mathcal{K}^{\prime}$ for $\mathcal{I}$ such
that $\Delta^{*}\geq\mbox{LB}^{w}_{\mathcal{I}}(W,\mathcal{K}^{\prime})\geq
T$. Consider the same set of nodes $W_{v}$ and commodities
$\mathcal{K}_{v}^{\prime}$ in $D$ instead of $D_{v}^{T}$. Since no leaf node
in $D_{v}^{T}$ is in $W_{v}$, $D[W_{v}]$ is connected. Moreover, for each
$k\in\mathcal{K}_{v}$, it holds $s_{k}\in W_{v}$ and $t_{k}\notin W_{v}$.

If $\delta^{+}_{P_{k}}(W)=\delta^{+}_{Q_{k}}(W)$ for all
$k\in\mathcal{K}^{\prime}_{v}$, then it follows that $W=W_{v}$ and
$\mathcal{K}^{\prime}=\mathcal{K}^{\prime}_{v}$ gives
$\mbox{LB}_{\mathcal{I}}^{w}(W,\mathcal{K}^{\prime})=\mbox{LB}_{\mathcal{I}^{T}_{v}}^{w}(W,\mathcal{K}^{\prime}_{v})\geq
T$ as required. So, suppose there is some commodity
$k\in\mathcal{K}^{\prime}_{v}$ such that
$\delta^{+}_{P_{k}}(W)\neq\delta^{+}_{Q_{k}}(W)$. By Lemmas 13 and 14, it
follows that there is a commodity $\ell\in\mathcal{K}^{\prime}_{v}$ with
$t^{\prime}_{\ell}\in V(B_{v})$ and $p(v)\in W_{v}$.

Let $W=W_{v}\cup\\{v\\}$. Since $p(v)\in W_{v}$ and $D[W_{v}]$ is connected,
it follows that $D[W]$ is connected. Let
$\bar{\mathcal{K}}=\\{(b(vt_{k}),t_{k}):t_{k}\in V(A_{k})\\}$. By definition
of $\bar{\mathcal{K}}$ and $B_{v}$, it follows that $s_{k}$ is on the unique
dipath between $s_{\ell}$ and $v$ for all $k\in\bar{\mathcal{K}}$. Since
$D[W]$ is connected and contains both $s_{\ell}$ and $v$, it follows that
$s_{k}\in W$ for all $k\in\bar{K}$.

If there is a commodity $k\in\mathcal{K}^{\prime}_{v}$ with $t_{k}=v$, let
$k_{v}$ denote this commodity, and otherwise let $k_{v}$ denote the empty set.
Let
$\mathcal{K}^{\prime}=(\mathcal{K}^{\prime}_{v}\cup\bar{\mathcal{K}})\setminus
k_{v}$. Then $s_{k}\in W$ for all $k\in\mathcal{K}^{\prime}$, and $t_{k}\notin
W$ for each $k\in\mathcal{K}^{\prime}$ since $k_{v}$ was removed. We also
claim that $\delta^{+}_{P_{k}}(W)\cap\delta^{+}_{P_{j}}(W)=\emptyset$ for any
$k,j\in\mathcal{K}^{\prime}$. If $k\in\mathcal{K}^{\prime}$ with $t_{k}\in
N_{D}^{+}(v)$, then $\delta^{+}_{P_{k}}(W)=vt_{k}$. Otherwise, $t_{k}\notin
V(C_{v})$ and
$\delta^{+}_{P_{k}}(W)=\delta^{+}_{Q_{k}}(W)\notin\delta^{+}_{D}(v)$.
Therefore, the disjointness of the cuts follows.

In order to prove that
$\mbox{LB}^{w}_{\mathcal{I}}(W,\mathcal{K}^{\prime})\geq T$, it remains to
argue that the cardinality of $|\mathcal{K}^{\prime}|$ is at least
$(T-1)|W|+1$. Observe that by definition, if $B_{v}\neq\emptyset$, then
$|A_{v}|=T$. By induction, we have
$|\mathcal{K}^{\prime}_{v}|\geq(T-1)|W_{v}|+1$. Therefore,
$|\mathcal{K}^{\prime}|\geq(T-1)|W_{v}|+T-1+1=(T-1)|W|+1$, and so
$\mbox{LB}^{w}_{\mathcal{I}}(W,\mathcal{K}^{\prime})\geq T$ as required. ∎

See 3

  * Proof.By executing Algorithm 2 for all possible target values, we determine the smallest value of $T$ for which Algorithm 2 gives a feasible subgraph $H$ with $\Delta^{+}(H)\leq T$. Since Algorithm 2 did not return a feasible subgraph for the target $T-1$, there is a witness set $W,\mathcal{K}^{\prime}$ with $\mbox{LB}^{w}(W,\mathcal{K}^{\prime})\geq T-1$ (constructible in polytime), certifying that $\Delta^{*}\geq T-1$. Hence, $\Delta^{+}(H)\leq\Delta^{*}+1$. ∎

As previously mentioned in the discussion of lower bounds, there are out-tree
instances of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ where
$\max_{W\subseteq
N,\mathcal{K}^{\prime}\subseteq\mathcal{K}}\mathtt{LB}(W,\mathcal{K}^{\prime})=\Delta^{*}-1$.
Furthermore, the analysis of Algorithm 2 is tight since there are out-tree
instances for which the algorithm does not return a solution with out-degree
at most $T$, even if $\Delta^{*}=T$.

Consider the following instance in Figure 13(a). A solution $H$ with
$\Delta^{+}(H)=2$ is given in Figure 13(b).

(a) Out-tree instance.

(b) Solution with $\Delta^{+}(H)=2$.

Figure 13:

However, when $T=2$ in the target algorithm, in the first step we generate the
subproblem given in Figure 14 by contracting node $v$ for the target $T=2$.
The resulting problem does _not_ have a feasible solution with max out-degree
at most 2. Thus, the algorithm would not produce a feasible solution with max
out-degree 2 for the original instance in Figure 13.

Figure 14:

It remains open whether or not out-tree instances are NP-hard. In Appendix B,
we relate the hardness of these instances to that of a natural packing
problem.

##  5 Arbitrary trees

In this section, we provide a framework for obtaining approximation results
for arbitrary tree instances. As a first step, we give an efficient
2-approximation when $D$ is a star. Our framework for obtaining an
approximation algorithm for arbitrary tree instances builds on the
approximability of junction tree instances, a generalization of stars. We also
highlight the weakening strength of the witness set construction for more
complex graphs.

###  5.1 Star instances

We have the following 2-approximate solution for star instances.

######  Proposition 16.

Given a star instance, $H=\\{s_{k}t_{k}:k\in\mathcal{K}\\}$ is a feasible
solution with $\Delta^{+}(H)\leq 2\Delta^{*}$.

  * Proof.Let $H=\\{s_{k}t_{k}:k\in\mathcal{K}\\}$. That is, $H$ is the subgraph obtained by routing all the commodities directly. The maximum out-degree of $H$, $\Delta^{+}(H)$, is equal $\max_{s\in\mathcal{S}}|\mathcal{T}(s)|$. Let $s^{*}=\mbox{argmax}_{s\in\mathcal{S}}|\mathcal{T}(s)|$. If $s^{*}=v$, the center vertex, then ${W=\\{v\\}}$ and $\mathcal{K}^{\prime}=\\{k\in\mathcal{K}:s_{k}=v\\}$, we obtain the following bound on $\Delta^{*}$:

$\Delta^{*}\geq\mbox{LB}(W,\mathcal{K}^{\prime})=\left\lceil\frac{|\mathcal{T}(v)|+1-1}{1}\right\rceil=|\mathcal{T}(v)|,$

which matches the maximum out-degree of $H$. Alternatively, $s^{*}\neq v$.
Then when $W=\\{s,v\\}$ and
$\mathcal{K}^{\prime}=\\{k\in\mathcal{K}:s_{k}=s^{*}\\}$, we obtain the
following bound on $\Delta^{*}$:

$\Delta^{*}\geq\mbox{LB}(W,\mathcal{K}^{\prime})=\left\lceil\frac{(|\mathcal{T}(s_{i})|-1)+2-1}{2}\right\rceil=\left\lceil\frac{|\mathcal{T}(s_{i})|}{2}\right\rceil.$

Note that we have $|\mathcal{T}(s_{i})|-1$ since it could be that some
commodity $k\in\mathcal{K}^{\prime}$ has source $s^{*}$ and sink $v$, which
falls within $W$. Thus, we have $\Delta_{H}\leq 2\Delta^{*}$ as desired. ∎

All of the algorithms presented rely on the lower bound formulation to certify
the performance of the algorithm. However, there are instances where the best
lower bound of the form provided in Lemma 7 is at most
$\frac{2}{3}\Delta^{*}$. Thus, arguing that the performance of an
approximation algorithm for the star setting is better than a factor 3/2
cannot rely on the current lower bound construction. Future work is to find
hardness results for the star setting, and to improve upon the factor 2
algorithm.

Consider the instance of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ in
Figure 15, where there are $2n$ sinks ($\mathcal{T}$), and $m={2n\choose n}$
sources ($\mathcal{S}$). Consider the $m$ subsets of $\mathcal{T}$ of size
$n$, and order the subsets arbitrarily as $T_{1},T_{2},\cdots,T_{m}$. The
commodity set is constructed so that each source must route to one of the $m$
subsets of $n$ sinks. That is, ${\mathcal{K}=\\{(s_{i},t):i\in[m],t\in
T_{i}\\}}$.

Figure 15:

Observe that $H=\\{s_{k}t_{k}:k\in\mathcal{K}\\}$ is one solution with
$\Delta^{+}(H)=n$. Furthermore, if in any feasible solution $H$ we had that
$\deg^{+}_{H}(v)\leq n-1$, then this would imply that $\deg_{H}^{+}(s)\geq n$
for some source $s$, since $v$ did not serve any of its corresponding sinks.
Thus, $\Delta^{*}=n$. Now consider the family of lower bounds from Lemma 7. It
is not hard to see that the best lower bound possible is when
$W=\\{s_{i},s_{j},v\\}$ where $T_{i}\cap T_{j}=\emptyset$, and
$\mathcal{K}^{\prime}$ is the set of $2n$ commodities with sources in
$\\{s_{i},s_{j}\\}$. This gives a lower bound of
$\left\lceil(2n+1)/3\right\rceil$.

See 4

###  5.2 Tree instances

A tree instance of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ is a
_junction tree instance_ if there is some node $r$ in $D$ such that $r$ is a
node in $P_{k}$ for all $k\in\mathcal{K}$. Suppose we had an algorithm for
junction tree instances of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$,
$\mathcal{A}$, that returns feasible solutions with max out-degree at most a
factor $\alpha$ larger than optimal. In this section, we show how an algorithm
for junction tree instances can be used to obtain an approximation algorithm
for tree instances.

Let $\mathcal{I}=(D,\mathcal{K})$ be a tree instance of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ and let $\Delta^{*}$ denote
the minimum max out-degree of a feasible solution. For any node $v$ in $D$,
there is a set of commodities, $\mathcal{K}_{v}$, such that the dipath between
the source and sink in $D$, $P_{k}$, includes $v$. That is,

$\mathcal{K}_{v}:=\\{k\in\mathcal{K}:v\in P_{k}\\}.$

For each of the remaining commodities not in $\mathcal{K}_{v}$, the path
$P_{k}$ is fully contained in one of the components in $D-v$. Naturally, the
union of a feasible solution to the instance $(D,\mathcal{K}_{v})$ and the
instance $(D,\mathcal{K}\setminus\mathcal{K}_{v})$ is a feasible solution to
the instance $\mathcal{I}$. Moreover, the two subproblems have a particular
structure: $(D,\mathcal{K}_{v})$ is a junction tree instance, and
$(D,\mathcal{K}\setminus\mathcal{K}_{v})$ is a set of tree instances – one
defined on each component of $D-v$.

Let $v\in N$ and let $C$ be some connected component in $D-v$. Let
$\mathcal{K}(C)$ denote the set of commodities $k\in\mathcal{K}$ with
$s_{k},t_{k}\in V(C)$. That is,

$\mathcal{K}(C):=\\{k\in\mathcal{K}:s_{k},t_{k}\in V(C)\\}.$

Note that each of the tree instances in
$(D,\mathcal{K}\setminus\mathcal{K}_{v})$ is the instance $(C,\mathcal{K}(C))$
for some component $C\in D-v$, and $C$ has fewer nodes than $D$. For each
instance $(C,\mathcal{K}(C))$, we again decompose the instance into a junction
tree instance and a set of smaller tree instances. We repeat this process
until all sub-instances of $\mathcal{I}$ are either junction tree instances,
or defined on digraphs with a single node.

Suppose each node in $D$ is in at most $\beta$ of the junction tree sub-
instances of $\mathcal{I}$. Then, applying the algorithm $\mathcal{A}$ to each
of the junction tree instances and taking the union of the solutions gives a
feasible solution for $\mathcal{I}$, with max out-degree at most
$\alpha\cdot\beta$ times $\Delta^{*}$. It is not hard to show that the node
$v$ in each iteration can be chosen so that $\beta=\log(n)$. Specifically, we
select the node $v$ so that each connected component in $D-v$ has at most
$|N|/2$ nodes.

We define the following algorithm for tree instances.

Input: A tree instance $\mathcal{I}=(D,\mathcal{K})$ of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$, where $D=(N,A)$, and an
$\alpha$-approximation algorithm, $\mathcal{A}$, for junction tree instances.

1 if  _$|N|=1$_ then

2 return $(N,\emptyset)$

3Let $v$ be a node in $N$ such that each connected component in $D-v$ contains
at most $|N|/2$ nodes.

4 $H_{v}\leftarrow\mathcal{A}((D,\mathcal{K}_{v}))$

5 Let $\mathcal{C}=\\{C_{1},C_{2},\ldots,C_{\ell}\\}$ be the set of connected
components in $D-v$.

6 for  _$C\in\mathcal{C}$_ do

7 $H_{v}^{C}\leftarrow\mathtt{tree}$-$\mathtt{alg}((C,\mathcal{K}(C))$

8$H\leftarrow H_{v}\bigcup_{C\in\mathcal{C}}H_{v}^{C}$

return $H$

Algorithm 3 $\mathtt{tree}$-$\mathtt{alg}(\mathcal{I},\mathcal{A})$

######  Proposition 17.

Let $\mathcal{I}=(D,\mathcal{K})$ be a tree instance of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$. Given an
$\alpha$-approximation algorithm for junction tree instances, Algorithm 3
returns a solution $H$ for $\mathcal{I}$ with
$\Delta^{+}(H)\leq\alpha\log(n)\Delta^{*}$

  * Proof.We first argue that the solution returned is feasible. Let $k\in\mathcal{K}$. Observe that if $k\notin\mathcal{K}_{v}$, then $P_{k}$ must be fully contained in a component $C$ in $D-v$. Thus, at any point in the algorithm when a tree instance is decomposed into a junction tree instance and a set of smaller tree instances, one of the instances contains the path $P_{k}$.

Furthermore, it is clear that the minimum max out-degree of any subproblem
$\mathcal{I}^{\prime}=(D^{\prime},\mathcal{K}^{\prime})$ generated by the
algorithm provides a lower bound on $\Delta^{*}$, since any solution to
$\mathcal{I}$ must also contain a subgraph
$H^{\prime}\subseteq\mathtt{cl}(D^{\prime})$ that is a solution for
$\mathcal{I}^{\prime}$. Finally, each node is contained in at most $\log(n)$
of the subproblems on which algorithm $\mathcal{A}$ is executed. Therefore,
$\Delta^{+}(H)\leq\alpha\log(n)\Delta^{*}$ as required. ∎

Thus, we have proven the following Theorem. See 5

##  6 Conclusion

In this paper, we propose a mathematical model to determine an allocation of
sort points that provides a feasible sortation plan. Even in the case where
the underlying undirected physical network forms as tree, it is NP-hard to
determine whether a feasible sort point allocation exists. We focus on the
natural objective of minimizing the maximum number of sort points required at
a warehouse, and define the directed min-degree problem of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$.

We present a simple and efficient combinatorial algorithm for solving single-
source tree instances of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ with
a quadratic speed-up over previous algorithms. We also present a fast
combinatorial additive $1$-approximation algorithm for the out-tree setting.
Moreover we prove that our analysis is tight by exhibiting an instance where
the algorithm returns a solution that has max out-degree one greater than
optimal. We also show that there is an inherent weakness of the family of
lower bounds considered since there is a gap of one between the best lower
bound and the minimum max out-degree for out-tree instances. For star
instances of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$, there are
instances for which this gap is a multiplicative factor of $3/2$. An
improvement to the approximation guarantee for the star setting, as well as a
non-trivial approximation algorithm for junction tree instances remain open
problems. A challenging open problem lies in finding good approximation
algorithms for arbitrary graph structures.

It remains open whether or not out-tree instances are NP-hard. In Appendix B,
we relate the hardness of these instances to that of a natural packing
problem. Furthermore, due to the limited understanding of optimizing for sort
point problems, we also believe alternative objectives are of interest, such
as varying degree constraints on nodes, and determining the minimum number of
sort points required in any feasible solution. These settings are of high
relevance in applications.

Acknowledgements  We thank Sharat Ibrahimpur and Kostya Pashkovich for
valuable discussions on lower bounds and the link to matroid intersection.

## References

  * [1] N. Bansal, R. Khandekar, and V. Nagarajan.  Additive guarantees for degree-bounded directed network design.  SIAM J. Comput., 39(4):1413–1431, 2009.
  * [2] D. Chakrabarty, Y. T. Lee, A. Sidford, S. Singla, and S. C. Wong.  Faster matroid intersection.  In FOCS, pages 1146–1168. IEEE Computer Society, 2019.
  * [3] K. Chaudhuri, S. Rao, S. J. Riesenfeld, and K. Talwar.  A push-relabel algorithm for approximating degree bounded msts.  In ICALP (1), volume 4051 of Lecture Notes in Computer Science, pages 191–201. Springer, 2006.
  * [4] K. Chaudhuri, S. Rao, S. J. Riesenfeld, and K. Talwar.  What would edmonds do? augmenting paths and witnesses for degree-bounded msts.  Algorithmica, 55(1):157–189, 2009.
  * [5] V. Chvátal.  Tough graphs and hamiltonian circuits.  Discrete Math., 5:215–228, 1973.
  * [6] S. Dehghani, S. Ehsani, M. Hajiaghayi, and V. Liaghat.  Online degree-bounded steiner network design.  In SODA, pages 164–175. SIAM, 2016.
  * [7] M. Fürer and B. Raghavachari.  Approximating the minimum-degree steiner tree to within one of optimal.  Journal of Algorithms, 17:409–423, 1994.
  * [8] M. R. Garey and D. S. Johnson.  Computers and Intractability; A Guide to the Theory of NP-Completeness.  W. H. Freeman & Co., USA, 1990.
  * [9] M. X. Goemans.  Minimum bounded degree spanning trees.  In FOCS, pages 273–282. IEEE Computer Society, 2006.
  * [10] X. Guo, G. Kortsarz, B. Laekhanukit, S. Li, D. Vaz, and J. Xian.  On approximating degree-bounded network design problems.  Algorithmica, 84(5):1252–1278, 2022.
  * [11] J. Koenemann and R. Ravi.  A matter of degree: Improved approximation algorithms for degree-bounded minimum spanning trees.  SIAM Journal on Computing, 31(6):1783–1793, 2002.
  * [12] J. Koenemann and R. Ravi.  Quasi-polynomial time approximation algorithm for low-degree minimum-cost steiner trees.  In FSTTCS, volume 2914 of Lecture Notes in Computer Science, pages 289–301. Springer, 2003.
  * [13] J. Koenemann and R. Ravi.  Primal-dual meets local search: Approximating msts with nonuniform degree bounds.  SIAM J. Comput., 34:763–773, 01 2005.
  * [14] G. Kortsarz and Z. Nutov.  Bounded degree group steiner tree problems.  In IWOCA, volume 12126 of Lecture Notes in Computer Science, pages 343–354. Springer, 2020.
  * [15] D. Kozen.  The design and analysis of algorithms.  Springer Science & Business Media, 1992.
  * [16] C. L. Lara, J. Koenemann, Y. Nie, and C. C. de Souza.  Scalable timing-aware network design via lagrangian decomposition.  European Journal of Operational Research, 309(1):152–169, 2023.
  * [17] L. C. Lau, J. Naor, M. R. Salavatipour, and M. Singh.  Survivable network design with degree or order constraints.  SIAM J. Comput., 39(3):1062–1087, 2009.
  * [18] L. C. Lau and M. Singh.  Additive approximation for bounded degree survivable network design.  SIAM J. Comput., 42(6):2217–2242, 2013.
  * [19] Z. Nutov.  Approximating directed weighted-degree constrained networks.  Theoretical Computer Science, 412(8):901–912, 2011.
  * [20] R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, and H. B. H. III.  Many birds with one stone: multi-objective approximation algorithms.  In STOC, pages 438–447. ACM, 1993.
  * [21] R. Ravi and M. Singh.  Delegate and conquer: An lp-based approximation algorithm for minimum degree msts.  In ICALP (1), volume 4051 of Lecture Notes in Computer Science, pages 169–180. Springer, 2006.
  * [22] A. Schrijver.  Combinatorial Optimization $-$ Polyhedra and Efficiency.  Springer, 2003.
  * [23] M. Singh and L. C. Lau.  Approximating minimum bounded degree spanning trees to within one of optimal.  STOC ’07, page 661–670, New York, NY, USA, 2007. Association for Computing Machinery.
  * [24] J. Van Belle, P. Valckenaers, and D. Cattrysse.  Cross-docking: State of the art.  Omega, 40(6):827–846, 2012.  Special Issue on Forecasting in Management Science.
  * [25] S. Win.  On a connection between the existence of k-trees and the toughness of a graph.  Graphs and Combinatorics, 5:201–205, 1989.
  * [26] G. Yao, D. Zhu, and S. Ma.  The minimum degree spanning tree problem on directed acyclic graphs.  In Proceedings of the 6th WSEAS International Conference on Applied Computer Science, ACS’06, page 311–316. World Scientific and Engineering Academy and Society (WSEAS), 2006.
  * [27] K. Zheng.  Sort optimization and allocation planning in amazon middle mile network.  Informs, 2021.

##  Appendix A Single-source (missing proofs from Section 4.1)

In this section, we expand on the overview provided in Section 4.1, and
provide the full results for the single-source setting.

We first show that this setting reduces to the problem of min-degree
arborescence in a directed acyclic graph, which can be solved by matroid
intersection in $O(n^{3}\log n)$ time [22, 2] or a combinatorial algorithm in
$O(nm\log n)$ time [26]. We then present, in detail, the simple and fast
combinatorial algorithm for single-source tree instances of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ that offers a quadratic speed-
up over previous algorithms. While our algorithm has similarities to the one
presented in [26], we can exploit the structure of transitive closure to
reduce the number of arc swaps. We show that an efficient implementation of
our approach gives a quadratic speed-up.

######  Lemma 18.

Single-source tree instances of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ reduce to the problem of
finding a min-degree arborescence in a directed acyclic graph.

  * Proof.Let $\mathcal{I}=(D,\mathcal{K})$ be a tree instance of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ with a single source, $s$. Note that $D$ is an out-tree rooted at $s$, and $\mathtt{cl}(D)$ is a directed acyclic graph. We may assume that each leaf node in $D$ is a sink for some commodity, as otherwise this node could be removed.

It suffices to prove that there is an optimal solution that contains an
$s,v$-dipath for each node $v\in N$. Let $H$ be an arbitrary optimal solution.
Certainly if $v\in\mathcal{T}$, then an $s,v$-dipath is enforced by
feasibility. So consider some node ${v\notin\mathcal{T}}$ and suppose there is
no $s,v$-dipath in $H$. Then we may assume $v$ has no out-arcs in $H$ as
otherwise they could be removed while maintaining feasibility.

Let $T_{v}$ be the subtree in $D$ rooted at $v$. Since each leaf is a sink for
some commodity, there is some arc $e=uw$ in $\delta^{+}_{H}(N\setminus
V(\mathcal{T}_{v}))$. We obtain an optimal solution with an $s,v$-dipath by
removing arc $uw$ and adding arcs $uv$ and $vw$. Repeating this process gives
an optimal solution that is an $s$-arborescence. ∎

In a directed acyclic graph, the min-degree arborescence problem can be solved
efficiently with matroid intersection for two partition matroids [22]. Given a
bound $T$ on the maximum out-degree, the first partition matroid ensures each
node has in-degree at most one, and the second ensures each node has out-
degree at most $T$. We then run matroid intersection for $\log(n)$ many
candidate values of $T$ to find an optimal solution. More precisely, for any
candidate value $T$, we find a maximum-cardinality set (of edges) that is an
independent set in both matroids. Since the base graph is acyclic, a maximum-
cardinality independent set is an arborescence of degree bounded by $T$.

In the remainder of this section, we describe the simple combinatorial
algorithm that solves single-source instances. First, we show that in the
single-source setting, we can simplify the construction of witness sets. This
set of lower bounds allows us to look at the base graph $D$ rather than
keeping track of the commodity set. Specifically, we show that we can replace
$|\mathcal{K}^{\prime}|$ with $|\delta^{+}_{D}(W)|$ in Corollary 7 by
recalling that all nodes $v$ in $D$ with $\delta_{D}^{+}(v)=\emptyset$ must be
the sink of some commodity.

######  Corollary 19.

Suppose $\mathcal{I}=(D,\mathcal{K})$ is a tree instance and
$|\mathcal{S}|=1$. Let $W\subseteq N$ such that $s\in W$ and $D[W]$ is a
directed tree, and suppose $\delta^{+}_{D}(W)\neq\emptyset$. Then

$\Delta^{*}\geq\left\lceil\frac{|\delta^{+}_{D}(W)|+|W|-1}{|W|}\right\rceil.$

  * Proof.It suffices to show that for any such node set $W$, there is a set of commodities $\mathcal{K}^{\prime}$ with cardinality $|\delta^{+}_{D}(W)|$ such that for each $k\in\mathcal{K}^{\prime}$, $t_{k}\notin W$, and for all distinct $k,j\in\mathcal{K}^{\prime}$, $\delta^{+}_{P_{k}}(W)\cap\delta^{+}_{P_{j}}(W)=\emptyset$.

Consider an arc $e\in\delta^{+}_{D}(W)$. Since each node $v$ with
$\deg^{+}_{D}(v)=0$ is a sink for some commodity $k\in\mathcal{K}$, there must
be a commodity $k$ such that $e\in P_{k}$, and more specifically,
$e=\delta^{+}_{P_{k}}(W)$. For each arc $e\in\delta^{+}_{D}(W)$, let $k_{e}$
denote an arbitrary commodity such that $e=\delta^{+}_{P_{k_{e}}}(W)$, and let
$\mathcal{K}^{\prime}=\bigcup_{e\in\delta^{+}_{D}(W)}\\{k_{e}\\}$. Observe
that for each pair of edges $e$ and $f$ in $\delta^{+}_{D}(W)$,
$\delta^{+}_{P_{k_{e}}}(W)\cap\delta^{+}_{P_{k_{f}}}(W)=\emptyset$. Thus,
$\mathcal{K}^{\prime}$ satisfies the desired conditions. ∎

Let $\mathcal{I}=(D,\mathcal{K})$ be an instance of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$. Recall that for each
${W\subseteq N}$ and $\mathcal{K}^{\prime}\subseteq\mathcal{K}$,

$\displaystyle\mathtt{LB}_{\mathcal{I}}(W,\mathcal{K}^{\prime})$
$\displaystyle:=\begin{cases}\left\lceil\frac{|\mathcal{K}^{\prime}|+|W|-1}{|W|}\right\rceil&\mbox{if
$W,\mathcal{K}^{\prime}$ satisfy the conditions of Lemma \ref{lemma:LB_multi}
for $\mathcal{I}$}\\\ 0&\mbox{otherwise}\end{cases}$

For $W\subseteq N$ and $\mathcal{K}^{\prime}\subseteq\mathcal{K}$, we define
the following function.

$\displaystyle\mathtt{LB}_{\mathcal{I}}(W)$
$\displaystyle:=\begin{cases}\left\lceil\frac{|\delta^{+}_{D}(W)|+|W|-1}{|W|}\right\rceil&\mbox{if
$W$ satisfies the conditions of Corollary \ref{cor:LB_single_simple} for
$\mathcal{I}$}\\\ 0&\mbox{otherwise}\end{cases}$

Again, when the instance $\mathcal{I}$ is clear from context, we drop the
subscript. Observe that the two families of lower bounds have equal strength
since for any choice of ${W\subseteq N}$, the subset $\mathcal{K}^{\prime}$
that maximizes the value of $\mathtt{LB}(W,\mathcal{K}^{\prime})$ has size
$|\delta^{+}(W)|$. That is,

$\max_{W\subseteq
N,\mathcal{K}^{\prime}\subseteq\mathcal{K}}\mathtt{LB}(W,\mathcal{K}^{\prime})=\max_{W\subseteq
N}\mathtt{LB}(W).$

We will prove in Proposition 20 that for single-source instances, $\Delta^{*}$
is equal to $\max_{W\subseteq N}\mathtt{LB}(W)$. Moreover, we will prove that
$\mbox{argmax}_{W\subseteq N}\mathtt{LB}(W)$ can be found in polynomial time
as a byproduct of a exact polytime algorithm for
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ in the single-source setting.

The single-source algorithm  In the single-source setting, $D$ is a directed
out-tree rooted at the source $s$. The algorithm can be described as follows.
We begin with the feasible subgraph $H_{0}$ set to $D$. Let $H_{i}$ denote the
feasible subgraph obtained in iteration $i$. In iteration $i$, we identify a
node in $H_{i-1}$ with the highest out-degree, denoted $v^{*}$. We then
attempt to shift an arc $v^{*}w$ in $H_{i-1}$ to instead depart a node along
the $s,v^{*}$-dipath in $D$ with out-degree at most $\Delta^{+}(H_{i-1})-2$ in
$H_{i-1}$. If such a node exists, we let $u$ denote the nearest such node to
$v^{*}$ in $D$, and define $H_{i}$ as the subgraph obtained from $H_{i-1}$ by
replacing arc $v^{*}w$ with arc $uw$. If no such node exists, the algorithm
terminates with $H=H_{i-1}$. This procedure is restated in Algorithm 4, where
$P_{uv}$ is used to denote the unique dipath in $D$ from $u$ to $v$. In the
following algorithm, we define a _topological ordering_ , $\preceq$, as an
ordering of the nodes so that for any arc $uv\in A$, $u\prec v$.

1 Assign a topological ordering $\preceq$ to the nodes

2 $H_{0}\leftarrow D$

3 $i=1$

4 while  _True_ do

5 Let $v^{*}\in\mbox{argmax}_{v\in N}\deg^{+}_{H_{i-1}}(v)$

6 Let $v^{*}w\in\delta^{+}_{H_{i-1}}(v^{*})$

7 $R\leftarrow\\{u\in
V(P_{sv^{*}}):\deg_{H_{i-1}}^{+}(u)\leq\deg_{H_{i-1}}^{+}(v^{*})-2\\}$

8

9 if  _$R\neq\emptyset$_ then

10 Let $u\in R$ such that $y\preceq u$ for all $y\in R$

11 $H_{i}\leftarrow H_{i-1}\setminus\\{v^{*}w\\}\cup\\{uw\\}$

12 else

13 return $H=H_{i-1}$

14 $i=i+1$

15

Algorithm 4 Local search algorithm for the single-source setting.

Figure 16 demonstrates the steps of the algorithm when the base graph $D$ is
as provided in Figure 16(a), and $\mathcal{T}$ is the set of leaves. The
square node is the selected max out-degree node in each iteration. Observe
that in iteration 3, the set $R$ is empty and so the algorithm terminates.

(a) $H=D$

(b) Iter. 1: $v^{*}$ identified.

(c) Iter. 1: $v^{*}w$ shifted.

(d) Iter. 2: $v^{*}$ identified.

(e) Iter. 2: $v^{*}w$ shifted.

(f) Iter. 3: $v^{*}$ identified.

Figure 16: Execution of local search algorithm for single-source setting.

The following observations are used in arguing for the efficiency and
optimality of the local search algorithm.

  1. (P1)

If a vertex $u$ has $\deg_{H_{i}}^{+}(u)\geq\Delta^{+}(H_{i})-1$ in iteration
$i$, then in each subsequent iteration $j\geq i$,
$\deg_{H_{j}}^{+}(u)\geq\Delta^{+}(H_{j})-1$;

  2. (P2)

Subgraph $H_{i}$ is an $s$-arborescence in each iteration.

The first statement holds since in each iteration, the only node that
decreases in out-degree is the identified max out-degree node. Roughly, (P1)
states that once a node has high out-degree relative to other nodes in some
iteration, it may decrease in out-degree, but it remains a high out-degree
node relative to the other nodes in each iteration. The second observation
follows from the fact that $D$ is directed tree, and in each iteration $H$
remains a single connected component without increasing the number of arcs.

######  Proposition 20.

Algorithm 4 returns a feasible subgraph $H$ with $\Delta^{+}(H)=\Delta^{*}$
given an instance with a single source in $O(n^{2}\log n)$ time.

  * Proof.First, we argue that the algorithm terminates in polynomial time.

In each iteration, the out-degree of some maximum out-degree vertex is reduced
by 1. Given a maximum out-degree of $\Delta$, there are at most
$\lfloor\frac{n}{\Delta}\rfloor$ iterations until the maximum out-degree is
reduced to $\Delta-1$. Since it holds $\Delta\in[2,n-1]$ (unless the initial
maximum out-degree is equal to 1), the total number of iterations is upper
bounded by

$\sum\limits_{\Delta=2}^{n-1}\left\lfloor\frac{n-1}{\Delta}\right\rfloor=O(n\log
n).$

Since each iteration can be implemented in $O(n)$ time, the algorithm runs in
$O(n^{2}\log n)$ time.

It remains to argue that the subgraph $H$ produced by the algorithm is both
feasible and $\Delta^{+}(H)=\Delta^{*}$. The feasibility of $H$ follows from
the observation that in each iteration, for each node $v\in N$, the current
subgraph contains an $s,v$-dipath.

We now prove that $\Delta^{+}(H)=\Delta^{*}$, by presenting a witness set $W$
such that $\mathtt{LB}(W)=\Delta^{+}(H)$. Let $v^{*}$ be a max out-degree node
in $H$. We iteratively construct $W$ as follows. First, $W=V(P_{sv^{*}})$.
Note that for all $v\in V(P_{sv^{*}})$, $\deg_{H}^{+}(v)\geq\Delta^{+}(H)-1$
since the algorithm terminated. Then, while there is a node $u\notin W$ such
that in some iteration an arc $uw$ was exchanged for an arc $vw$ where $v\in
W$, we add $V(P_{su})$ to $W$. Note that if such an exchange of arcs occurred,
$u$ was a max out-degree node in some iteration $i$, and all nodes along the
$v,u$-dipath, excluding $v$, had out-degree at least $\Delta^{+}(H_{i})-1$ in
$H_{i}$. By observation $(P1)$, it follows that each such node has out-degree
at least $\Delta^{+}(H)-1$ in $H$. Thus, for each node $v\in W$,
$\deg^{+}_{H}(v)\geq\Delta^{+}(H)-1$. Figure 17 shows the node set $W$
obtained for the instance solving in Figure 16.

Figure 17: The set $W$ certifies optimality of $H$ from Figure 16(f).

Observe that $D[W]$ is connected since $W$ is formed by adding the node set of
dipaths from $s$ in $D$. As a result,

$|\delta^{+}_{H}(W)|\geq(\Delta^{+}(H)-1)|W|+1-(|W|-1)=(\Delta^{+}(H)-2)|W|+2.$

Furthermore, $W$ contains $s$ and $\delta^{+}_{D}(W)\neq\emptyset$, so $W$
satisfies the conditions of Corollary 19. Thus, it suffices to show that
$|\delta^{+}_{D}(W)|\geq|\delta^{+}_{H}(W)|$, since then

$\mathtt{LB}(W)=\left\lceil\frac{|\delta^{+}_{D}(W)|+|W|-1}{|W|}\right\rceil\geq\left\lceil\frac{(\Delta^{+}(H)-2)|W|+2+|W|-1}{|W|}\right\rceil\geq\Delta^{+}(H)$

Let $vw\in\delta^{+}_{H}(W)$. This arc corresponds to the unique arc entering
$w$ in $D$, i.e., $uw$ (where possibly $u=v$). By the iterative construction
of $W$, $u\in W$, and so $uw\in\delta^{+}_{D}(W)$. Furthermore, no two arcs in
$\delta^{+}_{H}(W)$ correspond to the same arc in $\delta^{+}_{D}(W)$ since
throughout the algorithm, the feasible subgraph remains an arborescence (and
hence the total number of arcs is unchanged). If a pair of arcs in
$\delta^{+}_{H}(W)$ were obtained via exchanges of arcs originating at the
same arc $uw$ in $\delta^{+}_{D}(W)$, then at some point in the algorithm the
number of arcs would have decreased. Thus,
$|\delta^{+}_{D}(W)|\geq|\delta^{+}_{H}(W)|$ as required. ∎

To obtain a more efficient algorithm for the single-source setting, we can
reduce the number of operations by assuming we are given a target max out-
degree, $T$. Consider a node $v$ with _more_ than $T$ nodes in $N^{+}_{D}(v)$,
and let ${\alpha_{v}=|N^{+}_{D}(v)|-T}$ denote the number of excess nodes. If
there is a solution with $\Delta^{+}(H)\leq T$, at least $\alpha_{v}$ nodes in
the set $N^{+}_{D}(v)$ must instead be reached by arcs departing a predecessor
of $v$ in $D$. We divide the set $N^{+}_{D}(v)$ into a set of _fixed nodes_ ,
$F_{v}$, of cardinality $\min\\{|N_{D}^{+}(v)|,T\\}$, and the _remaining
nodes_ $R_{v}=N_{D}^{+}(v)\setminus F_{v}$. We then generate a solution $H$,
if $T\geq\Delta^{*}$, so that $H$ contains an arc $vw$ for all $w\in F_{v}$,
and an arc $uw$ for all $w\in R_{v}$, for some predecessor of $v$ in $D$.

We store the set of descendant nodes of a node $v$ that have not yet been
allocated in a set $D_{v}$, which is built throughout the algorithm. In other
words, $D_{v}$ is the set of remaining nodes that $v$ inherited from its
descendants that have not yet been allocated to a node. Moving from the leaves
towards the root, $s$, we shift any remaining nodes in $R_{v}$ and $D_{v}$, to
the set $D_{p(v)}$, where $p(v)$ denotes the parent of $v$ in $D$. If we
encounter a node with _fewer_ than $T$ nodes in $F_{v}$, we then take a
maximum of $-\alpha_{v}$ nodes from the set $D_{v}$ and allocate them to $v$.
Note that $-\alpha_{v}=T-|N^{+}_{D}(v)|>0$ and $R_{v}=\emptyset$ for such
nodes. Since the arcs departing the max out-degree nodes in Algorithm 4 were
chosen arbitrarily, the correctness of the algorithm implies that this
procedure will produce a feasible solution $H$ with ${\Delta^{+}(H)\leq T}$,
so long as $T\geq\Delta^{*}$. For the root node in $D$, $s$, let $p(s):=s$.

Input: A target $T\in\mathbb{Z}_{\geq 1}$, and a single-source instance of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$,
$\mathcal{I}=(D,\mathcal{K})$, where $D=(N,A)$ with root $s$.

1 $V\leftarrow\\{s=v_{1},v_{2},\ldots,v_{n}\\}$, in topological order

2 $F_{v}\leftarrow\min\\{|N_{D}^{+}(v)|,T\\}$ nodes from
$N_{D}^{+}(v)~{}\forall v\in N$

3 $R_{v}\leftarrow N_{D}^{+}(v)\setminus F_{v}~{}\forall v\in N$

4 $D_{v}\leftarrow\emptyset~{}\forall v\in N$

5 $\alpha_{v}=|N_{D}^{+}(v)|-T$ for all $v\in N$

6 for  _$i=n$ to $1$_ do

7 if  _$\alpha_{v} <0$_ then

8 Let $U$ be a set of $\min\\{|D_{v}|,-\alpha_{v}\\}$ nodes from $D_{v}$

9 $D_{v}\leftarrow D_{v}\setminus U$

10 $F_{v}\leftarrow F_{v}\cup U$

11

12 $D_{p(v)}\leftarrow D_{p(v)}\cup R_{v}\cup D_{v}$

13

14if  _$D_{s}\neq\emptyset$_ then

15 return $\emptyset$

16else

17 return $H=\\{vw:w\in F_{v},v\in N\\}$

Algorithm 5 Target algorithm for the single-source setting.

######  Proposition 21.

Algorithm 5 runs in $O(n\log n)$ time, and returns a solution $H$ with
$\Delta^{+}(H)\leq T$ whenever $T\geq\Delta^{*}$.

  * Proof.The correctness of the algorithm follows directly from that of Algorithm 4.

In the first step, the topological ordering can be computed in $O(n)$ time. In
this process, for each node, we create an object that stores the parent node.
The sets of nodes $F_{v},R_{v}$, and $D_{v}$ as well as the value of
$\alpha_{v}$ are computed in $O(n)$ time. Producing $H$ given the sets $F_{v}$
also takes $O(n)$ time. It remains to argue that the for-loop can be executed
in $O(n\log n)$ operations.

This can be argued via union-find type arguments (e.g., see Lecture 10 in
[15]). We store the sets $F_{v},R_{v}$, and $D_{v}$ as linked lists, with each
element storing both a pointer to the next element, as well as a pointer to
the head of its list. The union of two lists of length $L_{A}$ and $L_{B}$
takes $O(\min(L_{A},L_{B}))$ time, by splicing the shorter list into the
longer list. Then, each element $x$ has its head pointer updated at most $\log
n$ times.

Our algorithm has the added complication that elements are _removed_. Since we
remove an arbitrary set of nodes for a fixed size, $-\alpha$, this can be done
in $O(-\alpha)$, since we can select the first $-\alpha$ nodes after the head
of the list (or the entire list). Furthermore, each node is deleted at most
once, and so the total operations for deletion is $O(n)$.

To maintain that element $x$ has its head pointer updated at most $\log n$
times in the union operations, instead of splicing the shorter of the two sets
into the larger one, we measure the lengths of the sets _as though no
deletions have occurred_. Therefore the runtime of the algorithm is $O(n\log
n)$ as claimed. ∎

See 2

  * Proof.By executing Algorithm 5 for $\log n$ many possible target values, we determine the smallest value of $T$ for which Algorithm 5 gives a feasible subgraph $H$ with $\Delta^{+}(H)\leq T$. Since Algorithm 5 did not return a feasible subgraph for the target $T-1$, $\Delta^{*}>T$. Therefore, $\Delta^{+}(H)=\Delta^{*}$. ∎

##  Appendix B Out-tree hardness

It remains open whether or not out-tree instances of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ are NP-hard. Establishing
hardness for this setting would demonstrate that our additive 1-approximation
algorithm was the best possible in Section 4. Even in the seemingly simple
case of _broom instances_ – instances in which the underlying undirected graph
of $D$ is a broom – appears challenging. In this section we demonstrate that
broom instances are at least as hard as a particular packing problem, so long
as its inputs are polynomially bounded. We believe this packing problem is of
independent interest, and establishing it is strongly NP-hard is one avenue to
proving that $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ is NP-hard on
brooms, and out-trees more generally.

$\mathtt{SIGNED}$-$\mathtt{VALUES}$-$\mathtt{BIN}$-$\mathtt{PACKING}$
($\mathtt{SV}$-$\mathtt{BP}$): Given a set
$\mathcal{W}=\\{w_{1},w_{2},\ldots,w_{n}\\}$ of $n$ integers, determine if
there is a partition of $[n]$ into sets $N_{1},N_{2},\ldots,N_{\ell}$ for some
$\ell\in[n]$ such that for each part $i\in[\ell]$, $\sum_{j\in N_{i}}w_{j}\leq
1$.

Note that we may assume that none of the input integers are 0 or 1, since
$\mathcal{W}$ is a $\mathtt{YES}$-instance if and only if
$\mathcal{W}^{\prime}=\\{w_{i}:w_{i}\in\mathcal{W},w_{i}\notin\\{0,1\\}\\}$ is
a $\mathtt{YES}$-instance. In the proof of Lemma 23, we establish that broom
instances of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ are at least as
hard as the problem of $\mathtt{SV}$-$\mathtt{BP}$ when the integers are
bounded by a polynomial in $n$. Thus, establishing that
$\mathtt{SV}$-$\mathtt{BP}$ is strongly NP-hard would prove that
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ on brooms (and thus out-trees)
is NP-hard.

######  Open question 22.

Is $\mathtt{SV}$-$\mathtt{BP}$ strongly NP-hard?

######  Lemma 23.

Broom instances of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$ are at
least as hard as $\mathtt{SV}$-$\mathtt{BP}$ with weights that are polynomial
in $n$.

  * Proof.We show that there is a reduction from $\mathtt{SV}$-$\mathtt{BP}$ to broom instances of $\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$, when the integers are polynomial in $n$. Let $\mathcal{W}=\\{w_{1},w_{2},\ldots,w_{n}\\}$ be the input integers of an instance of $\mathtt{SV}$-$\mathtt{BP}$, where the integers are polynomial in $n$, $w_{1}\geq w_{2}\geq\ldots,w_{n}$. We say that a partition of $\mathcal{W}$ is _valid_ if each part sums to at most 1.

Let $T\geq 2$. We will construct a broom instance of
$\mathtt{min}$-$\mathtt{degree}$-$\mathtt{SPP}$, with sets of sources
$S_{1},S_{2},\ldots,S_{n}$, so that there is solution with max out-degree $T$
if and only if the weakly-connected sets of sources in an optimal solution
corresponds to a valid partition of the index set $[n]$. We construct a
corresponding instance of the broom problem with target $T$ as follows.

Construction of broom instance, given $T\geq 2$: we create a set of sources,
$S_{i}$, for each index $i\in[n]$. In this set, we generate $\alpha_{i}+1$
sources, where $\alpha_{i}$ is the smallest positive integer such that
$w_{i}+\alpha_{i}(T-1)\geq 0$. Let $\beta_{i}:=w_{i}+\alpha_{i}(T-1)$. We
introduce $\beta_{i}+T-1$ sinks,
$T_{i}=\\{t_{i}^{1},t_{i}^{2},\ldots,t_{i}^{\beta_{i}+T-1}\\}$.

We construct a set $\mathcal{K}_{i}$ of commodities with sources in $S_{i}$
and sinks in $T_{i}$ as follows. The first source, $s^{1}_{i}$, is assigned
$\beta_{i}$ sinks. The final source, $s_{i}^{\alpha_{i}+1}$ is assigned the
remaining $T-1$ sinks. Finally, we ensure that each source in $S_{i}$ must
have a path to a common sink node by defining a commodity with source $s$ and
sink $t_{i}^{\beta_{i}+1-1}$ for each source $s\in S_{i}$. Specifically, we
have the following commodities.

    * $\bullet$

$\\{(s_{i}^{1},t_{i}^{j}):j\in[\beta_{i}]\\}$

    * $\bullet$

$\\{(s_{i}^{\alpha_{i}+1},t_{i}^{j}):j\in[\beta_{i}+T-1]\setminus[\beta_{i}]\\}$

    * $\bullet$

$\\{(s_{i}^{j},t_{i}^{\beta_{i}+T-1}):j\in[\alpha_{i}]\\}$

Note that each node in $\\{s_{i}^{2},\ldots,s_{i}^{\beta_{i}+T-2}\\}$ is the
source of only a single commodity.

The corresponding broom instance $\mathcal{I}=(D,\mathcal{K})$ has the digraph
$D$ as depicted in Figure 18, with a dipath on the source sets $S_{1}$ to
$S_{n}$, and the sinks are the leaves. The commodity set is
$\mathcal{K}=\cup_{i\in[n]}\mathcal{K}_{i}$.

Figure 18: Digraph $D$ for the broom instance.

We now prove that $\Delta^{*}\leq T$ if and only if there is a valid partition
of $\mathcal{W}$.

$(\Rightarrow)$ Suppose there is a solution, $H$, to the instance
$\mathcal{I}=(D,\mathcal{K})$ with ${\Delta^{+}(H)\leq T}$. The solution
splits into weakly-connected components, $H_{1},H_{2},\ldots,H_{\ell}$. Recall
that each set of sources $S_{i}$ will be in the same weakly-connected
component due to the shared sink, $t_{i}^{\beta_{i}+T-1}$. For each component
$j\in[\ell]$, let ${N_{j}=\\{i:S_{i}\in H_{j}\\}}$. We will prove that
$N_{1},N_{2},\ldots,N_{\ell}$ is a valid partition of $\mathcal{W}$.

Let $\mathcal{S}_{j}$ and $\mathcal{T}_{j}$ denote the set of sources and
sinks in component $H_{j}$ respectively. By definition of $N_{j}$, it follows
that $\mathcal{S}_{j}=\bigcup_{i\in N_{j}}S_{i}$ and
$\mathcal{T}_{j}=\bigcup_{i\in N_{j}}T_{i}$. Furthermore, the node set of
$H_{j}$ is $\mathcal{S}_{j}\cup\mathcal{T}_{j}$. The fewest arcs possible for
the subgraph $H_{j}$, since it is weakly-connected, is
$|\mathcal{S}_{j}|+|\mathcal{T}_{j}|-1$. Since every arc in $H_{i}$ departs a
node in $\mathcal{S}_{j}$, $\Delta^{+}(H_{j})\leq T$ implies that
$\frac{|\mathcal{S}_{j}|+|\mathcal{T}_{j}|-1}{|\mathcal{S}_{j}|}\leq T$.
Therefore,

$\displaystyle|\mathcal{S}_{j}|+|\mathcal{T}_{j}|-1\leq T|\mathcal{S}_{j}|$
$\displaystyle\iff$ $\displaystyle\sum_{i\in N_{j}}(\alpha_{i}+1)+\sum_{i\in
N_{j}}(\beta_{i}+T-1)-1\leq T\sum_{i\in N_{j}}(\alpha_{i}+1)$
$\displaystyle\iff$ $\displaystyle\sum_{i\in
N_{j}}\alpha_{i}+|N_{j}|+\sum_{i\in
N_{j}}(w_{i}+\alpha_{i}(T-1))+(T-1)|N_{j}|-1\leq T\sum_{i\in
N_{j}}\alpha_{i}+T|N_{j}|$ $\displaystyle\iff$ $\displaystyle\sum_{i\in
N_{j}}\alpha_{i}+\sum_{i\in N_{j}}(w_{i}+\alpha_{i}(T-1))-1\leq T\sum_{i\in
N_{j}}\alpha_{i}$ $\displaystyle\iff$ $\displaystyle\sum_{i\in
N_{j}}\alpha_{i}+\sum_{i\in N_{j}}w_{i}+T\sum_{i\in
N_{j}}\alpha_{i}-\sum_{i\in N_{j}}\alpha_{i}-1\leq T\sum_{i\in
N_{j}}\alpha_{i}$ $\displaystyle\iff$ $\displaystyle\sum_{i\in N_{j}}w_{i}\leq
1.$

Since this holds for each $j\in[\ell]$, the partition
$N_{1},N_{2},\ldots,N_{\ell}$ satisfies ${\sum_{i\in N_{j}}w_{i}\leq 1}$ for
each $j\in[\ell]$.

$(\Leftarrow)$ Suppose there is a valid partition,
$N_{1},N_{2},\ldots,N_{\ell}$, for $\mathcal{W}$. We will form a solution $H$
to the broom instance $\mathcal{I}=(D,\mathcal{K})$, consisting of $\ell$
connected components, $H_{1},H_{2},\ldots,H_{\ell}$, where each component has
maximum out-degree at most $T$.

Construction of $H_{j}$. Let $j\in[\ell]$ and let
$\mathcal{S}_{j}=\bigcup_{i\in N_{j}}S_{i}$ and $\mathcal{T}_{j}=\bigcup_{i\in
N_{j}}T_{i}$. First, $H_{j}$ is formed by taking the unique dipath in
$\mathtt{cl}(D)$ on the nodes in $\mathcal{S}_{j}$. Let $\mathcal{P}_{j}$
denote this path. It remains to add arcs to each of the sinks in
$\mathcal{T}_{j}$ so that there is an $s_{k},t_{k}$-dipath for each commodity
$k\in\mathcal{K}_{i}$, for each $i\in N_{j}$, while ensuring that
$\Delta^{+}(H_{j})\leq T$.

Let $\\{s_{1},s_{2},\ldots,s_{|\mathcal{S}_{j}|}\\}$ be the set of sources in
$\mathcal{S}_{j}$, ordered so that there is an ${s_{i},s_{j}}$-dipath in $D$
whenever $i\leq j$. Let $\\{t_{1},t_{2},\ldots,t_{|\mathcal{T}_{j}|}\\}$ be
the set of sinks in $\mathcal{T}_{j}$, ordered first by increasing subscript,
and then increasing superscript (top to bottom from Figure 18).

We add arcs to $H_{j}$ from $\mathcal{S}_{j}$ to $\mathcal{T}_{j}$ as follows.
First we add an arc from $s_{|\mathcal{S}_{j}|}$ to each of the final $T$
sinks in $\mathcal{T}_{j}$. In decreasing order of sources, we continue to add
arcs from the current sink to the last $T-1$ sinks remaining in
$\mathcal{T}_{j}$, until no sinks remain, or we run out of sources. Observe
that the resulting graph, $H_{j}$, has $\Delta^{+}(H_{j})\leq T$.

If $|\mathcal{T}_{j}|\leq(T-1)|\mathcal{S}_{j}|+1$, then $H_{j}$ will include
all sinks in $\mathcal{T}_{j}$. This is indeed the case, since

$\displaystyle|\mathcal{T}_{j}|\leq(T-1)|\mathcal{S}_{j}|+1\iff|\mathcal{T}_{j}|+|\mathcal{S}_{j}|-1\leq
T|\mathcal{S}_{j}|\iff\sum_{i\in N_{j}}w_{i}\leq 1,$

as proven in the previous direction.

Thus, it remains to show that for each commodity $k\in\mathcal{K}$ with
$s_{k}\in\mathcal{S}_{j}$ and $t_{k}\in\mathcal{T}_{j}$, there is an
$s_{k},t_{k}$-dipath in $H_{j}$. We prove the following claims, and recall
that we may assume all weights $w_{i}$ are not equal to 0 or 1.

Claim 1: If $w_{i}\geq 2$, then $|T_{i}|\geq|S_{i}|T$.

_Proof._ If $w_{i}\geq 2$, then $\alpha_{i}=1$ and $|S_{i}|=2$. Furthermore,
it holds that ${\beta_{i}=w_{i}+(T-1)\geq T+1}$, and so
$|T_{i}|=\beta_{i}+T-1\geq 2T$. Therefore, $|T_{i}|\geq|S_{i}|T$.

Claim 2: If $w_{i}\leq 0$, then $|T_{i}|\leq|S_{i}|(T-1)$.

_Proof._ If $-(T-1)\leq w_{i}\leq 0$, then $\alpha_{i}=1$ and $|S_{i}|=2$.
Furthermore, it must be that $0\leq\beta_{i}\leq T-1$ and so
$|T_{i}|=\beta_{i}+T-1\leq 2T-2$. Thus, it is $|T_{i}|\leq|S_{i}|(T-1)$.

If instead $w_{i}<-(T-1)$, then $\alpha_{i}\geq 2$, and $|S_{i}|\geq 3$.
Furthermore, it holds $\beta_{i}\leq T$, and so $|T_{i}|\leq 2T-1$. Note that
for all $T\geq 0$, we have $2T-1\leq 3(T-1)$. Thus, $|T_{i}|\leq
3(T-1)\leq|S_{i}|(T-1)$.

For a contradiction, suppose there is some commodity with source $s_{p}$ and
sink $t_{q}$ (indices from ordered nodes in $\mathcal{S}_{j}$ and
$\mathcal{T}_{j}$), such that $H_{j}$ contains no ${s_{p},t_{q}}$-dipath.
Moreover, among all commodities of this form, assume that $p$ is the largest
possible index. Since there is no $s_{p},t_{q}$-dipath, the arc from
$\mathcal{S}_{j}$ to $t_{q}$ departs a node $s_{r}$ with $r<p$. Similarly,
since there is no $s_{p},t_{q}$-dipath in $H_{j}$, it follows that

$\displaystyle|\bigcup_{r\geq
p}\mathcal{T}(s_{r})|>(|\mathcal{S}_{j}|-p+1)(T-1)+1.$ (1)

Since $|\mathcal{T}(s_{i}^{r})|\leq T-1$ whenever $r\geq 2$, and $p$ is the
largest index such that there is no $s_{p},t$ dipath for some
$t\in\mathcal{T}(s_{p})$, it follows that $s_{p}=s_{i}^{1}$ for some ${i\in
N_{j}}$. Thus, an equivalent statement to (1) is

$\displaystyle\sum_{r\in N_{j}:r\geq i}|T_{r}|>1+\sum_{r\in N_{j}:r\geq
i}|S_{r}|(T-1).$ (2)

Due to the ordering of the sets $S_{1}$ to $S_{n}$ in $D$ and by Claim 2,
inequality (2) cannot be satisfied if $w_{i}\leq 0$. Alternatively, $w_{i}\geq
2$. By Claim 1 and the ordering of the source sets,

$\displaystyle\sum_{r\in N_{j}:r<i}|T_{r}|\geq\sum_{r\in N_{j}:r<i}|S_{r}|T.$
(3)

But then by combining inequalities (2) and (3), we see that
$|\mathcal{T}_{j}|>|\mathcal{S}_{j}|(T-1)+1$, a contradiction. Therefore,
$H_{j}$ is feasible as claimed, and $\Delta^{*}\leq T$. ∎