# Strong arc decompositions of split digraphs††thanks: Research supported by
the Independent Research Foundation of Denmark under grant number DFF
7014-00037B

J. Bang-Jensen Department of Mathematics and Computer Science, University of
Southern Denmark, Odense Denmark. (email<EMAIL_ADDRESS>Y. Wang School of
Mathematics, Shandong University, Jinan 250100, China and Department of
Mathematics and Computer Science, University of Southern Denmark, Odense
Denmark. (email:yunwang<EMAIL_ADDRESS>
###### Abstract

A strong arc decomposition of a digraph $D=(V,A)$ is a partition of its arc
set $A$ into two sets $A_{1},A_{2}$ such that the digraph $D_{i}=(V,A_{i})$ is
strong for $i=1,2$. Bang-Jensen and Yeo (2004) conjectured that there is some
$K$ such that every $K$-arc-strong digraph has a strong arc decomposition.
They also proved that with one exception on 4 vertices every 2-arc-strong
semicomplete digraph has a strong arc decomposition. Bang-Jensen and Huang
(2010) extended this result to locally semicomplete digraphs by proving that
every 2-arc-strong locally semicomplete digraph which is not the square of an
even cycle has a strong arc decomposition. This implies that every 3-arc-
strong locally semicomplete digraph has a strong arc decomposition. A split
digraph is a digraph whose underlying undirected graph is a split graph,
meaning that its vertices can be partioned into a clique and an independent
set. Equivalently, a split digraph is any digraph which can be obtained from a
semicomplete digraph $D=(V,A)$ by adding a new set $V^{\prime}$ of vertices
and some arcs between $V^{\prime}$ and $V$. In this paper we prove that every
3-arc-strong split digraph has a strong arc decomposition which can be found
in polynomial time and we provide infinite classes of 2-strong split digraphs
with no strong arc decomposition. We also pose a number of open problems on
split digraphs.

Keywords: Split digraph; semicomplete digraph, strong arc decomposition,
branchings

##  1 Introduction

Notation follows [4] so we only repeat a few definitions here (see also
Section 2). A digraph is not allowed to have parallel arcs or loops. A
directed multigraph can have parallel arcs but no loops. A directed multigraph
is semicomplete if it has no pair of non-adjacent vertices.

A directed multigraph $D$ is strong if there exists a path from $x$ to $y$ in
$D$ for every ordered pair of distinct vertices $x$, $y$ of $D$ and $D$ is
$k$-arc-strong if $D\setminus{}A^{\prime}$ is strong for every subset
$A^{\prime}\subseteq A(D)$ of size at most $k-1$. A strong arc decomposition
of a directed multigraph $D=(V,A)$ is a decomposition of its arc set $A$ into
two subsets $A_{1}$ and $A_{2}$ such that $A_{1}\cap A_{2}=\emptyset$ and both
of the spanning subdigraphs $D_{1}=(V,A_{1})$ and $D_{2}=(V,A_{2})$ are
strong. Note that a directed multigraph with a strong arc decomposition must
be 2‐arc‐strong.

###### Theorem 1.1

[12] It is NP-complete to decide whether a digraph has a strong arc
decomposition.

In fact it was shown in [12] that the problem is already NP-complete for
2-regular digraphs.

An out-branching (resp., in-branching) of $D$ is a spanning oriented tree in
which every vertex except one, called the root, has in-degree (resp., out-
degree) one in $D$. Thomassen [17] made the following difficult conjecture.

###### Conjecture 1.1

There exists an integer $K$ such that every $K$-arc-strong digraph $D=(V,A)$
has an out-branching rooted at $u$ which is arc-disjoint from some in-
branching rooted at $v$ for every choice of $u,v\in V$.

Clearly, a strong digraph contains an out-branching (resp., an in-branching)
with arbitrary given root so the following conjecture by Bang-Jensen and Yeo
would imply Conjecture 1.1.

###### Conjecture 1.2

[11] There exists an integer $K$ such that every $K$-arc-strong digraph has a
strong arc decomposition.

Bang-Jensen and Yeo gave a characterization of semicomplete digraphs with a
strong arc decomposition. This characterization implies that every 3-arc-
strong semicomplete digraph has a strong arc decomposition.

###### Theorem 1.2

[11] A 2‐arc‐strong semicomplete digraph $D$ has a strong arc decomposition if
and only if $D$ is not isomorphic to the digraph $S_{4}$ depicted in Figure 2.
Furthermore, a strong arc decomposition of $D$ can be obtained in polynomial
time when it exists.

Bang‐Jensen and Huang extended Theorem 1.2 to a super class of semicomplete
digraphs, namely locally semicomplete digraphs. A digraph is locally
semicomplete if every two vertices with a common out‐ or in‐neighbor have an
arc between them. The square of a directed cycle $v_{1}v_{2}\cdots v_{n}v_{1}$
is obtained by adding an arc from $v_{i}$ to $v_{i+2}$ for every $i\in[n]$,
where $v_{n+1}=v_{1}$ and $v_{n+2}=v_{2}$. Note that $S_{4}$ above is the
square of a 4-cycle.

###### Theorem 1.3

[7] A 2‐arc‐strong locally semicomplete digraph $D$ has a strong arc
decomposition if and only if $D$ is not the square of an even cycle. Every
3-arc-strong locally semicomplete digraph has a strong arc decomposition and
such a decomposition can be obtained in polynomial time.

Let $D$ be a digraph with vertex set $\\{v_{i}:i\in[n]\\}$, and let
$H_{1},\ldots,H_{n}$ be digraphs which are pairwise vertex-disjoint. The
composition $D[H_{1},\ldots,H_{n}]$ is the digraph $Q$ with vertex set
$V(H_{1})\cup\cdots\cup V(H_{n})$ and arc set
$(\bigcup_{i=1}^{n}A(H_{i}))\cup\\{h_{i}h_{j}:h_{i}\in V(H_{i}),h_{j}\in
V(H_{j}),v_{i}v_{j}\in A(D)\\}$. A composition $D[H_{1},\ldots,H_{n}]$ is
called semicomplete composition if $D$ is semicomplete.

Sun, Gutin and Ai [15] gave a characterization of a subset of semicomplete
compositions with a strong arc decomposition. Later, Bang-Jensen, Gutin and
Yeo solved the problem for all semicomplete compositions as follows, here
$C_{n},K_{n}$ and $P_{n}$ denote the directed cycle, the complete digraph and
the directed path on $n$ vertices, respectively.

###### Theorem 1.4

[5] Let T be a strong semicomplete digraph on $t\geq 2$ vertices and let
$H_{1},\ldots,H_{t}$ be arbitrary digraphs. Then $Q=T[H_{1},\ldots,H_{t}]$ has
a strong arc decomposition if and only if $D$ is 2‐arc‐strong and is not
isomorphic to one of the following four digraphs: $S_{4}$,
$C_{3}[\overline{K}_{2},\overline{K}_{2},\overline{K}_{2}]$,
$C_{3}[\overline{K}_{2},\overline{K}_{2},P_{2}]$ and
$C_{3}[\overline{K}_{2},\overline{K}_{2},\overline{K}_{3}]$. In particular,
every 3-arc-strong semicomplete composition has a strong arc decomposition.

A split digraph is a digraph whose vertex set is a disjoint union of two non-
empty sets $V_{1}$ and $V_{2}$ such that $V_{1}$ is an independent set and the
subdigraph induced by $V_{2}$ is semicomplete. We use the notation
$D=(V_{1},V_{2};A)$ to denote a split digraph $D$. This class of digraphs has
not been studied in many papers. In fact, our definition of a split digraph is
different from that in [13, 14] but is very similar to the definition used in
[1]. Recall that an undirected graph is a split graph if its vertex set can be
partitioned into an independent set and a clique. So by our definition, a
split digraph is simply any digraph whose underlying undirected graph is a
split graph. It should be noted that problems for split digraphs are often
much harder than the corresponding problem for semicomplete digraphs. One
example is the hamiltonian cycle problem which is easy for semicomplete
digraphs (a semicomplete digraph has a hamiltonian cycle if and only if it is
strongly connected) but the complexity of the hamiltonian cycle problem is
open already for split digraphs with only two vertices in the independent set.
For split digraphs which become semicomplete after deletion of some vertex,
the hamiltonian cycle problem is equivalent to deciding the existence of a
hamiltonian path with prescribed starting and ending vertices and hence
polynomial (but highly non-trivial) by [8].

It was shown in [9] that it is NP-complete to decide for a given semicomplete
digraph $D=(V,A)$ and a subset $A^{\prime}\subset A$ whether $D$ has a
hamiltonian cycle containing all arcs of $A^{\prime}$. This immediately
implies the following (for each arc $uv\in A^{\prime}$ add a new vertex
$x_{uv}$ and arcs $ux_{uv},x_{uv}v$).

###### Theorem 1.5

The hamiltonian cycle problem is NP-complete for split digraphs.

As mentioned above the following conjecture is open already for $k=2$ (note
that a digraph obtained as described below may not be a split digraph as we
may add arcs between new vertices).

###### Conjecture 1.3

[3] For every fixed integer $k$ there exists a polynomial algorithm for
deciding if there is a hamiltonian cycle in a given digraph which is obtained
from a semicomplete digraph by adding $k$ new vertices and some arcs.

Based on this conjecture and the discussion on page 290 in [4] we conjecture
the following.

###### Conjecture 1.4

For every fixed integer $k$ the hamiltonian cycle problem is polynomial for
the class of split digraphs $D=(V_{1},V_{2};A)$ where the independent set
$V_{1}$ has size at most $k$.

In this paper, we study strong arc decompositions of split digraphs. Our main
result is the following.

###### Theorem 1.6

Let $D=(V_{1},V_{2};A)$ be a 2-arc-strong split digraph such that $V_{1}$ is
an independent set and the subdigraph induced by $V_{2}$ is semicomplete. If
every vertex of $V_{1}$ has both out- and in-degree at least 3 in $D$, then
$D$ has a strong arc decomposition.

###### Corollary 1

Every 3-arc-strong split digraph has a strong arc decomposition.

The paper is organized as follows. Section 2 provides additional terminology
and notation and preliminary results. The proof of our main result, Theorem
1.6, is given in Section 3. In Section 4, we show some results on arc-disjoint
in- and out-branchings in split digraphs and we provide an infinite family of
split digraphs which shows that vertex-connectivity 2 is not sufficient to
guarantee the existence of a strong arc decomposition in split digraphs
(Corollary 5). Finally we list some open problems in Section 5.

##  2 Preliminaries

Let $D$ be a directed multigraph and let $X$ be a subset of $V(D)$. We use
$D\left\langle X\right\rangle$ to denote the directed multigraph induced by
$X$. Let $D-X=D\left\langle V\backslash X\right\rangle$. We often identify a
subdigraph $H$ of $D$ with its vertex set $V(H)$. For example, we write $D-H$
and $v\in H$ instead of $D-V(H)$ and $v\in V(H)$.

In this paper a cycle and a path always means a directed cycle and path. For
subsets $X,Y$ of $V(D)$, a path $P$ is an $(X,Y)$-path if it starts at a
vertex $x$ in $X$ and ends at a vertex $y$ in $Y$ such that $V(P)\cap(X\cup
Y)=\\{x,y\\}$. For a path $P$, we use $P[x,y]$ to denote the subpath of $P$
from $x$ to $y$. For every digraph $D$, we can label its strong components
$C_{1},\ldots{},C_{p}$ ($p\geq 1$) such that there is no arc from $C_{j}$ to
$C_{i}$ when $j>i$. We call such an ordering an acyclic ordering of the strong
components of $D$. For a semicomplete digraph $D$ it is easy to see that the
ordering $C_{1},\ldots{},C_{p}$ ($p\geq 1$) is unique and we call $C_{1}$
(resp., $C_{p}$) the initial (resp., terminal) strong component of $D$.

###  2.1 Nice decompositions of strong digraphs

A vertex decomposition of a digraph $D$ is a partition of its vertex set
$V(D)$ into disjoint sets $(U_{1},\ldots,U_{l})$ ($l\geq 1$). The index of a
vertex $v$ in the decomposition, denoted by $ind(v)$, is the index $i$ such
that $v\in U_{i}$. An arc $xy$ is called a backward arc if $ind(x)>ind(y)$.
The following decomposition, introduced in [6], plays an important role in our
proof of Theorem 1.6. A nice decomposition of a digraph $D$ is a vertex
decomposition such that $D\left\langle U_{i}\right\rangle$ is strong for all
$i\in[l]$ and the set of cut‐arcs of $D$ is exactly the set of backward arcs.

###### Theorem 2.1

[6] Every strong semicomplete digraph $D$ of order at least 4 admits a unique
nice decomposition. Furthermore, the nice decomposition can be constructed in
polynomial time.

Given a semicomplete digraph and its nice decomposition, the natural ordering
of its backward arcs is the ordering of these in decreasing order according to
the index of their tails.

###### Proposition 2.2

[6] Let $D$ be a strong semicomplete digraph of order at least 4. Suppose that
$(U_{1},\ldots,U_{l})$ is the nice decomposition of $D$ and
$(x_{1}y_{1},\ldots,x_{r}y_{r})$ is the natural ordering of the backward arcs.
Then the following statements hold.

(i) $x_{1}\in U_{l}$ and $y_{r}\in U_{1}$;

(ii) $ind(y_{j+1})<ind(y_{j})\leq ind(x_{j+1})<ind(x_{j})$ for all $j\in[r-1]$
and $ind(y_{j+1})\leq ind(x_{j+2})<ind(y_{j})$ for all $j\in[r-2]$.

$U_{1}$$U_{2}$$U_{3}$$U_{4}$$U_{5}$$y_{2}$$y_{3}$$x_{1}$$y_{1}$$x_{3}$ Figure
1: An illustration of a nice decomposition $(U_{1},\ldots,U_{5})$. The
backward arcs are $\\{x_{1}y_{1},x_{2}y_{2},x_{3}y_{3}\\}$ with $x_{2}=y_{1}$.
All arcs between different $U_{i}$s which are not shown are from left to
right.

###  2.2 Strong arc decompositions of semicomplete directed multigraphs

Bang-Jensen, Gutin and Yeo generalized Theorem 1.2 to semicomplete directed
multigraphs. The characterization below turns out to be extremely useful in
our proof of Theorem 1.6.

###### Theorem 2.3

[5] A 2‐arc‐strong semicomplete directed multigraph $D=(V,A)$ on $n\geq 4$
vertices has a strong arc decomposition if and only if it is not isomorphic to
one of the exceptional digraphs depicted in Figure 2. Furthermore, a strong
arc decomposition of $D$ can be obtained in polynomial time when it exists.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$ $S_{4}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$ $S_{4,1}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$ $S_{4,2}$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$ $S_{4,3}$

Figure 2: 2-arc-strong directed multigraphs without strong arc decompositions.

###  2.3 Splitting off arcs

We now introduce a very useful operation that can be used to obtain various
semicomplete directed multigraphs on the vertex set $V_{2}$ from a split
digraph $D=(V_{1},V_{2};A)$. This will allow us to apply Theorem 2.3 and Lemma
2.4 below in many cases to obtain the desired result for $D$.

###### Definition 1

Suppose that $D=(V_{1},V_{2};A)$ is a split digraph and that $ut$ and $tv$
with $u\neq v$ are two arcs incident to a vertex $t\in V_{1}$. Splitting off
the pair $(ut,tv)$ at $t$ means that we replace the arcs $ut,tv$ by a new arc
$uv$ (or a copy of that arc if it already exists). The arc $uv$ is called a
splitting arc. The reverse operation where we replace a splitting arc by the
two original arcs is called lifting the arc.

###### Definition 2

Suppose that $P$ is a path of a split digraph $D=(V_{1},V_{2};A)$ with both
end-vertices in $V_{2}$. Splitting off the path $P$ means that we split off
the pairs $(t^{-}t,tt^{+})$ for every vertex $t\in V(P)\cap V_{1}$, where
$t^{-}$ and $t^{+}$ are the predecessor and successor of $t$ on the path $P$,
respectively.

###### Lemma 2.4

Let $D$ be a directed multigraph and let $X$ be a subset of $V(D)$ such that
every vertex of $D-X$ has both two in-neighbors and two out-neighbors in $X$.
If $X$ has a strong arc decomposition then $D$ has a strong arc decomposition.

Proof. Let $(A_{1},A_{2})$ be a strong arc decomposition of $X$. By
assumption, every vertex $x\in D-X$ has two out-neighbors
$x_{1}^{+},x_{2}^{+}$ and two in-neighbors $x_{1}^{-},x_{2}^{-}$ in $X$. Then
$A_{i}\cup\\{x_{i}^{-}x,xx_{i}^{+}:x\in D-X\\}$, $i\in[2]$ is a strong arc
decomposition of $D$. $\square$

###### Lemma 2.5

Let $D=(V_{1},V_{2};A)$ be a split digraph such that every vertex of $V_{1}$
has out- and in-degree at least 3 in $D$. Let $D^{\ast}$ be a directed
multigraph obtained from $D$ by splitting off at most two pairs at every
vertex in $V_{1}$. If $D^{\ast}\left\langle V_{2}\right\rangle$ has a strong
arc decomposition, then there is a strong arc decomposition of $D$.

Proof. Let $A_{1}$ and $A_{2}$ be a strong arc decomposition of
$D^{\ast}\left\langle V_{2}\right\rangle$. Lifting every splitting arc
$s_{1}s_{2}$, that is, replacing $s_{1}s_{2}$ with the two arcs
$s_{1}t,ts_{2}$ in its corresponding splitting pair, we obtain two disjoint
arc sets $A_{1}^{\prime},A_{2}^{\prime}$ of $A(D)$, see Figure 3.

Let $D_{i}$ $(i\in[2])$ be the digraph induced by $A_{i}^{\prime}$. Clearly,
each $D_{i}$ is strong and it covers all vertices of $V_{2}$. Then every
vertex of $V_{1}$ has at least 3 out- and in-neighbors in $V(D_{i})$ for all
$i\in[2]$. Recall that $D^{\ast}$ is obtained from $D$ by splitting off at
most two pairs of every vertex in $V_{1}$. This implies that for each
$i\in[2]$ and each vertex $t\in V(D_{i})-V(D_{3-i})$, $t$ has at least one
pair of in- and out-arcs which are not in $D_{i}$. Adding such in- and out-
arcs of $t$ in $A(D)-A(D_{i})$ to $A(D_{3-i})$, we obtain a strong arc
decomposition of $D\left\langle V(D_{1}\cup D_{2})\right\rangle$ and the claim
follows by Lemma 2.4. $\square$

$V_{2}$$V_{1}$$s_{1}$$s_{4}$$t$$t^{\prime}$ (a)

$V_{2}$$V_{1}$$s_{1}$$s_{4}$$t$$t^{\prime}$ (b)

$V_{2}$$V_{1}$$s_{1}$$s_{4}$$t$$t^{\prime}$ (c)

Figure 3: The split digraph $D=(V_{1},V_{2};A)$ with
$V_{1}=\\{t,t^{\prime}\\}$ and $V_{2}=\\{s_{1},s_{2},s_{3},s_{4}\\}$ such that
there is a 2-cycle between every vertex in $V_{1}$ and every vertex in
$\\{s_{1},s_{2},s_{3}\\}$, see (a). The vertices of $V_{2}$ in (a)-(c) are
labeled from top to bottom. We split off $(s_{1}t,ts_{2})$ and
$(s_{2}t,ts_{3})$ at $t$ to obtain $D^{\ast}$ and then $D^{\ast}\left\langle
V_{2}\right\rangle=D\left\langle
V_{2}\right\rangle\cup\\{s_{1}s_{2},s_{2}s_{3}\\}$, see (b). Note that the
dashed arc set $A_{1}$ and bold arc set $A_{2}$ form a strong arc
decomposition of $D^{\ast}\left\langle V_{2}\right\rangle$. Lifting the arcs
$s_{1}s_{2},s_{2}s_{3}$ to get $A_{1}^{\prime},A_{2}^{\prime}$ and adding a
pair of arcs $s_{3}t,ts_{1}$ to $A_{2}^{\prime}$, we obtain a strong arc
decomposition of $D\left\langle V_{2}\cup\\{t\\}\right\rangle$, which is shown
by dashed and bold arcs in (c). It should be noted that $t^{\prime}$ is not
covered by $A_{1}^{\prime}\cup A_{2}^{\prime}$, so by Lemma 2.4, we do not
need to consider it.

The next lemma covers the cases where the semicomplete part of the split
digraph has size at most 3 or it is one of the exceptions in Theorem 2.3

###### Lemma 2.6

Let $D=(V_{1},V_{2};A)$ be a split digraph such that every vertex of $V_{1}$
has out- and in-degree at least 3 in $D$. Then $D$ has a strong arc
decomposition if one of the following statements holds.

(i) $D$ is 2-arc-strong and $|V_{2}|\leq 3$.

(ii) $D\left\langle V_{2}\right\rangle$ is isomorphic to one of the digraphs
shown in Figure 2.

Proof. Let $t$ be an arbitrary vertex of $V_{1}$. Observe that $|V_{2}|\geq 3$
as $t$ has in- and out-degree at least three in $D$. Further, if $|V_{2}|=3$,
then there is a 2-cycle between $t$ and each vertex of $V_{2}$.

First we consider the case $|V_{2}|=3$. If $D\left\langle V_{2}\right\rangle$
contains a 3-cycle, say $s_{1}s_{2}s_{3}s_{1}$, then the arcs of
$ts_{1}s_{2}s_{3}t$ and $ts_{3}s_{1}t\cup ts_{2}t$ form a strong arc
decomposition of $D\left\langle V_{2}\cup\\{t\\}\right\rangle$ and now the
claim follows by Lemma 2.4. So we may assume that $D\left\langle
V_{2}\right\rangle$ contains no 3-cycle. Then there is a vertex of $V_{2}$
which has in-degree or out-degree zero in $D\left\langle V_{2}\right\rangle$.
Since $D$ is 2-arc-strong, $V_{1}$ has size at least two. Let $t^{\prime}$ be
a vertex of $V_{1}-\\{t\\}$ and let $s_{1}s_{2}s_{3}$ be a hamiltonian path of
$D\left\langle V_{2}\right\rangle$. Then the arcs of
$ts_{1}s_{2}t^{\prime}s_{3}t$ and $ts_{2}s_{3}t^{\prime}s_{1}t$ form a strong
arc decomposition of $D\left\langle V_{2}\cup\\{t,t^{\prime}\\}\right\rangle$.
Thus the claim follows by Lemma 2.4 again.

To prove (ii) it suffices to show the case $D\left\langle
V_{2}\right\rangle=S_{4}$ as each digraph in Figure 2 contains $S_{4}$ has a
spanning subdigraph. Since $t$ has in- and out-degree at least three in $D$,
the vertex $t$ has an in-neighbor and an out-neighbor in $\\{v_{1},v_{3}\\}$
(resp., in $\\{v_{2},v_{4}\\}$). Let $A_{1}$ be the union of the four arcs
between $t$ and such neighbors and arcs in
$\\{v_{1}v_{3},v_{3}v_{1},v_{2}v_{4},v_{4}v_{2}\\}$. As $t$ has in- and out-
degree at least 3, there exist $t^{-},t^{+}\in V_{2}$ such that
$t^{-}t,tt^{+}$ is a pair of in- and out-arcs of $t$ in $A(D)-A_{1}$. Let
$A_{2}=\\{t^{-}t,tt^{+},v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{4}v_{1}\\}$. Then
$A_{1}$ and $A_{2}$ form a strong arc decomposition of $D\left\langle
V_{2}\cup\\{t\\}\right\rangle$ and now the claim follows by Lemma 2.4.
$\square$

###### Lemma 2.7

Let $D=(V_{1},V_{2};A)$ be a split digraph such that every vertex of $V_{1}$
has out- and in-degree at least 3 in $D$. Let $D^{\ast}$ be any directed
multigraph obtained from $D$ by splitting off some pairs at every vertex in
$V_{1}$. If $D^{\ast}\left\langle V_{2}\right\rangle$ is isomorphic to one of
the digraphs in Figure 2, then $D$ has a strong arc decomposition.

Proof. Since $D\left\langle V_{2}\right\rangle$ is a semicomplete digraph, it
contains at least one arc between every pair of distinct vertices of $V_{2}$.
So we may assume that the arcs in
$A_{1}=\\{v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{4}v_{1}\\}$ are original arcs,
in other words, they belong to $D\left\langle V_{2}\right\rangle$. By Lemma
2.6 (ii), we may further assume that $D^{\ast}\left\langle V_{2}\right\rangle$
contains at least one splitting arc. Observe that as $D\left\langle
V_{2}\right\rangle$ has no parallel arcs, at least one arc from each pair of
parallel arcs must be a splitting arc in $D^{\ast}\left\langle
V_{2}\right\rangle$. So the arc from $v_{1}$ to $v_{2}$ in $A(S_{4,2})-A_{1}$
is a splitting arc.

Suppose first that there is no splitting arc of $D^{\ast}\left\langle
V_{2}\right\rangle$ with both end-vertices in $\\{v_{1},v_{3}\\}$ or in
$\\{v_{2},v_{4}\\}$. Then $D^{\ast}\left\langle V_{2}\right\rangle$ is
isomorphic to the digraph $S_{4,2}$ and the arc from $v_{1}$ to $v_{2}$ in
$A(S_{4,2})-A_{1}$ is the only splitting arc. Let $(v_{1}t,tv_{2})$ be its
corresponding splitting pair and let $t^{-}t,tt^{+}$ be two arcs in $D$ with
$t^{-}\in\\{v_{2},v_{4}\\}$ and $t^{+}\in\\{v_{1},v_{3}\\}$. The arcs $t^{-}t$
and $tt^{+}$ exist as $t$ has out-degree and in-degree at least three in $D$.
Moreover, there exists a pair of in- and out-arcs $e^{-},e^{+}$ of $t$ in $D$
which are distinct from the arcs in $\\{v_{1}t,tv_{2},t^{-}t,tt^{+}\\}$. Then
$\\{e^{+},e^{-}\\}\cup A_{1}$ and
$\\{v_{1}t,tv_{2},t^{-}t,tt^{+},v_{1}v_{3},v_{3}v_{1},v_{2}v_{4},v_{4}v_{2}\\}$
is a strong arc decomposition of $D\left\langle V_{2}\cup\\{t\\}\right\rangle$
and the claim follows by Lemma 2.4.

If there is a splitting arc of $D^{\ast}\left\langle V_{2}\right\rangle$ with
both end-vertices in $\\{v_{1},v_{3}\\}$ (resp., in $\\{v_{2},v_{4}\\}$), then
let $ab$ with $\\{a,b\\}=\\{v_{1},v_{3}\\}$ (resp., $cd$ with
$\\{c,d\\}=\\{v_{2},v_{4}\\}$) be such an arc. We may further assume that
$(at_{1},t_{1}b)$ and $(ct_{2},t_{2}d)$ are the corresponding splitting pairs
of $ab$ and $cd$, respectively, if $ab$ or $cd$ exists. Clearly, $C_{1}=aba$
or $C_{1}=at_{1}ba$ (resp., $C_{2}=cdc$ or $C_{2}=ct_{2}dc$) is a cycle of the
original split digraph $D$. Observe that $C_{1}$ and $C_{2}$ are vertex
disjoint or they share exactly one common vertex. For the case that $C_{1}$
and $C_{2}$ share one vertex, both $ab$ and $cd$ exist and $t_{1}=t_{2}$. Let
$t_{1}^{-}t_{1},t_{1}t_{1}^{+}$ be a pair of arcs in $A(D)-A(C_{1}\cup
C_{2})$. Then $A_{1}\cup\\{t_{1}^{-}t_{1},t_{1}t_{1}^{+}\\}$ and $A(C_{1}\cup
C_{2})$ is a strong arc decomposition of $D\left\langle
V_{2}\cup\\{t_{1}\\}\right\rangle$ and the claim follows by Lemma 2.4.

It remains to consider the case where $C_{1}$ and $C_{2}$ are vertex disjoint.
If $ab$ exits, let $t_{1}^{-}t_{1},t_{1}t_{1}^{+}$ be two arcs with
$t_{1}^{-},t_{1}^{+}$ in $\\{v_{2},v_{4}\\}$ and, if $cd$ exits, let
$t_{2}^{-}t_{2},t_{2}t_{2}^{+}$ be two arcs with $t_{2}^{-},t_{2}^{+}$ in
$\\{v_{1},v_{3}\\}$. The arcs $t_{i}^{-}t_{i},t_{i}t_{i}^{+}$ $i\in[2]$ exist
as every vertex of $V_{1}$ has out- and in-degree at least three. Since one of
$ab$ and $cd$ is a splitting arc, one of $t_{1}$ and $t_{2}$, say $t_{j}$,
exists. Let $A_{2}=A(C_{1}\cup C_{2})\cup\\{t_{j}^{-}t_{j},t_{j}t_{j}^{+}\\}$
and let $e^{+},e^{-}$ be an out- and in-arc of $t_{j}$ in $A(D)-A_{2}$. Then
$A_{1}\cup\\{e^{+},e^{-}\\}$ (or
$A_{1}\cup\\{e^{+},e^{-},t_{3-j}^{-}t_{3-j},t_{3-j}t_{3-j}^{+}\\}$ if
$t_{3-j}$ exists) and $A_{2}$ is a strong arc decomposition of $D\left\langle
V_{2}\cup\\{t_{1}\\}\cup\\{t_{2}\\}\right\rangle$. By Lemma 2.4, $D$ has a
strong arc decomposition. $\square$

Combining Theorem 2.3 and Lemmas 2.5, 2.7, we obtain the following result
which indicates that what we seek is a number of arc-disjoint paths such that
when we split off these, the semicomplete part of the resulting directed
multigraph is 2-arc-strong.

###### Corollary 2

Let $D=(V_{1},V_{2};A)$ be a split digraph such that every vertex of $V_{1}$
has out- and in-degree at least 3 in $D$. Let $D^{\ast}$ be a directed
multigraph obtained from $D$ by splitting off at most two pairs of every
vertex in $V_{1}$. If $D^{\ast}\left\langle V_{2}\right\rangle$ is 2-arc-
strong, then $D$ has a strong arc decomposition.

##  3 The proof of Theorem 1.6

For convenience we repeat the statement of the theorem.

Theorem 1.6 Let $D=(V_{1},V_{2};A)$ be a 2-arc-strong split digraph such that
$V_{1}$ is an independent set and the subdigraph induced by $V_{2}$ is
semicomplete. If every vertex of $V_{1}$ has both out- and in-degree at least
3 in $D$, then $D$ has a strong arc decomposition.

We first have the following simple observations, which the first follows
immediately by considering whether the vertex $x$ belongs to $S_{k}$ or not,
and the second one can be checked easily as $xy$ must be a backward arc of
$S$.

###### Observation 3.1

Suppose that $xy$ is the only out-arc of some vertex $x$ in $D\left\langle
V_{2}\right\rangle$. Then one of the following holds.

(i) $V_{S_{k-1}}=\\{x\\}$ and $V(S_{k})=\\{y\\}$.

(ii) $x,y\in V(S_{k})$ and $xy$ is a cut-arc of $S_{k}$.

Recall that the backward arcs of a nice decomposition are exactly the cut-
arcs.

###### Observation 3.2

Let $S$ be a strong semicomplete digraph with $|V(S)|\geq 4$ and let
$(U_{1},\ldots,U_{l})$ be the nice decomposition of $S$ and
$(x_{1}y_{1},\ldots,x_{r}y_{r})$ the natural ordering of its backward arcs. If
$xy\in A(S)$ is the only out-arc of $x$ in $S$, then one of the following
holds.

(i) $U_{l}=\\{x\\}=\\{x_{1}\\}$ and $y=y_{1}$.

(ii) $U_{l}=\\{x_{1}\\}$, $U_{l-1}=\\{x_{2}\\}=\\{y_{1}\\}=\\{x\\}$ and
$y=y_{2}$.

By Lemma 2.6 (i), we may assume that $|V_{2}|\geq 4$ and by Corollary 2, we
may assume that $D\left\langle V_{2}\right\rangle$ is not 2-arc-strong. Let
$S_{1},\ldots,S_{k}$ $(k\geq 1)$ be the acyclic ordering of the strong
components of $D\left\langle V_{2}\right\rangle$. If $|V(S_{k})|\geq 4$, then
by Theorem 2.1, $V(S_{k})$ has a nice decomposition. Let
$(U_{1},\ldots,U_{l})$ be its nice decomposition and let
$(x_{1}y_{1},\ldots,x_{r}y_{r})$ be the natural ordering of its backward arcs.
Similarly, suppose that $(W_{1},\ldots,W_{p})$ is the nice decomposition of
$V(S_{1})$ when $|V(S_{1})|\geq 4$.

Let the subsets $X,Y$ of $V_{2}$ be defined as follows. Note that $X\neq Y$
since $D\left\langle V_{2}\right\rangle$ is either non-strong or it is strong
and has at least one cut-arc.

$X=\begin{cases}U_{l},&\mbox{if }|V(S_{k})|\geq 4;\\\
V(S_{k}),&\mbox{otherwise}.\end{cases}\mbox{ \;\;and
\;\;}Y=\begin{cases}W_{1},&\mbox{if }|V(S_{1})|\geq 4;\\\
V(S_{1}),&\mbox{otherwise}.\end{cases}$

###### Lemma 3.3

For each $(X,Y)$-path $P$ in $D$, the directed multigraph $D_{P}\left\langle
V_{2}\right\rangle$ obtained from $D\left\langle V_{2}\right\rangle$ by
splitting off $P$ is strong.

Proof. Observe that $D_{P}\left\langle V_{2}\right\rangle$ can be obtained
from $D\left\langle V_{2}\right\rangle$ by adding some splitting arcs. So we
may assume that $D\left\langle V_{2}\right\rangle$ is non-strong since
otherwise there is nothing to prove.

Suppose that $P$ starts from $a$ and ends at $b$. Clearly, $a\in X\subseteq
V(S_{k})$ and $b\in Y\subseteq V(S_{1})$. Further, for any vertex $x\in
V_{2}$, it can reach $a$ by the arc $xa$ if $x\notin V(S_{k})$ or an
$(x,a)$-path in $S_{k}$, similarly, any vertex $y\in V_{2}$ can reached from
$b$. Then there exists an $(x,y)$-path consisting of such $(x,a)$-,
$(b,y)$-paths and the path $P^{\prime}$, where $P^{\prime}$ is the path in
$D_{P}\left\langle V_{2}\right\rangle$ which is obtained by splitting off $P$.
In other words, for any vertices $x,y$, there is an $(x,y)$-path in
$D_{P}\left\langle V_{2}\right\rangle$ and thus $D_{P}\left\langle
V_{2}\right\rangle$ is strong. $\square$

Suppose that $\mathcal{Q}=(Q_{1},\ldots,Q_{\alpha})$ ($\alpha\geq 2$) is an
ordering of arc-disjoint paths such that $Q_{1}$ and $Q_{2}$ are $(X,Y)$-paths
and $Q_{i}=u_{i}t_{i}v_{i}$ ($i\geq 3$) with $t_{i}\in V_{1}$. For
convenience, we also regard $\mathcal{Q}$ as a set of those paths. The set
$\mathcal{Q}$ is called $\gamma$-feasible if every vertex of $V_{1}$ belongs
to at most $\gamma$ paths of $\mathcal{Q}$. Splitting off $\mathcal{Q}$ means
that split off all paths in $\mathcal{Q}$. We often use the symbol
$D_{\mathcal{Q}}$ to denote the directed multigraph obtained from $D$ by
splitting off all paths in $\mathcal{Q}$.

$V_{2}$$V_{1}$$v_{1}$$v_{5}$$u$$v$$w$ Figure 4: An illustration of the
splitting off operation on a 2-feasible set $\mathcal{Q}$. $D\left\langle
V_{2}\right\rangle$ is a transitive tournament of order 5 with vertices
$v_{1},\ldots,v_{5}$ and all arcs from top to bottom. So
$X=V(S_{k})=\\{v_{5}\\}$ and $Y=\\{v_{1}\\}$. The 2-feasible set $\mathcal{Q}$
consists of three paths $Q_{1},Q_{2}$ and $Q_{3}$, where
$Q_{1}=v_{5}wv_{2}v_{3}uv_{1}$, $Q_{2}=v_{5}vv_{1}$ and $Q_{3}=v_{4}wv_{3}$.
The dashed arcs are the splitting arcs obtained by splitting off
$\mathcal{Q}$. Note that $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$ can
be constructed from $D\left\langle V_{2}\right\rangle$ by adding all dashed
arcs.

It follows by Lemma 3.3 that every vertex of $V_{2}$ has both out- and in-
degree at least one in $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$. Let
$W_{\mathcal{Q}}^{+}\subseteq V_{2}$ (resp., $W_{\mathcal{Q}}^{-}\subseteq
V_{2}$) denote the set of vertices with out- (resp., in-)degree exactly one in
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$. Next we show that if
$W_{\mathcal{Q}}^{+}=W_{\mathcal{Q}}^{-}=\emptyset$, then either
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$ is 2-arc-strong or it
contains at most two cut-arcs.

###### Lemma 3.4

Let $Q=(Q_{1},\ldots,Q_{\alpha})$ ($\alpha\geq 2$) be a $\gamma$-feasible set.
Suppose that $W_{\mathcal{Q}}^{+}=W_{\mathcal{Q}}^{-}=\emptyset$. If
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$ is not 2-arc-strong, then
every cut-arc $xy$ of $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$
satisfies one of the following statements.

(i) $xy\in{A(S_{k})}$, $|V(S_{k})|=3$ and the two $(X,Y)$-paths $Q_{1},Q_{2}$
in $\mathcal{Q}$ are starting from the vertex $y$;

(ii) $xy\in{A(S_{1})}$, $|V(S_{1})|=3$ and the two $(X,Y)$-paths $Q_{1},Q_{2}$
in $\mathcal{Q}$ are ending at the the vertex $x$;

Moreover, there exists a $\gamma$-feasible set $\mathcal{Q^{\prime}}$ such
that $D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$ is 2-arc-
strong.

Proof. By Lemma 3.3, we may assume that $D_{\mathcal{Q}}\left\langle
V_{2}\right\rangle$ is 1-arc-strong with a cut-arc $xy$. First we claim that
$xy$ is an original arc of $D\left\langle V_{2}\right\rangle$. Suppose not,
say $xy$ is a splitting arc of $D_{\mathcal{Q}}\left\langle
V_{2}\right\rangle$ and it is obtained by splitting off the path
$Q_{i}\in\mathcal{Q}$. By the fact that $\mathcal{Q}-Q_{i}$ has an
$(X,Y)$-path and Lemma 3.3 again, the directed multigraph
$D_{\mathcal{Q}-Q_{i}}\left\langle V_{2}\right\rangle$ obtained from
$D\left\langle V_{2}\right\rangle$ by splitting off all paths in
$\mathcal{Q}-Q_{i}$ is also strong. This contradicts the fact that $xy$ is a
cut-arc of $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$ as
$A(D_{\mathcal{Q}-Q_{i}}\left\langle V_{2}\right\rangle)\subseteq
A(D_{\mathcal{Q}}\left\langle V_{2}\right\rangle-xy)$.

Note that at most one of the paths $Q_{1},Q_{2}$ contains the arc $xy$ so
suppose w.l.o.g that $Q_{1}$ avoids $xy$. Let $P$ be an arbitrary $(X,Y)$-path
in $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle-xy$. Such a path exists as
it can be obtained by splitting off the $(X,Y)$-path $Q_{1}$ in $D$. Suppose
that $P$ starts from $a$ and ends at $b$. Clearly $a\in X\subseteq V(S_{k})$
and $b\in Y\subseteq V(S_{1})$.

As $xy$ is a cut-arc of $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$,
there is no $(x,a)$-path or no $(b,y)$-path in $D_{\mathcal{Q}}\left\langle
V_{2}\right\rangle-xy$, consequently, the same holds in $D\left\langle
V_{2}\right\rangle-xy$. W.l.o.g we may assume that $D\left\langle
V_{2}\right\rangle-xy$ contains no $(x,a)$-path. Suppose first that $x\notin
V(S_{k})$. Then $x$ dominates $a$. So we have $V(S_{k})=\\{a\\}=\\{y\\}$ and
$V(S_{k-1})=\\{x\\}$. Since there is no $(x,a)$-path in
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle-xy$, $xy$ is also the only
out-arc of $x$ in $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$, which
implies that $x\in W_{\mathcal{Q}}^{+}$ and this contradicts our assumption.
Therefore, we may assume that $x\in V(S_{k})$. Then $y\in V(S_{k})$ as $xy\in
A(D\left\langle V_{2}\right\rangle)$. Moreover, there is no $(x,a)$-path in
$S_{k}-xy$, which means that $xy$ is also a cut-arc of $S_{k}$.

If $|V(S_{k})|\geq 4$, then $a\in U_{l}$ and $xy=x_{i}y_{i}$ for some
$i\in[r]$. Since there is no $(x_{i},a)$-path in $S_{k}-x_{i}y_{i}$, we have
$x_{i}\neq x_{1}$ and $x_{i}$ does not dominate $a$. Note that there is only
one arc, i.e., $x_{1}y_{1}$, leaving the set $U_{l}$ in $D\left\langle
V_{2}\right\rangle$ and every vertex in $U_{1}\cup\cdots\cup U_{l-1}$ except
$y_{1}$ dominates all vertices of $U_{l}$. So $a=x_{1},x=x_{i}=y_{1}$ and
$x_{i}y_{i}$ is the only out-arc of $x$ in $D\left\langle V_{2}\right\rangle$.
This means that $U_{l}=\\{x_{1}\\}=\\{a\\}$, $U_{l-1}=\\{x\\}$ and
$xy=x_{2}y_{2}$ by Proposition 2.2 (ii). Moreover, since $x$ can not reach $a$
in $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle-xy$, the arc $xy$ is also
the only out-arc of $x$ in $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$.
Then $x\in W_{\mathcal{Q}}^{+}$, which contradicts our assumption.

For the case $|V(S_{k})|=2$, we have $S_{k}=xyx$ and $y=a$. Moreover, the arc
$xy$ is also the only out-arc of $x$ in $D_{\mathcal{Q}}\left\langle
V_{2}\right\rangle$ and then $x\in W_{\mathcal{Q}}^{+}$, a contradiction
again.

So it suffices to consider the case $|V(S_{k})|=3$. As $S_{k}$ is strong and
$xy$ is a cut-arc, we may assume that $xyzx$ is a 3-cycle in $S_{k}$. Recall
that there is no $(x,a)$-path in $S_{k}-xy$ and in
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle-xy$. Clearly $x\neq a$.
Further, $x$ can not reach any vertex $u$ of $V_{2}-V(S_{k})$ in
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle-xy$ as $u$ dominates $a$.
Since $x\notin W_{\mathcal{Q}}^{+}$, either $xz\in A(S_{k})$ or there exists a
path $Q_{i}\in\mathcal{Q}$ with $i\geq 3$ such that $Q_{i}=xtz$. In both
cases, $x$ can reach $z$ in $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle-
xy$, which implies that $z\neq a$ and then $y=a$. In the same way, $z$ can not
reach $a$ and can not reach any vertex of $V_{2}-V(S_{k})$ in
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle-xy$. As $z\notin
W_{\mathcal{Q}}^{+}$, there exists a path $Q_{j}\in\mathcal{Q}$ with $i\neq j$
and $i\geq 3$ such that $Q_{j}=zt^{\prime}x$, see Figure 5 (a). Since $a$ is
the first vertex of an arbitrary $(X,Y)$-path in $D_{\mathcal{Q}}\left\langle
V_{2}\right\rangle-xy$ and $xy\in A(S_{k})$, we have that both $Q_{1}$ and
$Q_{2}$ are starting from $a=y$, which implies (i). By symmetry, if there is
no $(b,y)$-path in $D\left\langle V_{2}\right\rangle-xy$, then (ii) holds.

Next we show that there exists a $\gamma$-feasible set $\mathcal{Q^{\prime}}$
such that $D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$ is 2-arc-
strong. Since $t^{\prime}$ has out-degree at least 3, it has an out-neighbor
$w$ in $V_{2}-\\{x,z\\}$. Let
$\mathcal{Q^{\prime}}=(\mathcal{Q}-zt^{\prime}x)\cup\\{zt^{\prime}w\\}$. It
can be checked easily that $\mathcal{Q^{\prime}}$ is also a $\gamma$-feasible
set and every vertex of $V_{2}$ has the same out-degree (resp., every vertex
of $V_{2}-x$ has the same in-degree) in $D_{\mathcal{Q^{\prime}}}\left\langle
V_{2}\right\rangle$ and in $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$.
Furthermore, $d_{D_{\mathcal{Q^{\prime}}}\left\langle
V_{2}\right\rangle}^{-}(x)\geq d_{D\left\langle V_{2}\right\rangle}^{-}(x)\geq
2$ as $|V_{2}|\geq 4$. Thus
$W_{\mathcal{Q^{\prime}}}^{+}=W_{\mathcal{Q^{\prime}}}^{-}=\emptyset$.
Moreover, for each arc $uv\in V(S_{k})$, there is a $(u,v)$-path in
$D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle-uv$. In other words,
no arc of $S_{k}$ is a cut-arc of $D_{\mathcal{Q^{\prime}}}\left\langle
V_{2}\right\rangle$. Similarly, we can adjust $Q^{\prime}$ a little bit to
obtain a new $\gamma$-feasible set, still call it $Q^{\prime}$, such that
$W_{\mathcal{Q^{\prime}}}^{+}=W_{\mathcal{Q^{\prime}}}^{-}=\emptyset$ and no
arc of $S_{1}$ and $S_{k}$ is a cut-arc of
$D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$. Then statements (i)
and (ii) show that $D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$
is 2-arc-strong and this completes the proof. $\square$

$V_{2}$$V_{1}$$b$$y$$x$$z$$t^{\prime}$$v$$u$ (a) $D$

$b$$y$$x$$z$ (b) $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$

$b$$y$$x$$z$ (c) $D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$

Figure 5: An illustration of a 2-feasible set
$\mathcal{Q}=(Q_{1},Q_{2},Q_{3})$ such that $W_{\mathcal{Q}}^{+}=\emptyset$,
see (a), where $Q_{1}=yvb,Q_{2}=yub$ and $Q_{3}=zt^{\prime}x$. For readability
we have only shown the relevant arcs of $D$. The directed multigraph in (b) is
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$. It can be checked easily
that the arc $xy$ is a cut-arc of $D_{\mathcal{Q}}\left\langle
V_{2}\right\rangle$. The set
$\mathcal{Q^{\prime}}=(Q_{1},Q_{2},Q_{3}^{\prime})$ with
$Q_{3}^{\prime}=zt^{\prime}y$ is also 2-feasible and the directed multigraph
$D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$ in (c) is 2-arc-
strong.

Now observe that there exists a $2$-feasible set $\mathcal{Q}$ in $D$. In
fact, every set of two arc-disjoint $(X,Y)$-paths in $D$ clearly is a
$2$-feasible set. Such a pair of paths exist as $D$ is 2-arc-strong. We may
assume that for every 2-feasible set $\mathcal{Q}$,
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$ is not 2-arc-strong since
otherwise $D$ has a strong arc decomposition by Corollary 2 with
$D^{\ast}=D_{\mathcal{Q}}$. By the last line of the statement of Lemma 3.4,
either $W_{\mathcal{Q}}^{+}\neq\emptyset$ or
$W_{\mathcal{Q}}^{-}\neq\emptyset$ for each 2-feasible set $\mathcal{Q}$.

$\mbox{We choose a 2-feasible set
}\mathcal{Q}=(Q_{1},\ldots,Q_{\alpha})(\alpha\geq 2)\mbox{ such that
}|W_{\mathcal{Q}}^{+}|+|W_{\mathcal{Q}}^{-}|\mbox{ is minimum. }$ ($C1$)

Recall that $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$ is obtained from
$D\left\langle V_{2}\right\rangle$ by adding splitting arcs. So
$d_{D_{\mathcal{Q}}\left\langle V_{2}\right\rangle}^{+}(x)\geq
d_{D\left\langle V_{2}\right\rangle}^{+}(x)$ and then every vertex of
$W_{\mathcal{Q}}^{+}$ has out-degree at most one in $D\left\langle
V_{2}\right\rangle$. Moreover, we have the following.

###### Lemma 3.5

Let $x$ be a vertex of $W_{\mathcal{Q}}^{+}$. Suppose that $x$ has out-degree
exactly one in $D\left\langle V_{2}\right\rangle$. Then

(i) $A(\mathcal{Q})$ contains no arc from $x$ to $V_{1}$;

(ii) each out-neighbor $t$ of $x$ in $V_{1}$ belongs to two paths in
$\mathcal{Q}$;

(iii) if $t$ is an out-neighbor of $x$ in $V_{1}$ and $Q_{i}=wtz$ with
$i\notin[2]$, then $w$ has out-degree at most two in
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$. In particular, $w$ has out-
degree at most one in $D\left\langle V_{2}\right\rangle$.

Proof. First we claim that $A(\mathcal{Q})$ contains no arcs from $x$ to
$V_{1}$. If not, say $xty$ is a subpath of some path $Q_{j}\in\mathcal{Q}$.
Then $xy$ is a new out-arc of $x$ in $D_{\mathcal{Q}}\left\langle
V_{2}\right\rangle$ and thus $d_{D_{\mathcal{Q}}\left\langle
V_{2}\right\rangle}^{+}(x)>d_{D\left\langle V_{2}\right\rangle}^{+}(x)=1$.
This contradicts the definition of set $W_{\mathcal{Q}}^{+}$ and so the claim
holds.

Let $t$ be any out-neighbor of $x$ in $V_{1}$. Clearly $xt\notin
A(\mathcal{Q})$ by (i). As $\mathcal{Q}$ is $2$-feasible, $t$ belongs to at
most two paths in $\mathcal{Q}$. Suppose to the contrary that $t$ belongs to
at most one path in $\mathcal{Q}$. Since $t$ has out-degree at least three,
there is an out-arc $ty$ of $t$ in $D-x$ with $ty\notin A(\mathcal{Q})$. Then
$\mathcal{Q}\cup\\{xty\\}$ is a $2$-feasible set $\mathcal{Q}^{\prime}$.
Further, $x\notin W_{\mathcal{Q^{\prime}}}^{+}$ as $x$ has one more out-arc,
i.e., $xy$, in $D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$,
which contradicts (C1). This proves (ii).

Suppose that $Q_{i}=wtz$ with $i\notin[2]$ such that $t$ is an out-neighbor of
$x$ in $V_{1}$ and $w$ has out-degree at least three in
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$. By (ii), $t$ belongs to only
one path in $\mathcal{Q}-Q_{i}$. Since $t$ has out-degree at least three,
there exists an out-neighbor $t^{+}$ of $t$ such that $t^{+}\neq x$ and
$tt^{+}\notin A(\mathcal{Q}-Q_{i})$. In particular, let $t^{+}=z$ when $z\neq
x$. Let $\mathcal{Q^{\prime}}=(\mathcal{Q}-wtz)\cup\\{xtt^{+}\\}$. Then
$\mathcal{Q^{\prime}}$ is $2$-feasible and both $w$ and $x$ have out-degree at
least two in $D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$. It
should be mentioned that when $x=z$, although $x$ is loosing one in-neighbor,
$x\notin W_{\mathcal{Q}}^{-}$ as $d_{D\left\langle
V_{2}\right\rangle}^{-}(x)\geq|V_{2}|-1\geq 3$. This contradicts (C1) again as
$|W_{\mathcal{Q^{\prime}}}^{+}|<|W_{\mathcal{Q}}^{+}|$ and
$|W_{\mathcal{Q^{\prime}}}^{-}|=|W_{\mathcal{Q}}^{-}|$. So $w$ has at most two
out-arcs in $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$ and then it has
out-degree at most one in $D\left\langle V_{2}\right\rangle$ as $wz$ is a
splitting arc of $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$. $\square$

Next we show that the minimum out-degree of $D_{\mathcal{Q}}\left\langle
V_{2}\right\rangle$ is at least two except for one case in which we have
complete knowledge of the structure of the terminal component of
$D\left\langle V_{2}\right\rangle$.

###### Lemma 3.6

If $W_{\mathcal{Q}}^{+}$ is not empty for each 2-feasible set $\mathcal{Q}$,
then $S_{k}$ is a 3-cycle and each vertex of $S_{k}$ has exactly one out-
neighbor in $V_{1}$. Furthermore, they all have the same out-neighbor in
$V_{1}$.

Proof. Fix an arbitrary vertex $x\in W_{\mathcal{Q}}^{+}$. If $|X|=1$, then
the vertex of $X$ clearly has out-degree at least two in
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$ as $Q_{1},Q_{2}$ are two arc-
disjoint paths starting from $X$. So we may assume that $X\neq\\{x\\}$. Then
$x$ has out-degree at least one in $D\left\langle V_{2}\right\rangle$ since
otherwise we would have $\\{x\\}=V(S_{k})=X$. On the other hand, since every
vertex of $W_{\mathcal{Q}}^{+}$ has out-degree at most one in $D\left\langle
V_{2}\right\rangle$, we obtain that $x$ has only one out-arc, say $xy$, in
$D\left\langle V_{2}\right\rangle$.

Fix an arbitrary out-neighbor $t$ of $x$ in $V_{1}$. Such a neighbor exists as
$D$ is 2-arc-strong. Moreover, $xt\notin A(\mathcal{Q})$ as $A(\mathcal{Q})$
contains no arc from $x$ to $V_{1}$ by Lemma 3.5 (i). Next we divide the proof
into the following three cases.

###### Case 1

$|V(S_{k})|\leq 2$.

In this case, we have $X=V(S_{k})$ and either
$V(S_{k-1})=\\{x\\},V(S_{k})=\\{y\\}$ or $S_{k}=xyx$. In both cases it follows
from the definition of $Q_{1}$ and $Q_{2}$ that arc $xy$ is not in $Q_{1}\cup
Q_{2}$. Since $A(\mathcal{Q})$ contains no arc from $x$ to $V_{1}$, the paths
$Q_{1},Q_{2}$ are two arc-disjoint $(\\{y\\},Y)$-paths.

Next we show that $t\in V(Q_{1})\cap V(Q_{2})$. Suppose that $t$ belongs to a
path $Q_{i}\in\mathcal{Q}$ with $i\notin[2]$, say $Q_{i}=wtz$. By Lemma 3.5
(iii), $w$ has out-degree at most one in $D\left\langle V_{2}\right\rangle$.
Observe that $x,y$ are the only two vertices of $V_{2}$ with out-degree at
most one in $D\left\langle V_{2}\right\rangle$ as every other vertex dominates
both $x$ and $y$. Since $xt\notin A(\mathcal{Q})$, we have $w=y$. Then
$Q_{1},Q_{2}$ and $Q_{i}$ are all starting from $y$, which implies that $y$
has out-degree at least three in $D_{\mathcal{Q}}\left\langle
V_{2}\right\rangle$. This contradicts Lemma 3.5 (iii) and now it follows by
Lemma 3.5 (ii) that $t\in V(Q_{1})\cap V(Q_{2})$.

Since $Q_{1}$ and $Q_{2}$ are arc-disjoint $(\\{y\\},Y)$-paths, we may assume
that $t$ is not the second vertex of $Q_{1}$. Let $t^{-}$ be the predecessor
of $t$ on the path $Q_{1}$. Replacing the arc $t^{-}t$ with $t^{-}xt$ in
$\mathcal{Q}$ (see Figure 6 (b)), we obtain a new $2$-feasible set
$\mathcal{Q^{\prime}}$ containing $xt$. This means that the vertex $x$ gains
one more out-neighbor and thus $x\notin W_{\mathcal{Q^{\prime}}}^{+}$.
Moreover, although $t^{-}$ is loosing one out-neighbor after the replacement,
$t^{-}\notin W_{\mathcal{Q^{\prime}}}^{+}$ as it has at least two out-
neighbors $x,y$ in $V_{2}$, consequently, in
$D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$. Therefore,
$|W_{\mathcal{Q^{\prime}}}^{+}|<|W_{\mathcal{Q}}^{+}|=|\\{x\\}|$ and
$|W_{\mathcal{Q^{\prime}}}^{-}|=|W_{\mathcal{Q}}^{-}|$, which contradicts
(C1). It should be noted that $Q_{1}$ and $Q_{2}$ do not contain any arc from
$V_{1}$ to $x$, so they still are two paths after replacing the arc $t^{-}t$
with $t^{-}xt$.

$V_{2}$$V_{1}$$t^{-}$$x$$y$$u$$t$$w$ (a)

$V_{2}$$V_{1}$$t^{-}$$x$$y$$u$$t$$w$ (b)

Figure 6: An illustration of Case 1 in Lemma 3.6. All arcs in $D\left\langle
V_{2}\right\rangle$ not shown go from top to bottom. For readability we have
only shown the relevant arcs of $D$. The dashed and bold paths shown in (a)
and in (b) form a $2$-feasible set $\mathcal{Q}$ and $\mathcal{Q^{\prime}}$ of
$D$, respectively.

This concludes Case 1 and therefore, we may assume that $|V(S_{k})|\geq 3$.
Recall that $xy$ is the only out-arc of $x$ in $D\left\langle
V_{2}\right\rangle$. By Observation 3.1, we have $x,y\in V(S_{k})$ and $xy$ is
a cut-arc of $S_{k}$.

###### Case 2

$|V(S_{k})|\geq 4$.

Recall that by Theorem 2.1, $V(S_{k})$ has a nice decomposition
$(U_{1},\ldots,U_{l})$ with cut-arcs $\\{x_{i}y_{i}:i\in[r]\\}$. It follows by
Observation 3.2 and the fact that $U_{l}=X\neq\\{x\\}$ that
$xy=x_{2}y_{2},U_{l}=\\{x_{1}\\}$ and $U_{l-1}=\\{y_{1}\\}=\\{x_{2}\\}$. Hence
$Q_{1}$ and $Q_{2}$ are two arc-disjoint $(\\{x_{1}\\},Y)$-paths. Moreover, by
the same argument as in the second paragraph of Case 1 (replace $y$ by
$x_{1}$), we have that the vertex $t$, which we fixed above, belongs to both
$Q_{1}$ and $Q_{2}$.

$V_{2}$$V_{1}$$b$$v$$y$$x$$x_{1}$$a$$t$ (a)

$V_{2}$$V_{1}$$b$$v$$y$$x$$x_{1}$$a$$t$ (b)

Figure 7: An illustration of Case 2 in Lemma 3.6 with
$x=x_{2}=y_{1},y=y_{2}=u$. All arcs in $D\left\langle V_{2}\right\rangle$ not
shown are from top to bottom. For readability we have only shown the relevant
arcs of $D$. The dashed and bold paths $Q_{1},Q_{2}$ shown in (a) form a
$2$-feasible set $\mathcal{Q}$ of $D$. The two bold paths
$Q_{2}^{\prime}=x_{1}xtb$ and $Q_{3}=uav$ in (b) are obtained from $Q_{2}$.
Note that $Q_{2}^{\prime}$ is an $(X,Y)$-path and then
$\mathcal{Q^{\prime}}=(Q_{1},Q_{2}^{\prime},Q_{3})$ is a $2$-feasible set.

Observe that if one of the paths $Q_{1},Q_{2}$, say $Q_{i}$, contains an arc
from $V_{1}$ to $x$, then $Q_{i}$ must also contain the only out-arc $xy$ of
$x$ in $D\left\langle V_{2}\right\rangle$ and $x_{1}x\notin Q_{3-i}$ as
$A(\mathcal{Q})$ contains no arc from $x$ to $V_{1}$. So we may assume w.l.o.g
that $x_{1}x\notin Q_{1}$ and that $Q_{1}$ has no arcs from $V_{1}$ to $x$.
Let $Q_{2}^{\prime}=x_{1}xt\cup Q_{2}[t,b]$, where $b$ is the last vertex of
$Q_{2}$. Clearly $Q_{2}^{\prime}$ is also an $(\\{x_{1}\\},Y)$-path. Replacing
$Q_{2}$ with $Q_{2}^{\prime}$ in $\mathcal{Q}$ and adding all subpaths $uav$
of $Q_{2}[x_{1},t^{-}]$ with $a\in V_{1}$ (see Figure 7 (b)), we obtain a
$2$-feasible set $\mathcal{Q^{\prime}}$ containing the arc $xt$. This means
that the vertex $x$ gains one more out-neighbor and then $x\notin
W_{\mathcal{Q^{\prime}}}^{+}$. Moreover, although $t^{-}$ is loosing one out-
neighbor after the replacement, $t^{-}\notin W_{\mathcal{Q^{\prime}}}^{+}$ as
it has at least two out-neighbors $x,x_{1}$ in $V_{2}$, consequently, in
$D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$. Therefore,
$|W_{\mathcal{Q^{\prime}}}^{+}|<|W_{\mathcal{Q}}^{+}|=|\\{x\\}|$ and
$|W_{\mathcal{Q^{\prime}}}^{-}|=|W_{\mathcal{Q}}^{-}|$, which contradicts
(C1).

###### Case 3

$|V(S_{k})|=3$.

Observe that in this case every vertex of $S_{k}$ has out-degree at least one
in $D\left\langle V_{2}\right\rangle$ as $S_{k}$ is strong. First we claim
that the vertex $t$ that we fixed above belongs to $V(Q_{1})\cup V(Q_{2})$. If
not, then Lemma 3.5 (ii)-(iii) shows that there are two paths
$Q_{i}=w_{1}tz_{1},Q_{j}=w_{2}tz_{2}$ with $i,j\geq 3$ containing $t$.
Moreover, each of $w_{1}$ and $w_{2}$ has out-degree at most two in
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$. This and the fact that
$d_{D\left\langle V_{2}\right\rangle}^{+}(w)\geq 1$ for all $w\in V(S_{k})$
imply that $w_{1}\neq w_{2}$, $V(S_{k})=\\{x,w_{1},w_{2}\\}$ and both $Q_{1}$
and $Q_{2}$ are starting from $x$, which contradicts Lemma 3.5 (i). Thus $t\in
V(Q_{1})\cup V(Q_{2})$.

Next we show that $t\in V(Q_{1})\cap V(Q_{2})$. Suppose to the contrary that
$t\in V(Q_{1})-V(Q_{2})$. Let $a_{1},a_{2}$ be the first vertex of $Q_{1}$ and
$Q_{2}$, respectively. If $a_{1}=a_{2}$, then construct a new $2$-feasible set
$\mathcal{Q^{\prime}}$ by replacing $Q_{1}$ by $xtQ_{1}[t,b]$, where $b$ is
the last vertex of $Q_{1}$. It is not difficult to check that both $x$ and
$a_{1}$ are not vertices in $W_{\mathcal{Q^{\prime}}}^{+}$, which contradicts
(C1). So we may assume that $a_{1}\neq a_{2}$ and thus
$V(S_{k})=\\{x,a_{1},a_{2}\\}$. On the other hand, by Lemma 3.5 (ii), there is
a path $Q_{i}=wtz$ ($i\geq 3$) containing $t$ such that $w$ has out-degree at
most two in $D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$. Then $w$ must be
$x$, which contradicts Lemma 3.5 (i). Therefore, $t$ belongs to $Q_{1}$ and
$Q_{2}$.

Now we claim that $t$ is the second vertex of $Q_{i}$ for all $i\in[2]$.
Otherwise construct a new $2$-feasible set $\mathcal{Q^{\prime}}$ from
$\mathcal{Q}$ by replacing $Q_{i}$ with $xtQ_{i}[t,b]$ and all subpaths $uav$
with $a\in V_{1}$ of $Q_{i}[a_{i},t]$, we obtain a contradiction with (C1) as
$x\notin W_{\mathcal{Q^{\prime}}}^{+}$. This shows that $a_{1}\neq a_{2}$,
$V(S_{k})=\\{x,a_{1},a_{2}\\}$ and there is an arc from each vertex of $S_{k}$
to $t$. Note that for any vertices $u,v\in V(S_{k})$, the arcs $ut,vt$ can be
the first arcs of the $(X,Y)$-paths in any given 2-feasible set $\mathcal{F}$.
As $W_{\mathcal{F}}^{+}$ is not empty, the vertex in $V(S_{k})-\\{u,v\\}$ must
belong to $W_{\mathcal{F}}^{+}$. In other words, every vertex in $V(S_{k})$
can be regarded as $x$ and then every vertex of $S_{k}$ has out-degree one in
$S_{k}$, that is, $S_{k}$ is a 3-cycle. This completes the proof of Lemma 3.6.
$\square$

By symmetry, we have the following.

###### Lemma 3.7

If $W_{\mathcal{Q}}^{-}$ is not empty for each 2-feasible set $\mathcal{Q}$,
then $S_{1}$ is a 3-cycle and each vertex of $S_{1}$ has exactly one in-
neighbor in $V_{1}$. Furthermore, they all have the same in-neighbor in
$V_{1}$.

Completing the proof of Theorem 1.6.

Let $\mathcal{Q}$ be a $2$-feasible set satisfying (C1). Recall that either
$W_{\mathcal{Q}}^{+}\neq\emptyset$ or $W_{\mathcal{Q}}^{-}\neq\emptyset$. By
reversing all arcs of $D$ if necessary, we may assume that
$W_{\mathcal{Q}}^{+}\neq\emptyset$.

It follows by Lemma 3.6 that the terminal component $S_{k}$ of $D\left\langle
V_{2}\right\rangle$ is a 3-cycle. Let $S_{k}=u_{1}u_{2}u_{3}u_{1}$. Moreover,
by Lemma 3.6, every vertex of $V(S_{k})$ has exactly one out-neighbor in
$V_{1}$ and the out-neighbor of them in $V_{1}$ is the same vertex. Suppose
that $t$ is the common out-neighbor of vertices $u_{1},u_{2}$ and $u_{3}$ in
$V_{1}$. Recall that $t$ has out-degree at least three and $Q_{1},Q_{2}$ are
two $(V(S_{k}),Y)$-paths. As $S_{k}$ is a 3-cycle, the vertices $u_{1},u_{2}$
and $u_{3}$ are symmetrical. Relabeling $u_{1},u_{2}$ and $u_{3}$ if
necessary, we may assume that $u_{i}t\in Q_{i}$ for all $i\in[2]$ and $t$ has
an out-arc $tz\in D-u_{3}$ which is not in $Q_{1}\cup Q_{2}$. Note that
$u_{3}$ is the only vertex of $V_{2}$ with out-degree exactly one in
$D_{\mathcal{Q}}\left\langle V_{2}\right\rangle$, that is,
$W_{\mathcal{Q}}^{+}=\\{u_{3}\\}$. By symmetry, if
$W_{\mathcal{Q}}^{-}\neq\emptyset$, then let $S_{1}=v_{1}v_{2}v_{3}v_{1}$.
Moreover, we may assume that $t^{\prime}v_{i}$ $(t^{\prime}\in V_{1})$ is the
last arc of $Q_{i}$ for $i\in[2]$ and $t^{\prime}$ has an in-neighbor in
$wt^{\prime}$ in $D-v_{3}$. Clearly, $W_{\mathcal{Q}}^{-}=\\{v_{3}\\}$.

Let $\mathcal{Q^{\prime}}=\mathcal{Q}\cup\\{u_{3}tz\\}$ if
$W_{\mathcal{Q}}^{-}=\emptyset$ and let
$\mathcal{Q^{\prime}}=\mathcal{Q}\cup\\{u_{3}tz\\}\cup\\{wt^{\prime}v_{3}\\}$
if we also have $W_{\mathcal{Q}}^{-}\neq\emptyset$, see Figure 8 (b). It
should be mentioned that $\mathcal{Q^{\prime}}$ is not $2$-feasible as $t$
(resp., $t^{\prime}$) is in three paths of $\mathcal{Q^{\prime}}$. Moreover,
each vertex of $V_{1}$, except for $t$ and $t^{\prime}$, belongs to at most
two paths in $\mathcal{Q^{\prime}}$. Let $D_{\mathcal{Q^{\prime}}}$ be the
directed multigraph obtained from $D$ by splitting off $\mathcal{Q^{\prime}}$.
Now we claim that $W_{\mathcal{Q^{\prime}}}^{+}=\emptyset$. In fact, note that
each $u_{i}\in V(S_{k})$ has out-degree exactly two in
$D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$ and every vertex of
$V_{2}-V(S_{k})$ has out-degree at least 3 in $D\left\langle
V_{2}\right\rangle$ as it dominates all vertices of $V(S_{k})$. Therefore,
$W_{\mathcal{Q^{\prime}}}^{+}=\emptyset$ and we have
$W_{\mathcal{Q^{\prime}}}^{-}=\emptyset$ in the same way.

$V_{2}$$V_{1}$$v_{1}$$v_{2}$$v_{3}$$w_{1}$$w_{2}$$w_{3}$$u_{1}$$u_{2}$$u_{3}$$t^{\prime}$$t$
(a) $D$

$v_{1}$$v_{2}$$v_{3}$$w_{1}$$w_{2}$$w_{3}$$u_{1}$$u_{2}$$u_{3}$ (b)
$D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$

Figure 8: An illustration of a set
$\mathcal{Q^{\prime}}=(Q_{1},Q_{2},Q_{3},Q_{4})$ which is not $2$-feasible,
where
$Q_{1}=u_{1}tw_{2}t^{\prime}v_{1},Q_{2}=u_{2}tw_{3}t^{\prime}v_{2},Q_{3}=u_{3}tz$
with $z=u_{1}$ and $Q_{4}=wt^{\prime}v_{3}$ with $w=w_{1}$. Both $S_{1}$ and
$S_{k}$ are 3-cycles and all arcs not shown are from top to bottom. The 2-arc-
strong directed multigraph in (b) is obtained from $D\left\langle
V_{2}\right\rangle$ by splitting off all paths in $\mathcal{Q^{\prime}}$. The
dashed arcs in (b) are splitting arcs.

By Lemma 3.4 and the fact that the two $(X,Y)$-paths in
$\mathcal{Q^{\prime}}$, i.e., $Q_{1},Q_{2}$, are starting from and ending at
two distinct vertices, we have that $D_{\mathcal{Q^{\prime}}}\left\langle
V_{2}\right\rangle$ is 2-arc-strong. It follows by Theorem 2.3 that either
$D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$ has a strong arc
decomposition, or $D_{\mathcal{Q^{\prime}}}\left\langle V_{2}\right\rangle$ is
isomorphic to one of the directed multigraphs shown in Figure 2. If the former
case holds, repeating the proof of Lemma 2.5 with
$D^{\ast}=D_{\mathcal{Q^{\prime}}}$ one may obtain a strong arc decomposition
of $D$. Here it should be noted that the condition ‘splitting off at most two
pairs at every vertex in $V_{1}$’ in the statement of Lemma 2.5 only be used
for vertices in $V(D_{i})-V(D_{3-i})$ with $i\in[2]$. Therefore, although we
splitting three pairs at $t$ and $t^{\prime}$ and splitting at most two pairs
at every vertex in $V_{1}-\\{t,t^{\prime}\\}$, as $t,t^{\prime}\in
V(D_{i})\cap V(D_{3-i})$, we also can obtain a strong arc decomposition of $D$
in the same way mentioned in the proof of Lemma 2.5. If the latter case holds,
$D$ also has a strong arc decomposition by Lemma 2.7, which completes the
proof of Theorem 1.6. $\square$

Observe that in the proof of Theorem 1.6, if a given 2-feasible set
$\mathcal{Q}$ violates the condition (C1), then we can construct a new
2-feasible set $\mathcal{Q^{\prime}}$ with
$|W_{\mathcal{Q^{\prime}}}^{+}|+|W_{\mathcal{Q^{\prime}}}^{-}|<|W_{\mathcal{Q}}^{+}|+|W_{\mathcal{Q}}^{-}|$
from $\mathcal{Q}$ by a slight modification of $\mathcal{Q}$. This means that
we may get a 2-feasible set satisfying (C1) in polynomial time and combing
this observation with the fact that all other steps in the proof are
constructive, we conclude the following holds.

###### Theorem 3.8

There exists a polynomial algorithm which given a 2-arc-strong split digraph
$D=(V_{1},V_{2};A)$ such that each vertex of $V_{1}$ has minimum in- and out-
degree at least 3, finds a strong arc decomposition of $D$.

##  4 Arc-disjoint out- and in-branchings in split digraphs

Recall the definitions of in-branchings and out-branchings from the
introduction. A relaxation of the problem of whether a given digraph $D$ has a
strong arc decomposition is to ask whether it contains an out-branching and an
in-branching which are arc-disjoint. Such pair will be called a good pair in
below and more precisely we call it a good $(u,v)$-pair if the roots $u$ and
$v$, of the out- and in-branchings respectively, are specified.

Clearly, a strong digraph contains an out-branching (resp., an in-branching)
with arbitrary given root. Thus the following simple observation holds.

###### Observation 4.1

Every digraph with a strong arc decomposition contains a good $(u,v)$-pair for
every choice of $u,v$.

The above observation and Theorem 1.6 imply the following.

###### Theorem 4.2

Let $D=(V_{1},V_{2};A)$ be a 2-arc-strong split digraph such that $V_{1}$ is
independent and $D\left\langle V_{2}\right\rangle$ is semicomplete. Suppose
that every vertex of $V_{1}$ has both in- and out-degree at least 3 in $D$.
Then $D$ has a good $(u,v)$-pair for every choice of $u,v$.

###### Corollary 3

Every 3-arc-strong split digraph contains a good $(u,v)$-pair for every choice
of $u,v$.

A split digraph $D=(V_{1},V_{2};A)$ is semicomplete if every vertex in the
independent set, i.e., $V_{1}$, is adjacent to every vertex in $V_{2}$. Below
we prove that arc-connectivity 2 is sufficient to guarantee a good pair with
the same root $u$, that is, a good $(u,u)$-pair, in semicomplete split
digraphs.

###### Lemma 4.3

[10] Let $D$ be a digraph and let $X$ be a subset of $V(D)$ such that every
vertex of $D-X$ has both an in-neighbor and an out-neighbor in $X$. If $X$ has
a good $(u,v)$-pair then $D$ has a good $(u,v)$-pair.

###### Theorem 4.4

Let $D$ be a 2-arc-strong digraph and let $u$ be a vertex of $D$. Suppose that
$S$ is a semicomplete induced subdigraph of $D$ containing the vertex $u$. If
every vertex in $D-S$ has at least two in- and out-neighbors in $V(S)$, then
there is a good $(u,u)$-pair in $D$.

Proof. Let $N^{+}_{S}(u)=A\cup C$ and $N^{-}_{S}(u)=B\cup C$, where $C$ is the
set of vertices that form a 2-cycle with $u$. Possibly $A,B$ or $C$ is empty.
We may assume that $A\cup B\neq\emptyset$ since otherwise $S$ clearly has a
good pair rooted at $s$ and the claim follows by Lemma 4.3. By symmetry
(reversing all arcs of $D$ if necessary) we may assume that $A\neq\emptyset$.
Let $Ter(A)$ be the terminal component of $D\left\langle A\right\rangle$ and
let $Ini(B)$ be the initial component of $D\left\langle B\right\rangle$ when
$B\neq\emptyset$.

Since $D$ is 2-arc-strong, there are two arc-disjoint $(V(Ter(A)),W)$-paths
$P_{1},P_{2}$ in $D$, where $W=V(Ini(B))$ if $B\neq\emptyset$ and $W=\\{u\\}$
when $B$ is empty. Suppose that $p_{1}$ is the first vertex of $P_{1}$ and
$q_{1}$ is the first vertex of $P_{1}$ in $B\cup C\cup\\{u\\}$. Similarly,
suppose that $p_{2}$ is the last vertex of $P_{2}$ in $A\cup C\cup\\{u\\}$ and
$q_{2}$ is the last vertex of $P_{2}$. Let $Q_{i}=P_{i}[p_{i},q_{i}]$ for all
$i\in[2]$. Note that $p_{2}=q_{2}=u$ when $B$ is empty.

By our assumption, for each vertex $w\in D-S$, if it belongs to $Q_{2}-Q_{1}$,
then it has an out-neighbor $w_{o}$ in $V(S)$ which is distinct from the
successor of $w$ on $Q_{2}$ and if $w$ belongs to $Q_{1}-Q_{2}$, then it has
an in-neighbor $w_{I}$ in $S$ which is distinct from the predecessor of $w$ on
$Q_{1}$. So we can obtain a good $(u,u)$-pair $(O,I)$ in $D\left\langle
V(Q_{1}\cup Q_{2}\cup S)\right\rangle$ as follows (if $B$ is empty, then
ignore the items related to $B$) and then $D$ has a good pair rooted at $u$ by
Lemma 4.3, see Figure 9.

Construct $I$ from $Q_{1}$ and an in-branching rooted at $p_{1}$ in $Ter(A)$
by adding arcs $\\{ru:r\in B\cup C\\}\cup\\{rp_{1}:r\in
A-V(Ter(A))-V(Q_{1})\\}$ and $\\{ww_{o}:w\in V(Q_{2}-Q_{1})\cap V(D-S)\\}$.
Moreover, construct $O$ from the path $Q_{2}$ and an out-branching rooted at
$q_{2}$ in $Ini(B)$ by adding arcs $\\{ur:r\in A\cup C\\}\cup\\{q_{2}r:r\in
B-V(Ini(B))-V(Q_{2})\\}$ and $\\{w_{I}w:w\in V(Q_{1}-Q_{2})\cap V(D-S)\\}$.
$\square$

$q_{2}$$q_{1}$$w_{I}$$p_{1}$$p_{2}$$u$$w$ Figure 9: An illustration of a good
$(u,u)$-pair constructed in the proof of Theorem 4.4, when
$A=\\{w_{I},p_{1}\\},B=\\{q_{1},q_{2}\\},C=\\{p_{2}\\}$ and $V(D-S)=\\{w\\}$.
Moreover, $Q_{1}=p_{1}wq_{1}$ and $Q_{2}=p_{2}q_{2}$. For readability we have
only shown the relevant arcs of $D$. The out- and in-branching are shown in
bold and thin arcs, respectively.

The following corollary follows by Theorem 4.4 with $S=D\left\langle
V_{2}\cup\\{u\\}\right\rangle$ and the fact that every vertex in $V_{1}$ has
at least two in-neighbors and at least two out-neighbors in $V_{2}$
(consequently in $V_{2}\cup\\{u\\}$).

###### Corollary 4

Let $D=(V_{1},V_{2};A)$ be a 2-arc-strong split digraph and let $u$ be an
arbitrary vertex of $D$. If $D\left\langle V_{2}\cup\\{u\\}\right\rangle$ is
semicomplete, then $D$ has a good pair rooted at $u$. In particular, every
2-arc-strong semicomplete split digraph has a good $(u,u)$-pair for every
choice of $u$.

###### Conjecture 4.1

Every 2-arc-strong semicomplete split digraph $D$ contains a good $(u,v)$-pair
for every choice of vertices $u,v$ of $D$.

The example in Figure 10 shows that even vertex-connectivity 2 is not
sufficient to guarantee the existence of a good $(u,v)$-pair for every choice
of $u$ and $v$ in a general split digraph, even when both $u$ and $v$ are
vertices of $V_{2}$ and the subdigraph induced by $V_{2}$ is strong.

$V_{2}$$V_{1}$$u_{t}^{+}$$v$$b$$u$$a$$v_{t}$$w$$u_{t}$$W$ $D_{1}$

$V_{2}$$V_{1}$$u_{t}^{+}$$b$$v$$a$$u$$v_{t}$$u_{t}$$W$ $D_{2}$

Figure 10: Split digraphs with vertex partition $V_{1}\cup V_{2}$ such that
$V_{1}$ is independent and $D\left\langle V_{2}\right\rangle$ is semicomplete.
$W$ is an arbitrary semicomplete digraph containing the vertex $u_{t}^{+}$.
All arcs in $D_{1}\left\langle V_{2}\right\rangle-W$ are from top to bottom
and all arcs in $D_{2}\left\langle V_{2}\right\rangle-W$ except for
$\\{ua,ab,bv\\}$ are from top to bottom. Note that $D_{2}\left\langle
V_{2}\right\rangle$ is strong.

###### Proposition 4.5

The 2-strong split digraphs in Figure 10 have no good $(u,v)$-pairs.

Proof. It is not difficult to check that $D_{i}$ is 2-strong for all
$i\in[2]$. Now we claim that $uawbv$ and $uu_{t}u_{t}^{+}v_{t}v$ is the only
pair of arc-disjoint $(u,v)$-paths in $D_{1}$. Note that for any pair of arc-
disjoint $(u,v)$-paths $P_{1},P_{2}$ in $D_{1}$, we can label these so that
$awb\in P_{1}$ and $u_{t}u_{t}^{+}v_{t}\in P_{2}$. Since
$N_{D_{1}}^{-}(a)=\\{u,w\\}$ and $aw\in P_{1}$, the arc $ua\in P_{1}$. In the
same way, we have $bv\in P_{1}$ as $N_{D_{1}}^{+}(b)=\\{v,w\\}$. That is,
$P_{1}=uawbv$. On the other hand, since the out-neighbor are of $u$ in $D_{1}$
are $u_{t},a$ and the arc $ua$ belongs to $P_{1}$, we have $uu_{t}\in P_{2}$
and we also have $v_{t}v\in P_{2}$ by symmetry, which shows that
$P_{2}=uu_{t}u_{t}^{+}v_{t}v$.

Suppose that $D_{1}$ has a good $(u,v)$-pair $(O,I)$ in $D_{1}$ and assume
that $P_{i}$ and $P_{3-i}$ ($i\in[2]$) are the $(u,v)$-path in $O$ and $I$,
respectively. If $i=1$, then $uu_{t}\in I$ and $aw\in O$. By the definitions
of in- and out-branchings, each vertex in $D_{1}-u$ has in-degree one in $O$
and each vertex in $D_{1}-v$ has out-degree one in $I$. Hence the arc $au_{t}$
should be used in $O$ to collect $u_{t}$ and also should be used in $I$ to
collect $a$, a contradiction. For the case $i=2$, it is not difficult to check
that the arc $v_{t}b$ should be used both in $O$ and $I$, a contradiction
again. Therefore, $D_{1}$ has no good $(u,v)$-pair. Similarly, $uabv$ and
$uu_{t}u_{t}^{+}v_{t}v$ is the only pair of arc-disjoint $(u,v)$-paths in
$D_{2}$ and there is no good $(u,v)$-pair in $D_{2}$ as the arc $v_{t}b$ or
$au_{t}$ should be used both in the out- and in-branchings. $\square$

The following proposition follows immediately by the fact that the subdigraph
$W$ in Figure 10 can be any semicomplete digraph.

###### Proposition 4.6

There are infinitely many 2-strong split digraphs which do not have good
$(u,v)$-pairs for some choice of $u,v$.

Combining Observation 4.1 and Proposition 4.6, we have the following
corollary, which implies that the connectivity condition in Theorem 1.6 is
best possible in some sense.

###### Corollary 5

There are infinitely many 2-strong split digraphs which do not have a strong
arc decomposition.

##  5 Remarks and further open problems

###### Problem 1

Does all but a finite number of 2-arc-strong semicomplete split digraphs have
a strong arc decomposition?

Note that we allow the independent set $V_{1}$ of a split digraph to be empty.
Thus every semicomplete digraph is a split digraph and hence $S_{4}$ is an
exception above.

The degree of a vertex $v$ in $D$ is $d(v)=d^{+}(v)+d^{-}(v)$.

###### Problem 2

Does every 2-arc-strong split digraph with minimum degree at least 5 have a
strong arc decomposition?

The 2-linkage problem is the following: given a digraph $D=(V,A)$ and four
distinct vertices $s_{1},s_{2},t_{1},t_{2}$; does $D$ have a pair of disjoint
paths $P_{1},P_{2}$ such that $P_{i}$ is an $(s_{i},t_{i})$-path for $i=1,2$?

The 2-linkage problem can be solved in polynomial time for semicomplete
digraphs [9].

###### Problem 3

Is there a polynomial algorithm for the 2-linkage problem for split digraphs?

It was shown in [16] that every 5-strong semicomplete digraph $D$ is 2-linked,
that is, it has a pair of disjoint paths $P_{1},P_{2}$ such that $P_{i}$ is an
$(s_{i},t_{i})$-path for $i=1,2$ for all choices of distinct vertices
$s_{1},s_{2},t_{1},t_{2}$. It was shown in [2] that the bound on the
connectivity cannot be lowered.

Using the same approach as on pages 386 and 387 in [4] it is easy to show that
every 6-strong semicomplete split digraph is 2-linked.

###### Problem 4

Is every 6-strong split digraph 2-linked?

## References

  * [1] J. Ai, S. Gerke, G. Gutin, A. Yeo, and Y. Zhou.  Results on the small quasi-kernel conjecture.  Disc. Math, 346:113435, 2023.
  * [2] J. Bang-Jensen.  On the $2$-linkage problem for semicomplete digraphs.  In Graph theory in memory of G. A. Dirac (Sandbjerg, 1985), volume 41 of Ann. Discrete Math., pages 23–37. North-Holland, 1989.
  * [3] J. Bang-Jensen and G. Gutin.  Paths, trees and cycles in tournaments.  Congr. Numer., 115:131–170, 1996.  Surveys in graph theory (San Francisco, 1995).
  * [4] J. Bang-Jensen and G. Gutin.  Digraphs: Theory, Algorithms and Applications.  Springer-Verlag, London, 2nd edition, 2009.
  * [5] J. Bang-Jensen, G. Gutin, and A. Yeo.  Arc-disjoint strong spanning subdigraphs of semicomplete compositions.  J. Graph Theory, 95(2):267–289, 2020.
  * [6] J. Bang-Jensen, F. Havet, and A. Yeo.  Spanning eulerian subdigraphs in semicomplete digraphs.  J. Graph Theory, 102(3):578–606, 2023.
  * [7] J. Bang-Jensen and J. Huang.  Decomposing locally semicomplete digraphs into strong spanning subdigraphs.  J. Combin. Theory Ser. B, 102:701–714, 2010.
  * [8] J. Bang-Jensen, Y. Manoussakis, and C. Thomassen.  A polynomial algorithm for Hamiltonian-connectedness in semicomplete digraphs.  J. Algor., 13(1):114–127, 1992.
  * [9] J. Bang-Jensen and C. Thomassen.  A polynomial algorithm for the 2-path problem for semicomplete digraphs.  SIAM J. Discrete Math., 5:366–376, 1992.
  * [10] J. Bang-Jensen and Y. Wang.  Arc-disjoint in- and out-branchings in compositions of semicomplete digraphs.  Submitted.
  * [11] J. Bang-Jensen and A. Yeo.  Decomposing $k$-arc-strong tournaments into strong spanning subdigraphs.  Combinatorica, 24(3):331–349, 2004.
  * [12] J. Bang-Jensen and A. Yeo.  Arc-disjoint spanning sub(di)graphs in digraphs.  Theor. Comput. Sci., 438:48–54, 2012.
  * [13] P. Hell and C. Hernández-Cruz.  Strict chordal and strict split digraphs.  Discret. Appl. Math., 216:609–617, 2017.
  * [14] M. D. Lamar.  Split digraphs.  Discret. Math., 312(7):1314–1325, 2012.
  * [15] Y. Sun, G. Gutin, and J. Ai.  Arc-disjoint strong spanning subdigraphs in compositions and products of digraphs.  Discret. Math., 342(8):2297–2305, 2019.
  * [16] C. Thomassen.  Connectivity in tournaments.  In Graph theory and combinatorics (Cambridge, 1983), pages 305–313. Academic Press, 1984.
  * [17] C. Thomassen.  Configurations in graphs of large minimum degree, connectivity, or chromatic number.  Annals of the New York Academy of Sciences, 555:402–412, 1989.


# U-Noise: Learnable Noise Masks for Interpretable Image Segmentation

###### Abstract

Deep Neural Networks (DNNs) are widely used for decision making in a myriad of
critical applications, ranging from medical to societal and even judicial.
Given the importance of these decisions, it is crucial for us to be able to
interpret these models. We introduce a new method for interpreting image
segmentation models by learning regions of images in which noise can be
applied without hindering downstream model performance. We apply this method
to segmentation of the pancreas in CT scans, and qualitatively compare the
quality of the method to existing explainability techniques, such as Grad-CAM
and occlusion sensitivity. Additionally we show that, unlike other methods,
our interpretability model can be quantitatively evaluated based on the
downstream performance over obscured images.

Index Terms—  Segmentation, Interpretability, Medical Imaging

##  1 Introduction

The ability to interpret the decisions made by predictive models helps to
understand and evaluate model performance and has been a useful tool for
identifying algorithmic biases [1]. In recent years, several methods for
interpreting neural networks, which have typically been considered "black
boxes", have been developed [2, 3].

Most of the recent advancements have prioritized interpretability in image
classification tasks, with little development in other important tasks like
image segmentation. Image segmentation is an active area of research in
medical domains, for tumor and disease identification [4, 5]. However, if
these tools are to be used in practice by medical professionals to drive
complex and life-changing decisions, it is necessary to be able to explain and
understand how segmentations are made.

Motivated by these applications, we introduce U-Noise, a novel method to
interpret segmentation models through noisy image occlusion 111The code for
this work can be found at https://github.com/teddykoker/u-noise. U-Noise
learns to develop interpretability maps from training images, which makes it
an extensible and easily deployable interpretation method; once trained,
U-Noise is quick to generate interpretability maps for new images.

U-Noise interprets an already trained segmentation model (we name it the
Utility model), whose parameters are frozen, and finds the context that it
uses to semantically segment an image to find a target through a systematic
process of adding noise. For example, in the case of pancreas segmentation in
CT-scans, U-Noise finds the context organs used by the model to identify where
the pancreas is.

U-Noise builds on the intuition that if the model is resilient to the addition
of noise with high scale (standard deviation) to a pixel, then that pixel is
not important with respect to the model we are trying to interpret. We train a
small neural network called an interpretability model, to directly
parameterize the noise distribution (noise mask) for each pixel in an input
image, such that the segmentation accuracy is not harmed. Once the training is
finished, we can generate an "importance map" for each input image by feeding
it to the interpretability model. Pixels that would have received noise with a
higher scale are less important and vice-versa. Figure 1 shows the workflow of
U-noise for training the interpretability model.

There are only a few previous works that focus on segmentation
interpretability [6, 7]. These works solve the problem in a lower resolution
setup, and then up-sample to get pixel level explanation. They either return
explanations for a part of the image [6, 7], a single pixel [6], or for the
whole class [6]. Our method on the other hand, seamlessly returns the relative
importance of each pixel, with respect to the entire input.

##  2 Related Work

Fig. 1: The components and the training process of our proposed U-Noise
method. The model we are trying to interpret (utility model, $U$) is frozen,
and the interpretability model is being trained. The interpretability model’s
output is the standard deviation of the noise tolerated by each pixel of the
input. It is then multiplied by random noise and fed to $U$, to measure its
utility for the loss function, and update the interpretability model
accordingly.

Since our work is on the interpretability of image segmentation, and our
proposed method trains noise distributions directly, we divide the related
work into two sections: DNN interpretability methods for vision tasks and
probability distribution training methods for neural networks.

Interpretability. CAM [8], Grad-CAM [9], occlusion sensitivity [10] and T-CAV
[11] are the state-of-the-art methods for classification interpretation using
CNNs. Grad-CAM uses the gradients of target concepts to measure sensitivity
and offer explanations. However, this is done for intermediate activations and
upsampled to match the original image, which causes some loss in
interpretation power. Occlusion sensitivity covers parts of the input to find
important regions and is therefore computationally intensive. Hoyer et al. [7]
use perturbations for interpreting segmentation models, however, they do not
train the noise parameters as we do, and they also use upsampling for getting
pixel-level explanations, unlike our framework which offers importance levels
for each pixel directly.

Distribution Training. Mireshghallah et al. introduced Cloak [12], a method
that trains distributions to obscure parts of the image for privacy purposes.
Our work is also related to a method called Bayes by backprop [13], which
trains distribution parameters using backpropagation, for weights of Bayesian
neural networks. U-Noise builds upon these methods to directly train dynamic
noise maps, where the noise parameters can change based on the input image,
unlike previous work which offers static distributions.

Segmentation. U-Net [14] is a powerful image segmentation architecture which
is used extensively in medical domains [5]. The model consists of a
contracting path of convolutions to capture context from the image, followed
by an expanding path of deconvolutions to allow precise object localization.
The architecture is fast and produces high-resolution segmentations.

##  3 U-Noise

We build on the intuition that if a pixel is important for the decision making
of a trained model that is supposed to run a task, in our case segmentation,
then adding noise with high scale to this pixel would harm that model’s
utility. As such, we define a utility model $U$ (with parameters
$\theta_{U}$), which is the model whose decisions we want to interpret, and an
interpretability model $N$ (with parameters $\theta_{N}$, whose purpose is to
compute the scale of noise to be applied to each pixel, while simultaneously
maximizing utility model performance, as well as the total scale of noise
applied. In the segmentation task explored in this work, both the $U$ and $N$
have a U-Net architecture. Figure 1 shows the components of U-Noise and how
they interact.

Given an image $x\in\mathbb{R}^{C\times H\times W}$ with $C$ channels, and a
height and width of $H$ and $W$ pixels respectively, the noise model produces
a mask $B\in\mathbb{R}^{H\times W}=N(x;\theta_{N})$ contained in the range
$[0,1]$ by the sigmoid function. $B$ is then linearly scaled to range
$[\sigma_{\text{min}},\sigma_{\text{max}}]$ (hyperparameters) to determine the
scale of noise applied to each pixel. The noised image, $x^{\prime}$, is then
produced:

$x^{\prime}_{ij}=x_{ij}+B_{ij}(\sigma_{\text{max}}-\sigma_{\text{min}})\epsilon+\sigma_{\text{min}}$
(1)

Where $\epsilon\sim\mathcal{N}(0,1)$ is sampled from the standard normal
distribution. The predicted segmentation mask,
$\hat{y}=U(x^{\prime};\theta_{U})$ is then computed using the frozen utility
model. The goal of the training process for the interpretability model is:

$\min_{\theta_{N}}\quad-\log\Pr(\hat{y}|y;\theta_{U},\theta_{N})-\lambda\log
B$

Where $\theta_{N}$ and $\theta_{U}$ are the parameters of the interpretability
and utility model, respectively. The first term is the utility loss, which is
the cross-entropy loss that incentivizes $N$ to orchestrate the noise such
that the utility of the main model is unharmed. The second term is $-\log{B}$,
which incentivizes the growth of the scale (standard deviation) of the noise
standard deviation for each pixel so that we can find the unimportant ones.
Algorithm 1 shows the training process in U-Noise. The trade-off between the
two terms is governed by $\lambda$, the noise ratio hyperparameter.

Training of the interpretability model only takes place once, after which one
only needs to run inference on the interpretability model to interpret a new
image.

Input: Input images $X$, segmentation masks $Y$, learning rate $\eta$, noise
model $N$ with parameters $\theta_{N}$, trained utility model $U$ with
parameters $\theta_{U}$, learning rate $\eta$, min/max noise scale
$\sigma_{\text{min}}$ and $\sigma_{\text{max}}$

Output: Trained noise model parameters $\theta_{N}$

while  _not converged_ do

for  _$x\in X,y\in Y$_ do

$B\leftarrow N(\theta_{N},x)$ ;

$\epsilon\sim\mathcal{N}(0,1)$ ;

$x^{\prime}\leftarrow
x+B(\sigma_{\text{max}}-\sigma_{\text{min}})\epsilon+\sigma_{\text{min}}$ ;

$\hat{y}\leftarrow U(x^{\prime};\theta_{U})$ ;

$\mathcal{L}_{\text{utility}}\leftarrow\text{CrossEntropy}(y,\hat{y})$ ;

$\mathcal{L}\leftarrow\mathcal{L}_{\text{utility}}-\lambda\log B$;

$\theta_{N}\leftarrow\theta_{N}+\eta\frac{d\mathcal{L}}{d\theta_{N}}$;

end for

end while

Algorithm 1 Train U-Noise

##  4 Results

###  4.1 Experimental Setup

We apply the U-Noise framework to a pancreas segmentation task on a dataset
from [15]. This publicly available dataset contains CT scans of the pancreatic
region and associated masks outlining the pancreas. For all experiments, we
use a pre-trained U-Net model as the Utility model. We train various sizes of
U-Noise interpretability models, outlined in Table 1. Each model is trained
with a minibatch size of 8 for 100 epochs.

Model name | Depth | Channels | Parameter count
---|---|---|---
Utility | 5 | $2^{6}$ | 34M
U-Noise Small | 2 | $2^{4}$ | 10K
U-Noise Medium | 3 | $2^{4}$ | 130K
U-Noise Large | 4 | $2^{4}$ | 537K

Table 1: Details of the Utility and U-Noise models used in experiments. Depth
denotes the number of downsample and upsample layers; Channels denotes the
number of output channels of the first layer.

###  4.2 Method Comparison

Image + Mask | U-Noise Large | Occlusion | Grad-CAM
---|---|---|---
|  |  |
|  |  |
|  |  |
|  |  |

Fig. 2: Comparison of U-Noise Large model to Occlusion Sensitivity and Grad-
CAM interpretation techniques.

Fig. 2 plots a random selection of images from the Pancreas-CT validation set,
interpreted by different methods: U-Noise Large, occlusion sensitivity, and
Grad-CAM. For U-Noise, we visualize the positive values retrieved prior to the
sigmoid layer in the noise model. For occlusion sensitivity, we convolve a
15x15 pixel window through the image with a stride of 2 pixels. At each
position, we report the dice coefficient relative to the unoccluded image.
Finally, for Grad-CAM, we follow [6, 11] and obtain a heatmap with respect to
the convolutional layer at the bottleneck of the Utility model.

Qualitatively, it can be seen that, unlike the other methods, U-Noise places
the highest importance on the pancreas itself. Logically, this can be
interpreted as a pixel being labeled as part of the pancreas increases the
probability of neighboring pixels also being labeled as the pancreas. Other
pixels of importance tend to be on the borders of organs near the pancreas and
the outside edges of the body, demonstrating what the model might be using to
signpost towards the pancreas. In comparison, it is not clear how to interpret
the heatmaps from the other techniques.

Fig. 3(b) shows pixels at each decile of importance, as ranked by the
interpretability model, for an example image by setting a threshold for
occlusion map value below which pixels were zeroed. The first pixels to be un-
zeroed (the most important) relate to the pancreas. Next are the edges of the
body and nearby organs, suggesting that these are used to identify pancreas
location and extent.

###  4.3 Utility Tradeoff

(a) Percent image occlusion vs utility performance

|  |  |
---|---|---|---

(b) Image thresholded at $B\leq[0.1,0.3,0.5,0.7]$

Fig. 3: Effect of thresholding images to the percentage of the image visible,
and the accuracy of the downstream utility model. Models marked Pretrained
were first trained on the pancreas segmentation task before the noise task.
Intuitively, we observe a direct relationship between the percent of the image
visible and the ability of the utility model to segment the image.

Fig. 3(a) plots the dice coefficient of U-Noise against the percentage of
zeroed pixels in an image. The dice coefficient decreases minimally until less
than $~{}90\%$ of the image is visible, after which the model utility
decreases steadily. This suggests that the utility model requires context from
a large number of pixels in the image to make the segmentation.

The differences in utility response of the models when up to 50% of the image
is visible suggests that the pixel priority learned by the large model is sub-
optimal.

We analyze the importance assigned to each pixel by the occlusion map by
zeroing pixels with an occlusion map value above a certain threshold. Fig.
3(a) plots the impact on dice coefficient against the zero threshold and the
corresponding percentage pixels in the image which have been zeroed.

###  4.4 Model Pretraining

Fig. 4: Effect of model size and pretraining. We observe that the Small model
shows the least improvement to pretraining on the original task, while it
seems necessary for the Large model.

Fig. 4 plots the dice coefficient of U-Noise when 50% of the image is visible,
both when the interpretability model was and was not initialized with the
trained Utility model parameters. Unsurprisingly, U-Noise performs better with
a pre-trained interpretability model as it takes advantage of the pancreas
identification learned by the Utility model. The inverse relationship between
interpretability model size and U-Noise utility suggests that the
interpretability model struggles to simultaneously learn the implicit tasks of
pancreas identification and pixel importance ranking.

Although the absolute differences in dice coefficient are small, taken to its
extreme this may suggest that large interpretability models must be pre-
trained in order for U-Noise interpretations to work well. In non-segmentation
tasks, where the interpretability and Utility models may not share an
architecture and therefore cannot easily share parameters, it may not be
possible to use large interpretability models.

###  4.5 Run-time Analysis

Method | Inference Time (seconds) | Training Time | Parameters
---|---|---|---
U-Noise Large | 0.0031 | 4 hours 56 min. 30 sec. | 537K
Grad-CAM | 0.046 | NA | 34M
Occlusion Sensitivity | 201.37 | NA | 34M

Table 2: Compute requirements of different interpretability methods. Average
over 10 trials. Methods compared using an NVIDIA 2070 Super GPU.

Table 2 compares the computational cost of U-Noise to Grad-CAM and Occlusion
Sensitivity. Once trained, our method is orders of magnitude quicker to infer
than the others, making it more applicable for use at scale. In situations
where specialized, high-performance compute is not easily available (for
example in hospitals, for use-cases explored in this work), U-Noise remains a
useful interpretation method.

##  5 Conclusion and Future Work

In this paper, we present U-Noise, a noise-based framework for interpreting
image segmentation models. U-Noise discovers the pixels on which the
segmentation model relies to makes its decision, by applying additive noise
and observing how sensitive the model utility is to changes in the value of
each pixel. While this work has only considered U-Noise in segmentation tasks,
the method can in principle be applied to other tasks.

Additionally, the architecture presented in this work offers a lightweight
method for occluding sections of an image without severely compromising task
utility. Therefore, U-Noise could be utilized to obscure user data on-device
in a more directed way than existing privacy methods, such as local
differential privacy [16]. The efficacy of U-Noise for the purpose of user
privacy should be explored in detail.

Ethical Considerations. We have made sure that the data we used was collected
under HIPAA provenance and that the privacy of the patients who have
contributed to the dataset is not violated.

## References

  * [1] Lisa Anne Hendricks, Kaylee Burns, Kate Saenko, Trevor Darrell, and Anna Rohrbach,  “Women also snowboard: Overcoming bias in captioning models,”  in European Conference on Computer Vision. Springer, 2018, pp. 793–811.
  * [2] Scott M Lundberg and Su-In Lee,  “A unified approach to interpreting model predictions,”  in Advances in Neural Information Processing Systems 30, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, Eds., pp. 4765–4774. Curran Associates, Inc., 2017.
  * [3] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin,  “"why should I trust you?": Explaining the predictions of any classifier,”  in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016, 2016, pp. 1135–1144.
  * [4] Michal Drozdzal, Gabriel Chartrand, Eugene Vorontsov, Mahsa Shakeri, Lisa Di Jorio, An Tang, Adriana Romero, Yoshua Bengio, Chris Pal, and Samuel Kadoury,  “Learning normalized inputs for iterative estimation in medical image segmentation,”  Medical image analysis, vol. 44, pp. 1–13, 2018.
  * [5] Ozan Oktay, Jo Schlemper, Loic Le Folgoc, Matthew Lee, Mattias Heinrich, Kazunari Misawa, Kensaku Mori, Steven McDonagh, Nils Y Hammerla, Bernhard Kainz, et al.,  “Attention u-net: Learning where to look for the pancreas,”  arXiv preprint arXiv:1804.03999, 2018.
  * [6] Kira Vinogradova, Alexandr Dibrov, and Gene Myers,  “Towards interpretable semantic segmentation via gradient-weighted class activation mapping (student abstract),”  Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 10, pp. 13943–13944, Apr. 2020.
  * [7] Lukas Hoyer, Mauricio Munoz, Prateek Katiyar, Anna Khoreva, and Volker Fischer,  “Grid saliency for context explanations of semantic segmentation,”  in Advances in Neural Information Processing Systems, 2019, pp. 6462–6473.
  * [8] Bolei Zhou, Aditya Khosla, Agata Lapedriza, Aude Oliva, and Antonio Torralba,  “Learning deep features for discriminative localization,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 2921–2929.
  * [9] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra,  “Grad-cam: Visual explanations from deep networks via gradient-based localization,”  in Proceedings of the IEEE international conference on computer vision, 2017, pp. 618–626.
  * [10] Matthew D Zeiler and Rob Fergus,  “Visualizing and understanding convolutional networks,”  in European conference on computer vision. Springer, 2014, pp. 818–833.
  * [11] David Alvarez Melis and Tommi Jaakkola,  “Towards robust interpretability with self-explaining neural networks,”  in Advances in Neural Information Processing Systems, 2018, pp. 7775–7784.
  * [12] Fatemehsadat Mireshghallah, Mohammadkazem Taram, Ali Jalali, Ahmed Taha Elthakeb, Dean Tullsen, and Hadi Esmaeilzadeh,  “A principled approach to learning stochastic representations for privacy in deep neural inference,”  arXiv preprint arXiv:2003.12154, 2020.
  * [13] Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra,  “Weight uncertainty in neural networks,”  in Proceedings of the 32nd International Conference on International Conference on Machine Learning-Volume 37, 2015, pp. 1613–1622.
  * [14] Olaf Ronneberger, Philipp Fischer, and Thomas Brox,  “U-net: Convolutional networks for biomedical image segmentation,”  in International Conference on Medical image computing and computer-assisted intervention. Springer, 2015, pp. 234–241.
  * [15] “Medical segmentation decathlon,” http://medicaldecathlon.com/#organisers,  Accessed: 2021-01-11.
  * [16] Cynthia Dwork,  “Differential privacy,”  in Proceedings of the 33rd international conference on Automata, Languages and Programming-Volume Part II. Springer-Verlag, 2006, pp. 1–12.