We can argue as in the proof of Lemma A.17 in order to show that, for every
vertex $u$ in $H_{r}$ that is not $z$ or $d(r)$ (if $r\neq s$), there is a
path from $r$ to $u$ in $H_{r}$ that avoids $(d(z),z)$, and therefore all of
the edges $\\{(z,y_{1}),\dots,(z,y_{k})\\}$. Furthermore, there is certainly a
path in $H_{r}$ from $r$ to $z$ (by Corollary A.7), and so we can definitely
reach $z$ from $r$ in $H_{r}\setminus\\{(z,y_{1}),\dots,(z,y_{k})\\}$. ∎

######  Lemma A.21.

Let $G_{s}$ be a strongly connected digraph and let $r$ be either a marked
vertex of $G_{s}$ or $s$. Let $u$ and $v$ be two vertices of $H_{r}$, and let
$(x,y)$ be an edge of $G_{s}$ such that either $(1)$ both $x$ and $y$ are
ordinary vertices of $H_{r}$, or $(2)$ $y$ is a marked vertex of $G_{s}$ and
$x=d(y)$, or $(3)$ $(x,y)=(d(r),r)$ (assuming that $r\neq s$). Then $u$ can
reach $v$ in $G_{s}\setminus{(x,y)}$ if and only if $u$ can reach $v$ in
$H_{r}\setminus{(x,y)}$.

###### Proof.

$(\Rightarrow)$ Let $P$ be a path in $G_{s}\setminus{(x,y)}$ that starts from
$u$ and ends in $v$. Now consider the corresponding path $P_{H}$ of $P$ in
$H_{r}$. Then, since either one of $(1)$, $(2)$, or $(3)$ holds for $(x,y)$,
by Lemma A.6 we have that $(x,y)$ is not contained in $P_{H}$. Thus $u$ can
reach $v$ in $H_{r}\setminus{(x,y)}$.
$(\Leftarrow)$ Let us assume that $u$ cannot reach $v$ in
$G_{s}\setminus{(x,y)}$. Now let’s assume for the sake of contradiction that
there is path $\tilde{P}$ in $H_{r}\setminus{(x,y)}$ that starts from $u$ and
ends in $v$. By Lemma A.6, there is a path $P$ in $G_{s}$ such that
$P_{H}=\tilde{P}$. Since either one of $(1)$, $(2)$, or $(3)$ holds for
$(x,y)$, by the same Lemma we have that $(x,y)$ is not contained in $P$. But
this means that $u$ can reach $v$ in $G_{s}\setminus{(x,y)}$ \- a
contradiction. ∎

Now we can describe the structure of the strongly connected components of the
graphs that appear in Corollary A.16 when we remove a strong bridge from them.

######  Lemma A.22.

Let $G_{s}$ be a strongly connected digraph. Let $(x,y)$ be a strong bridge of
$H_{ss}$. Then the strongly connected components of $H_{ss}\setminus{(x,y)}$
are given by one of the following:

  1. (i)

$\\{x\\}$ and $H_{ss}\setminus\\{x\\}$, where $x$ is auxiliary in $H_{s}$ and
$y=d(x)$ in $G_{s}$ (see case $(1.3)$ below)

  2. (ii)

$\\{x\\}$ and $H_{ss}\setminus\\{x\\}$, where $x$ is auxiliary in $H_{ss}$ and
$(x,y)$ is the only outgoing edge of $x$ in $H_{ss}$ (see case $(3.3)$ below)

  3. (iii)

$\\{y\\}$ and $H_{ss}\setminus\\{y\\}$, where $y$ is auxiliary in $H_{ss}$ and
$x=d(y)$ in $H_{s}^{R}$ (see cases $(2.1)$ and $(2.2)$ below)

  4. (iv)

$\\{x\\}$, $\\{y\\}$ and $H_{ss}\setminus\\{x,y\\}$, where $x$ is auxiliary in
$H_{s}$, $y$ is auxiliary in $H_{ss}$, $x=d(y)$ in $H_{s}^{R}$ and $y=d(x)$ in
$G_{s}$ (see case $(2.3)$ below)

###### Proof.

Let $(x,y)$ be an edge of $H_{ss}$. We start by distinguishing four different
cases, depending on whether $x$ and $y$ are ordinary or auxiliary vertices of
$H_{ss}$.

$(1)$ Let $x$ and $y$ be both ordinary vertices of $H_{ss}$. Here we
distinguish four different cases, depending on whether $x$ and $y$ are
ordinary or auxiliary in $H_{s}$. Notice that, in any case, $(y,x)$ is an edge
of $H_{s}$. $(1.1)$ Let $x$ and $y$ be both $\mathit{oo}$-vertices. Then, by
Lemma A.17, $s$ can reach all vertices of $H_{s}$ in $H_{s}\setminus{(y,x)}$.
Thus, with the removal of $(x,y)$ from $H_{s}^{R}$, every vertex of
$H_{s}^{R}$ can reach $s$. Thus, Lemma A.21 implies that, even by removing
$(x,y)$ from $H_{ss}$, every vertex from $H_{ss}$ can reach $s$. Now, since
$x$ and $y$ are both ordinary vertices of $H_{ss}$, by Lemma A.17 we have that
$s$ can reach every vertex in $H_{ss}\setminus{(x,y)}$. We conclude that
$H_{ss}\setminus{(x,y)}$ is strongly connected. $(1.2)$ Let $x$ be
$\mathit{oo}$ and $y$ be $\mathit{oa}$. Then we use precisely the same
argument as in $(1.1)$ to conclude that $H_{ss}\setminus{(x,y)}$ is strongly
connected. $(1.3)$ Let $x$ be $\mathit{oa}$ and $y$ be $\mathit{oo}$. Then,
since there is no critical vertex in $H_{s}$, $x$ must be a marked vertex of
$G_{s}$ such that $d(x)\in T(s)$. Since $(y,x)$ is an edge of $H_{s}$, we must
have that $y=d(x)$ in $G_{s}$. Thus, by Lemma A.18, $s$ can reach all vertices
of $H_{s}$ in $H_{s}\setminus{(y,x)}$, except $x$. This implies that $s$ is
reachable from all vertices of $H_{s}^{R}$ in $H_{s}^{R}\setminus{(x,y)}$,
except from $x$. By Lemma A.21, this implies that $s$ is reachable from all
vertices of $H_{ss}$ in $H_{ss}\setminus{(x,y)}$, except from $x$.
Furthermore, Lemma A.21 also implies that all vertices of $H_{ss}$ are
reachable from $s$ in $H_{ss}\setminus{(x,y)}$. Thus, the strongly connected
components of $H_{ss}\setminus{(x,y)}$ are $\\{x\\}$ and
$H_{ss}\setminus\\{x\\}$. $(1.4)$ Let $x$ and $y$ be both $\mathit{oa}$. This
implies that $(y,x)$ is an edge of $H_{s}$ both of whose endpoints are
auxiliary. But this is impossible to occur, since there is no critical vertex
in $H_{s}$.

$(2)$ Let $x$ be an ordinary vertex of $H_{ss}$ and let $y$ be an auxiliary
vertex of $H_{ss}$. Since $H_{ss}$ does not contain a critical vertex, this
means that $y$ is a marked vertex of $H_{s}^{R}$ and $x=d(y)$ in $H_{s}^{R}$.
Thus, $(y,x)$ is also an edge of $H_{s}$. Now we distinguish four different
cases, depending on whether $x$ and $y$ are ordinary or auxiliary in $H_{s}$.
$(2.1)$ Let $x$ be $\mathit{oo}$ and $y$ be $\mathit{ao}$. Then, by Lemma
A.17, $s$ can reach all vertices of $H_{s}$ in $H_{s}\setminus{(y,x)}$. This
implies that $s$ is reachable from all vertices of $H_{s}^{R}$ in
$H_{s}^{R}\setminus{(x,y)}$. By Lemma A.21, this implies that $s$ is reachable
from all vertices of $H_{ss}$ in $H_{ss}\setminus{(x,y)}$. Now, since $x=d(y)$
in $H_{s}^{R}$, by Lemma A.18 we have that $s$ can reach all vertices of
$H_{ss}$ in $H_{ss}\setminus{(x,y)}$, except $y$. Thus, the strongly connected
components of $H_{ss}\setminus{(x,y)}$ are $\\{y\\}$ and
$H_{ss}\setminus\\{y\\}$. $(2.2)$ Let $x$ be $\mathit{oo}$ and $y$ be
$\mathit{aa}$. Then we use precisely the same argument as in $(2.1)$ in order
to show that the strongly connected components of $H_{ss}\setminus{(x,y)}$ are
$\\{y\\}$ and $H_{ss}\setminus\\{y\\}$. $(2.3)$ Let $x$ be $\mathit{oa}$ and
$y$ be $\mathit{ao}$. This means that $y$ is an ordinary vertex of $H_{s}$ and
$x$ is an auxiliary vertex of $H_{s}$. Thus, $x$ is a marked vertex of
$G_{s}$, and $y=d(x)$ in $G_{s}$. By Lemma A.18, we have that $s$ can reach
all vertices of $H_{s}$ in $H_{s}\setminus{(y,x)}$, except $x$. This implies
that $s$ is reachable from all vertices of $H_{s}^{R}$ in
$H_{s}^{R}\setminus{(x,y)}$, except from $x$. By Lemma A.21, this implies that
$s$ is reachable from all vertices of $H_{ss}$ in $H_{ss}\setminus{(x,y)}$,
except from $x$. Now, since $x=d(y)$ in $H_{s}^{R}$, Lemma A.18 implies that
$s$ can reach all vertices of $H_{ss}$ in $H_{ss}\setminus{(x,y)}$, except
$y$. We conclude that the strongly connected components of
$H_{ss}\setminus{(x,y)}$ are $\\{x\\}$, $\\{y\\}$, and
$H_{ss}\setminus\\{x,y\\}$. $(2.4)$. Let $x$ be $\mathit{oa}$ nd $y$ be
$\mathit{aa}$. This implies that $(y,x)$ is an edge of $H_{s}$ both of whose
endpoints are auxiliary. But this is impossible to occur, since there is no
critical vertex in $H_{s}$.

$(3)$ Let $x$ be an auxiliary vertex of $H_{ss}$ and let $y$ be an ordinary
vertex of $H_{ss}$. Since $H_{ss}$ has no critical vertex, this means that $x$
is a marked vertex of $H_{s}^{R}$ with $d(x)\in T(s)$ in $H_{s}^{R}$. Now we
distinguish four different cases, depending on whether $x$ and $y$ are
ordinary or auxiliary in $H_{s}$. In any case, by Lemma A.17 we have that $s$
can reach every vertex of $H_{ss}$ in $H_{ss}\setminus{(x,y)}$. $(3.1)$ Let
$x$ be $\mathit{ao}$ and $y$ be $\mathit{oo}$. Let $(x_{0},y)$ be an edge of
$H_{s}^{R}$ that corresponds to $(x,y)$ in $H_{ss}$. Then $(y,x_{0})$ is an
edge of $H_{s}$. If $x_{0}$ is an ordinary vertex of $H_{s}$, then by Lemma
A.17 we have that $s$ reaches all vertices of $H_{s}$ in
$H_{s}\setminus{(y,x_{0})}$. This implies that every vertex of $H_{s}^{R}$ can
reach $s$ in $H_{s}^{R}\setminus{(x_{0},y)}$. Then Lemma A.19 implies that $x$
can reach $s$ in $H_{ss}\setminus{(x,y)}$. Thus, every vertex of $H_{ss}$ can
reach $s$ in $H_{ss}\setminus{(x,y)}$, and so we have that
$H_{ss}\setminus{(x,y)}$ is strongly connected. Similarly, if $x_{0}$ is an
auxiliary vertex of $H_{s}$, then, by Lemma A.18, we have that $s$ reaches all
vertices of $H_{s}$ in $H_{s}\setminus{(y,x_{0})}$, except $x_{0}$, which is
unreachable from $s$ in $H_{s}\setminus{(y,x_{0})}$. This implies that every
vertex of $H_{s}^{R}$ can reach $s$ in $H_{s}^{R}\setminus{(x_{0},y)}$, except
$x_{0}$, which cannot reach $s$ in $H_{s}^{R}\setminus{(x_{0},y)}$. Since $x$
is an ordinary vertex of $H_{s}$, we have that $x\neq x_{0}$, and so $x$ can
reach $s$ in $H_{s}^{R}\setminus{(x_{0},y)}$. Now Lemma A.19 implies that $x$
can reach $s$ in $H_{ss}\setminus{(x,y)}$. Thus, every vertex of $H_{ss}$ can
reach $s$ in $H_{ss}\setminus{(x,y)}$, and so we have that
$H_{ss}\setminus{(x,y)}$ is strongly connected. $(3.2)$ Let $x$ be
$\mathit{ao}$ and $y$ be $\mathit{oa}$. Now let
$\\{(x_{1},y),\dots,(x_{k},y)\\}$ be the set of all edges of $H_{s}^{R}$ that
correspond to $(x,y)$. Then $\\{(y,x_{1}),\dots,(y,x_{k})\\}$ is a set of
edges of $H_{s}$ that stem from $y$. Thus, by Lemma A.20 we have that $s$ can
reach all vertices of $H_{s}$ in
$H_{s}\setminus\\{(y,x_{1}),\dots,(y,x_{k})\\}$. This implies that $s$ can be
reached by all vertices of $H_{s}^{R}$ in
$H_{s}^{R}\setminus\\{(x_{1},y),\dots,(x_{k},y)\\}$. In particular, there is a
path $P$ from $x$ to $s$ in
$H_{s}^{R}\setminus\\{(x_{1},y),\dots,(x_{k},y)\\}$. Then, by Lemma A.6, the
corresponding path $P_{H}$ of $P$ in $H_{ss}$ goes from $x$ to $s$ and avoids
the edge $(x,y)$ of $H_{ss}$. This means that $s$ is reachable from $x$ in
$H_{ss}\setminus{(x,y)}$, and therefore every vertex of $H_{ss}$ reaches $s$
in $H_{ss}\setminus{(x,y)}$. Thus we have established that
$H_{ss}\setminus{(x,y)}$ is strongly connected. $(3.3)$ Let $x$ be
$\mathit{aa}$ and $y$ be $\mathit{oo}$. Let $(x_{0},y)$ be an edge of
$H_{s}^{R}$ that corresponds to $(x,y)$ in $H_{ss}$. Then $(y,x_{0})$ is an
edge of $H_{s}$. Now, if $x_{0}$ is ordinary in $H_{s}$ or it is auxiliary in
$H_{s}$ but $x_{0}\neq x$, then we can argue as in $(3.1)$ in order to
establish that $H_{ss}\setminus{(x,y)}$ is strongly connected. Otherwise,
suppose that $x_{0}=x$. Then, since $x$ is auxiliary in $H_{s}$ and $y$ is
ordinary in $H_{s}$ (and $H_{s}$ contains no marked vertex), we have that
$y=d(x)$ in $G_{s}$. Now, by Lemma A.18 we have that $s$ reaches all vertices
of $H_{s}$ in $H_{s}\setminus{(y,x)}$, except $x$, which is unreachable from
$s$ in $H_{s}\setminus{(y,x)}$. This implies that every vertex of $H_{s}^{R}$
can reach $s$ in $H_{s}^{R}\setminus{(x,y)}$, except $x$, which cannot reach
$s$ in $H_{s}^{R}\setminus{(x,y)}$. Now Lemma A.19 implies that every vertex
of $H_{ss}$ can reach $s$ in $H_{ss}\setminus{(x,y)}$, except $x$, which
cannot reach $s$ in $H_{ss}$. Thus, we have that the strongly connected
components of $H_{ss}\setminus{(x,y)}$ are $\\{x\\}$ and
$H_{ss}\setminus\\{x\\}$. Furthermore, since $(y,x)$ is the only incoming edge
to $x$ in $H_{s}$, we have that $(x,y)$ is the only outgoing edge from $x$ in
$H_{s}^{R}$. Therefore, since $y$ is ordinary in $H_{ss}$, we have that $x$
has no descendants in $D(H_{s}^{R})$. This means that $(x,y)$ is the only
outgoing edge of $x$ in $H_{ss}$. $(3.4)$ Let $x$ be $\mathit{aa}$ and $y$ be
$\mathit{oa}$. Then we can argue as in $(3.2)$ in order to conclude that
$H_{ss}\setminus{(x,y)}$ is strongly connected.

$(4)$ It is impossible that $x$ and $y$ are both auxiliary vertices of
$H_{ss}$, since $H_{ss}$ does not contain a critical vertex. ∎

######  Lemma A.23.

Let $G_{s}$ be a strongly connected digraph, and let $r$ be a marked vertex of
$G_{s}$. Let $(x,y)$ be a strong bridge of $H_{rr}$. Then the strongly
connected components of $H_{rr}\setminus{(x,y)}$ are given by one of the
following:

  1. (i)

$\\{x\\}$ and $H_{rr}\setminus\\{x\\}$, where $x$ is auxiliary in $H_{r}$ and
$y=d(x)$ in $G_{s}$ (see case $(1.3)$ below)

  2. (ii)

$\\{x\\}$, $\\{d(r)\\}$ and $H_{rr}\setminus\\{x,d(r)\\}$, where $x$ is
$\mathit{oa}$ in $H_{rr}$, $y$ is $\mathit{oo}$ in $H_{rr}$, $y=d(x)$ in
$G_{s}$, and $(d(r),x)$ is the only kind of outgoing edge of $d(r)$ in
$H_{rr}$ (see case $(1.3)$ below)

  3. (iii)

$\\{x\\}$ and $H_{rr}\setminus\\{x\\}$, where $x$ is auxiliary in $H_{rr}$ and
$(x,y)$ is the only outgoing edge of $x$ in $H_{rr}$ (see cases $(3.3)$ and
$(3.4)$ below)

  4. (iv)

$\\{y\\}$ and $H_{rr}\setminus\\{y\\}$, where $y$ is auxiliary in $H_{rr}$ and
$x=d(y)$ in $H_{r}^{R}$ (see the beginning of $(2)$, and cases $(2.1)$ and
$(2.2)$ below)

  5. (v)

$\\{x\\}$, $\\{y\\}$ and $H_{rr}\setminus\\{x,y\\}$, where $x$ is
$\mathit{oa}$ in $H_{rr}$, $y$ is $\mathit{ao}$ in $H_{rr}$, $x=d(y)$ in
$H_{r}^{R}$ and $y=d(x)$ in $G_{s}$ (see case $(2.3)$ below)

  6. (vi)

$\\{x\\}$, $\\{y\\}$, $\\{d(r)\\}$ and $H_{rr}\setminus\\{x,y,d(r)\\}$, where
$x$ is $\mathit{oa}$ in $H_{rr}$, $y$ is $\mathit{ao}$ in $H_{rr}$, $x=d(y)$
in $H_{r}^{R}$, $y=d(x)$ in $G_{s}$, and $(d(r),x)$ is the only kind of
outgoing edge of $d(r)$ in $H_{rr}$ (see case $(2.3)$ below)

###### Proof.

First notice that $d(r)$ is an auxiliary vertex of $H_{r}$ and has only one
outgoing edge $(d(r),r)$. Thus, vertex $d(r)$ in $H_{r}^{R}$ has only one
incoming edge $(r,d(r))$, and so this must be a bridge of $H_{r}^{R}$. This
means that $d(r)$ is an $\mathit{aa}$-vertex of $H_{rr}$. Now let $(x,y)$ be
an edge of $H_{rr}$. We distinguish four different cases, depending on whether
$x$ and $y$ are ordinary or auxiliary vertices of $H_{rr}$.

$(1)$ Let $x$ and $y$ be both ordinary vertices of $H_{rr}$. Here we
distinguish four different cases, depending on whether $x$ and $y$ are
ordinary or auxiliary in $H_{r}$. Notice that, in any case, $(y,x)$ is an edge
of $H_{r}$. $(1.1)$ Let $x$ and $y$ be both $\mathit{oo}$ in $H_{rr}$. By
Lemma A.17 we have that $r$ can reach all vertices of $H_{r}$ in
$H_{r}\setminus{(y,x)}$. Thus we infer that $r$ is reachable from all vertices
of $H_{r}^{R}$ in $H_{r}^{R}\setminus{(x,y)}$, and so Lemma A.21 implies that
$r$ is reachable from all vertices of $H_{rr}$ in $H_{rr}\setminus{(x,y)}$.
Now, since, $x$ and $y$ are both ordinary vertices of $H_{rr}$, by Lemma A.17
we have that $r$ reaches all vertices of $H_{rr}\setminus{(x,y)}$. We conclude
that $H_{rr}\setminus{(x,y)}$ is strongly connected. $(1.2)$ Let $x$ be
$\mathit{oo}$ and $y$ be $\mathit{oa}$. Then we can argue as in $(1.1)$ in
order to conclude that $H_{rr}\setminus{(x,y)}$ is strongly connected. $(1.3)$
Let $x$ be $\mathit{oa}$ and $y$ be $\mathit{oo}$. By Lemma A.18 we have that
$r$ can reach all vertices of $H_{r}$ in $H_{r}\setminus{(y,x)}$, except $x$,
which is unreachable from $r$ in $H_{r}\setminus{(y,x)}$, and possibly $d(r)$.
In any case, since $d(r)$ has only one outgoing edge $(d(r),r)$ in $H_{r}$, we
also have that $d(r)$ cannot reach $x$ in $H_{r}\setminus{(y,x)}$. This
implies that $r$ is reachable from all vertices of $H_{r}^{R}$ in
$H_{r}^{R}\setminus{(x,y)}$, except from $x$, and possibly $d(r)$; and that,
in any case, $x$ cannot reach $d(r)$ in $H_{r}^{R}\setminus{(x,y)}$. Now Lemma
A.21 implies that $r$ is reachable from all vertices of $H_{rr}$ in
$H_{rr}\setminus{(x,y)}$, except from $x$, and possibly $d(r)$, and that, in
any case, $x$ cannot reach $d(r)$ in $H_{rr}$. We conclude that there are two
possibilities: the strongly connected components of $H_{rr}\setminus{(x,y)}$
are either $\\{x\\}$ and $H_{rr}\setminus\\{x\\}$, or $\\{x\\}$, $\\{d(r)\\}$
and $H_{rr}\setminus\\{x,d(r)\\}$. $(1.4)$ Let $x$ and $y$ be both
$\mathit{oa}$. This implies that $(y,x)$ is an edge of $H_{s}$ both of whose
endpoints are auxiliary. But this is impossible to occur, since none of those
vertices is $d(r)$ (which is $\mathit{aa}$ in $H_{rr}$).

$(2)$ Let $x$ be ordinary in $H_{rr}$ and let $y$ be auxiliary in $H_{rr}$. If
$y=d(r)$, then $x$ must necessarily be $r$, since $d(r)$ has only one incoming
edge $(r,d(r))$ in $H_{r}^{R}$. So let us consider first the case that
$(x,y)=(r,d(r))$, which is the only case in which $d(r)$ can appear as an
endpoint of $(x,y)$ if $y$ is auxiliary in $H_{rr}$. By Corollary A.7, we have
that $H_{r}^{R}$ is strongly connected. Thus, even by removing the edge
$(r,d(r))$, we still have that $r$ is reachable from every vertex of
$H_{r}^{R}$. By Lemma A.21, this implies that every vertex of $H_{rr}$ is
reachable from $r$ in $H_{rr}\setminus{(r,d(r))}$. Now, by Lemma A.18 we have
that $r$ reaches every vertex of $H_{rr}\setminus{(r,d(r))}$, except $d(r)$,
which is unreachable from $r$ in $H_{rr}\setminus{(r,d(r))}$. Thus we conclude
that the strongly connected components of $H_{rr}\setminus{(r,d(r))}$ are
$\\{d(r)\\}$ and $H_{rr}\setminus\\{d(r)\\}$. Now, due to the preceding
argument, in what follows we can assume that none of $x$ and $y$ are $d(r)$.
This means that $y$ is a marked vertex of $H_{r}^{R}$ and $x=d(y)$ in
$H_{r}^{R}$. Thus, $(y,x)$ is an edge of $H_{r}$. Now we distinguish four
possibilities, depending on whether $x$ and $y$ are ordinary or auxiliary in
$H_{r}$. $(2.1)$ Let $x$ be $\mathit{oo}$ and $y$ be $\mathit{ao}$. Since $x$
and $y$ are ordinary vertices of $H_{r}$, and $(y,x)$ is an edge of $H_{r}$,
we can argue as in $(1.1)$ in order to show that $r$ is reachable from every
vertex of $H_{rr}$ in $H_{rr}\setminus{(x,y)}$. Now, by Lemma A.18 we have
that $r$ reaches every vertex of $H_{rr}$ in $H_{rr}\setminus{(x,y)}$, except
$y$, which is unreachable from $r$ in $H_{rr}\setminus{(x,y)}$. We conclude
that the strongly connected components of $H_{rr}\setminus{(x,y)}$ are
$\\{y\\}$ and $H_{rr}\setminus\\{y\\}$. $(2.2)$ Let $x$ be $\mathit{oo}$ and
$y$ be $\mathit{aa}$. Then we can argue as in $(2.1)$ in order to show that
the strongly connected components of $H_{rr}\setminus{(x,y)}$ are $\\{y\\}$
and $H_{rr}\setminus\\{y\\}$. $(2.3)$ Let $x$ be $\mathit{oa}$ and $y$ be
$\mathit{ao}$. This means that $y=d(x)$ in $H_{r}$, and so, by Lemma A.18, we
have that $r$ can reach every vertex of $H_{r}$ in $H_{r}\setminus{(y,x)}$,
except $x$, which is unreachable from $r$ in $H_{r}\setminus{(y,x)}$, and
possibly $d(r)$. In any case we have that $d(r)$ cannot reach $x$ in
$H_{r}\setminus{(y,x)}$, since there is only one outgoing edge $(d(r),r)$ of
$d(r)$ in $H_{r}$. Thus we have that $r$ is reachable from every vertex of
$H_{r}^{R}$ in $H_{r}^{R}\setminus{(x,y)}$, except from $x$, which cannot
reach $r$ in $H_{r}^{R}$, and possibly $d(r)$. In any case we have that $d(r)$
is not reachable from $x$ in $H_{r}^{R}\setminus{(x,y)}$. By Lemma A.21, this
implies that $r$ is reachable from every vertex of $H_{rr}$ in
$H_{rr}\setminus{(x,y)}$, except from $x$, which cannot reach $r$ in
$H_{r}^{R}$, and possibly $d(r)$. In any case we have that $d(r)$ is not
reachable from $x$ in $H_{rr}\setminus{(x,y)}$. Now, by Lemma A.18 we have
that $r$ can reach every vertex of $H_{rr}\setminus{(x,y)}$, except $y$, which
is unreachable from $r$ in $H_{rr}\setminus{(x,y)}$. Furthermore, no vertex of
$H_{rr}$ can reach $y$ in $H_{rr}\setminus{(x,y)}$, since $(x,y)$ is the only
incoming edge of $y$ in $H_{rr}$. We conclude that the strongly connected
components of $H_{rr}\setminus{(x,y)}$ are either $\\{x\\}$, $\\{y\\}$ and
$H_{rr}\setminus\\{x,y\\}$, or $\\{x\\}$, $\\{y\\}$, $\\{d(r)\\}$ and
$H_{rr}\setminus\\{x,y,d(r)\\}$. $(2.4)$ Let $x$ be $\mathit{oa}$ and let $y$
be $\mathit{aa}$. This means that both $x$ and $y$ are auxiliary vertices of
$H_{r}$, and so one of them must be $d(r)$. But we have forbidden this case to
occur, since it was treated in the beginning of $(2)$.

$(3)$ Let $x$ be an auxiliary vertex of $H_{rr}$ and let $y$ be an ordinary
vertex of $H_{rr}$. Since $H_{rr}$ has no critical vertex, this means that $x$
is a marked vertex of $H_{r}^{R}$ with $d(x)\in T(r)$ in $H_{r}^{R}$. Now we
distinguish four different cases, depending on whether $x$ and $y$ are
ordinary or auxiliary in $H_{r}$. In any case, by Lemma A.17 we have that $r$
can reach every vertex of $H_{rr}$ in $H_{rr}\setminus{(x,y)}$. $(3.1)$ Let
$x$ be $\mathit{ao}$ and $y$ be $\mathit{oo}$. Let $(x_{0},y)$ be an edge of
$H_{r}^{R}$ that corresponds to $(x,y)$ in $H_{rr}$. Then $(y,x_{0})$ is an
edge of $H_{r}$. If $x_{0}$ is an ordinary vertex of $H_{r}$, then by Lemma
A.17 we have that $r$ reaches all vertices of $H_{r}$ in
$H_{r}\setminus{(y,x_{0})}$. This implies that every vertex of $H_{r}^{R}$ can
reach $r$ in $H_{r}^{R}\setminus{(x_{0},y)}$. Then Lemma A.19 implies that $x$
can reach $r$ in $H_{rr}\setminus{(x,y)}$. Thus, every vertex of $H_{rr}$ can
reach $r$ in $H_{rr}\setminus{(x,y)}$, and so we have that
$H_{rr}\setminus{(x,y)}$ is strongly connected. Similarly, if $x_{0}$ is an
auxiliary vertex of $H_{r}$, then, by Lemma A.18, we have that $r$ reaches all
vertices of $H_{r}$ in $H_{r}\setminus{(y,x_{0})}$, except $x_{0}$, which is
unreachable from $r$ in $H_{r}\setminus{(y,x_{0})}$, and possibly $d(r)$. This
implies that every vertex of $H_{r}^{R}$ can reach $r$ in
$H_{r}^{R}\setminus{(x_{0},y)}$, except $x_{0}$, which cannot reach $r$ in
$H_{r}^{R}\setminus{(x_{0},y)}$, and possibly $d(r)$. Since $x$ is an ordinary
vertex of $H_{r}$, we have that $x\neq x_{0}$, and so $x$ can reach $r$ in
$H_{r}^{R}\setminus{(x_{0},y)}$. Now Lemma A.19 implies that $x$ can reach $r$
in $H_{rr}\setminus{(x,y)}$. Thus, every vertex of $H_{rr}$ can reach $r$ in
$H_{rr}\setminus{(x,y)}$, and so we have that $H_{rr}\setminus{(x,y)}$ is
strongly connected. $(3.2)$ Let $x$ be $\mathit{ao}$ and $y$ be $\mathit{oa}$.
Let $\\{(x_{1},y),\dots,(x_{k},y)\\}$ be the collection of all edges of
$H_{r}^{R}$ that correspond to $(x,y)$ in $H_{rr}$. Then
$\\{(y,x_{1}),\dots,(y,x_{k})\\}$ is a set of outgoing edges from $y$ in
$H_{r}$. Thus, Lemma A.20 implies that $r$ can reach all vertices of $H_{r}$
in $H_{r}\setminus\\{(y,x_{1}),\dots,(y,x_{k})\\}$, except possibly $d(r)$.
This implies that $r$ can be reached from all vertices of $H_{r}^{R}$ in
$H_{r}^{R}\setminus\\{(x_{1},y),\dots,(x_{k},y)\\}$, except possibly from
$d(r)$. In particular, there is a path $P$ from $x$ to $r$ in $H_{r}^{R}$ that
avoids all edges in $\\{(x_{1},y),\dots,(x_{k},y)\\}$. Then, by Lemma A.6 we
have that the corresponding path $P_{H}$ in $H_{rr}$ avoids $(x,y)$. This
means that $r$ is reachable from $x$ in $H_{rr}\setminus{(x,y)}$. Since
$H_{rr}$ is strongly connected (by Corollary A.7), we know that all vertices
of $H_{rr}$ can reach $r$. Thus they can reach $r$ by avoiding the edge
$(x,y)$. We conclude that $H_{rr}\setminus{(x,y)}$ is strongly connected.
$(3.3)$ Let $x$ be $\mathit{aa}$ and $y$ be $\mathit{oo}$. Let $(x_{0},y)$ be
an edge of $H_{r}^{R}$ that corresponds to $(x,y)$ in $H_{rr}$. Then
$(y,x_{0})$ is an edge of $H_{r}$. Now, if $x_{0}$ is ordinary in $H_{r}$ or
it is auxiliary in $H_{r}$ but $x_{0}\neq x$, then we can argue as in $(3.1)$
in order to establish that $H_{rr}\setminus{(x,y)}$ is strongly connected.
Otherwise, suppose that $x_{0}=x$. Then, since $x$ is auxiliary in $H_{r}$ and
$y$ is ordinary in $H_{r}$ (and $x\neq d(r)$), we have that $y=d(x)$ in
$G_{s}$. Now, by Lemma A.18 we have that $r$ reaches all vertices of $H_{r}$
in $H_{r}\setminus{(y,x)}$, except $x$, which is unreachable from $r$ in
$H_{r}\setminus{(y,x)}$, and possibly $d(r)$. This implies that every vertex
of $H_{r}^{R}$ can reach $r$ in $H_{r}^{R}\setminus{(x,y)}$, except $x$, which
cannot reach $r$ in $H_{r}^{R}\setminus{(x,y)}$, and possibly $d(r)$. Now
Lemma A.19 implies that every vertex of $H_{rr}$ can reach $r$ in
$H_{rr}\setminus{(x,y)}$, except $x$, which cannot reach $r$ in $H_{rr}$, and
possibly $d(r)$. But since $H_{r}$ is strongly connected (by Corollary A.7)
and there is no incoming edge $(x,d(r))$ to $d(r)$ in $H_{rr}$ (since $x$ and
$d(r)$ are both auxiliary, but not critical, vertices of $H_{rr}$), we also
have that $r$ reaches $d(r)$ in $H_{rr}\setminus{(x,y)}$. Thus we conclude
that the strongly connected components of $H_{rr}\setminus{(x,y)}$ are
$\\{x\\}$ and $H_{rr}\setminus\\{x\\}$. $(3.4)$ Let $x$ be $\mathit{aa}$ and
$y$ be $\mathit{oa}$. If $x\neq d(r)$, then we can argue as in $(3.2)$ in
order to conclude that $H_{rr}\setminus{(x,y)}$ is strongly connected.
Otherwise, let $x=d(r)$. Then, since $H_{rr}$ is strongly connected (by
Corollary A.7), we have that $r$ is reachable from every vertex of $H_{rr}$.
Since $d(r)$ has only one incoming edge $(r,d(r))$ in $H_{rr}$, this implies
that every vertex of $H_{rr}\setminus\\{d(r)\\}$ can reach $r$ by avoiding
$d(r)$. Thus, if $d(r)$ has more than one outgoing edges in $H_{rr}$, we have
that $H_{rr}\setminus{(x,y)}$ is strongly connected. Otherwise, the strongly
connected components of $H_{rr}\setminus{(x,y)}$ are $\\{d(r)\\}$ and
$H_{rr}\setminus\\{d(r)\\}$.

$(4)$ It is impossible that both $x$ and $y$ are auxiliary vertices of
$H_{rr}$, since $H_{rr}$ does not contain a critical vertex. ∎

We can simplify the result of Lemma A.23 by essentially eliminating cases
$(ii)$ and $(vi)$. This is done by observing that, in those cases, the only
outgoing edges from $d(r)$ have the form $(d(r),x)$, where $x$ is an
$\mathit{oa}$ vertex in $H_{rr}$. To achieve the simplification, we remove
$d(r)$ from $H_{rr}$, and we add a new edge $(r,x)$. This is in order to
replace the path $(r,d(r)),(d(r),x)$ of $H_{rr}$ with $(r,x)$. We call the
resulting graph $\widetilde{H}_{rr}$. The following two lemmas demonstrate
that $\widetilde{H}_{rr}$ maintains all the information that we need for our
purposes.

######  Lemma A.24.

For any two $\mathit{oo}$ vertices $u,v$ of $\widetilde{H}_{rr}$ we have
$u\stackrel{{\scriptstyle[}}{{]}}{\widetilde{H}_{\mathit{rr}}}\leftrightarrow_{2et}v$
if and only if
$u\stackrel{{\scriptstyle[}}{{]}}{H_{\mathit{rr}}}\leftrightarrow_{2et}v$.

###### Proof.

First observe that $x$ has only one outgoing edge in $H_{rr}$. This is because
$x$ is an auxiliary vertex of $H_{r}$, and thus (since $x\neq d(r)$) it has
only one incoming edge in $H_{r}$. This means that $x$ has only one outgoing
edge in $H_{r}^{R}$, and thus it has only one outgoing edge in $H_{rr}$, since
it is ordinary in $H_{rr}$.

Now let $u,v$ be two $\mathit{oo}$ vertices of $\widetilde{H}_{rr}$. Suppose
first that
$u\stackrel{{\scriptstyle[}}{{]}}{H_{\mathit{rr}}}\leftrightarrow_{2et}v$. Let
$e$ be an edge of $\widetilde{H}_{rr}$ different from $(r,x)$. Then $e$ is
also an edge of $H_{rr}$, and $u,v$ are twinless strongly connected in
$H_{rr}\setminus{e}$. This means that there is a path $P$ in
$H_{rr}\setminus{e}$ from $u$ to $v$, and a path $Q$ in $H_{rr}\setminus{e}$
from $v$ to $u$, such that there is no edge $(z,w)\in P$ with $(w,z)\in Q$.
Now, if $P$ and $Q$ do not pass from $d(r)$, then they are paths in
$\widetilde{H}_{rr}$, and this implies that $u,v$ are twinless strongly
connected in $\widetilde{H}_{rr}\setminus{e}$. Otherwise, at least one of
$P,Q$ has $(r,d(r)),(d(r),x)$ as a subpath. Then we replace every occurrence
of this subpath with $(r,x)$. If the outgoing edge of $x$ in
$\widetilde{H}_{rr}$ is not $(x,r)$, then we still have that $P$ and $Q$ do
not share a pair of antiparallel edges, and so $u,v$ are twinless strongly
connected in $\widetilde{H}_{rr}$. Otherwise, since $P$ and $Q$ must end in an
$\mathit{oo}$ vertex, for every occurrence of $d(r)$ in them they must pass
from the path $(r,d(r)),(d(r),x),(x,r)$. Then we can simply discard every
occurrence of this triangle. This shows that $u,v$ are twinless strongly
connected in $\widetilde{H}_{rr}\setminus{e}$. Now let $e=(r,x)$. Since
$u\stackrel{{\scriptstyle[}}{{]}}{H_{\mathit{rr}}}\leftrightarrow_{2et}v$, we
have that $u,v$ are twinless strongly connected in
$H_{rr}\setminus{(r,d(r))}$. This means that there is a path $P$ in
$H_{rr}\setminus{(r,d(r))}$ from $u$ to $v$, and a path $Q$ in
$H_{rr}\setminus{(r,d(r))}$ from $v$ to $u$, such that there is no edge
$(z,w)\in P$ with $(w,z)\in Q$. Since $(r,d(r))$ is the only incoming edge to
$d(r)$ in $H_{rr}$, this means that $P,Q$ do not pass from $d(r)$. Also, $P,Q$
do not use the edge $(r,x)$. This means that $u,v$ are twinless strongly
connected in $\widetilde{H}_{rr}\setminus{(r,x)}$. Thus we have
$u\stackrel{{\scriptstyle[}}{{]}}{\widetilde{H}_{\mathit{rr}}}\leftrightarrow_{2et}v$.

Conversely, suppose that $u,v$ are not $2$-edge twinless strongly connected in
$H_{rr}$. Then there is an edge $e\in H_{rr}$ and a pair of antiparallel edges
$(z,w),(w,z)\in H_{rr}$, such that for every path $P$ in $H_{rr}\setminus{e}$
from $u$ to $v$ and every path $Q$ in $H_{rr}\setminus{e}$ from $v$ to $u$, we
have $(z,w)\in P$ and $(w,z)\in Q$. Suppose first that $e$ is not one of
$(r,d(r)),(d(r),x)$. Now let us assume, for the sake of contradiction, that
there is a path $P$ in $\widetilde{H}_{rr}\setminus{e}$ from $u$ to $v$ that
does not contain $(z,w)$. Then we can construct a path $P^{\prime}$ in
$H_{rr}$ by replacing every occurrence of $(r,x)$ in $P$ with the segment
$(r,d(r)),(d(r),x)$. Observe that $(z,w)$ is neither $(r,d(r))$ nor
$(d(r),x)$, because $(w,z)$ is also an edge of $H_{rr}$ (and there cannot be
an edge $(d(r),r)$, because $(d(r),x)$ is the only outcoming edge of $d(r)$;
and also there cannot be an edge $(x,d(r))$, because $(r,d(r))$ is the only
incoming edge to $d(r)$ in $H_{rr}$, and $x\neq r$ because $x$ is auxiliary in
$H_{r}$ but $r$ is ordinary in $H_{r}$). Thus $P^{\prime}$ is a path in
$H_{rr}\setminus{e}$ from $u$ to $v$ that does not use $(z,w)$ \- a
contradiction. Similarly, we can show that there is no path $Q$ in
$\widetilde{H}_{rr}\setminus{e}$ from $v$ to $u$ that does not use $(w,z)$.
This means that $u,v$ are not twinless strongly connected in
$\widetilde{H}_{rr}\setminus{e}$. Now suppose that $e$ is either $(r,d(r))$ or
$(d(r),x)$. Then we can see that $u,v$ are not twinless strongly connected in
$\widetilde{H}_{rr}\setminus{(r,x)}$, because every path in
$\widetilde{H}_{rr}\setminus{(r,x)}$ from $u$ to $v$, or from $v$ to $u$, is
also a path in $H_{rr}\setminus{e}$. ∎

######  Lemma A.25.

Let $e$ be an edge of $\widetilde{H}_{rr}$. Then $e$ is a strong bridge of
$\widetilde{H}_{rr}$ if and only if it is a strong bridge of $H_{rr}$. The
strongly connected components of $\widetilde{H}_{rr}\setminus{e}$ are given
essentially by Lemma A.23 (where we replace “$H_{rr}$” with
“$\widetilde{H}_{rr}$”).

###### Proof.

First observe that $(r,x)$ is not a strong bridge of $\widetilde{H}_{rr}$,
because $x$ is an ordinary vertex of $H_{rr}$, and so, by removing any edge
from $H_{rr}$, $r$ can still reach $x$ in $H_{rr}$. In particular, by removing
$(r,d(r))$ or $(d(r),x)$ from $H_{rr}$, $r$ can still reach $x$. From this we
can conclude that $(r,x)$ is not a strong bridge of $\widetilde{H}_{rr}$.

Now let $e$ be an edge of $\widetilde{H}_{rr}$, but not $(r,x)$. Then $e$ is
also an edge of $H_{rr}$. Let $u,v$ be two vertices of $\widetilde{H}_{rr}$.
We will show that $u$ can reach $v$ in $\widetilde{H}_{rr}\setminus{e}$ if and
only if $u$ can reach $v$ in $H_{rr}\setminus{e}$. Let $P$ be a path in
$\widetilde{H}_{rr}\setminus{e}$ from $u$ to $v$. We can construct a path in
$H_{rr}\setminus{e}$ by replacing every occurrence of $(r,x)$ in $P$ with the
segment $(r,d(r)),(d(r),x)$. This shows that $u$ can reach $v$ in
$H_{rr}\setminus{e}$. Conversely, let $P$ be a path in $H_{rr}\setminus{e}$
from $u$ to $v$. If $P$ passes from $d(r)$, then it must necessarily use the
segment $(r,d(r)),(d(r),x))$ (because $(r,d(r))$ is the only incoming edge to
$d(r)$ in $H_{rr}$, and $(d(r),x)$ is the only king of outgoing edge from
$d(r)$ in $H_{rr}$). Then we can construct a path in
$\widetilde{H}_{rr}\setminus{r}$ by replacing every occurrence of the segment
$(r,d(r)),(d(r),x))$ with $(r,x)$. This shows that $u$ can reach $v$ in
$\widetilde{H}_{rr}\setminus{e}$. Thus we have that the strongly connected
components of $\widetilde{H}_{rr}\setminus{e}$ coincide with those of
$H_{rr}\setminus{e}$ (by excluding $d(r)$ from the strongly connected
component of $H_{rr}\setminus{e}$ that contains $d(r)$). ∎

Before we move on to describe the structure of the strongly connected
components of the remaining graphs, we will need the following two lemmas.

######  Lemma A.26.

Let $G_{s}$ be a strongly connected digraph and let $r$ be a marked vertex of
$G_{s}$. Let $(x,y)$ be an edge of $H_{r}$ such that either both $x$ and $y$
are ordinary in $H_{r}$, or $y$ is auxiliary in $H_{r}$ and $x=d(y)$ in
$G_{s}$. Then a vertex $u$ of $H_{r}$ reaches $s$ in $G_{s}\setminus{(x,y)}$
if and only if $u$ reaches $d(r)$ in $H_{r}\setminus{(x,y)}$.

###### Proof.

$(\Rightarrow)$ Let $P$ be a path from $u$ to $s$ in $G_{s}\setminus{(x,y)}$.
Since $r$ is a marked vertex of $G_{s}$, by Lemma A.5 we have that there is a
path $Q$ from $s$ to $d(r)$ that avoids every vertex of $D(r)$. In particular,
$Q$ does not use the edge $(x,y)$. Let $P^{\prime}=P+Q$ be the concatenation
of $P$ and $Q$ in $G_{s}$. This is a path from $u$ to $d(r)$ in
$G_{s}\setminus{(x,y)}$. Now consider the corresponding path $P_{H}$ of
$P^{\prime}$ in $H_{r}$. By Lemma A.6, this is a path from $u$ to $d(r)$ in
$H_{r}$ that avoids $(x,y)$.
$(\Leftarrow)$ Let $\tilde{P}$ be a path from $u$ to $d(r)$ in
$H_{r}\setminus{(x,y)}$. Then, by Lemma A.6, there is a path $P$ from $u$ to
$d(r)$ in $G_{s}$ with $P_{H}=\tilde{P}$. This implies that $P$ avoids the
edge $(x,y)$. Now, by Lemma A.5, there is a path $Q$ from $d(r)$ to $s$ that
avoids any vertex from $D(r)$. In particular, $Q$ does not use the edge
$(x,y)$. Thus we have that the concatenation $P+Q$ is a path from $u$ to $s$
in $G_{s}$ that avoids $(x,y)$. ∎

The following is a combination of Lemma A.19 and Lemma A.26.

######  Lemma A.27.

Let $G_{s}$ be a strongly connected digraph and let $r$ be a marked vertex of
$G_{s}$. Let $x$ be a marked vertex of $G_{s}$ such that $d(x)\in T(r)$. Let
also $(x_{0},y)$ be an edge of $G_{s}$ such that $x_{0}$ is a descendant of
$x$ in $D(G_{s})$, $y$ is not a descendant of $x$ in $D(G_{s})$, and $y\in
T(r)$. Let $u$ be a vertex of $H_{r}$. Then $u$ reaches $s$ in
$G_{s}\setminus{(x_{0},y)}$ if and only if $u$ reaches $d(r)$ in
$H_{r}\setminus{(x,y)}$.

###### Proof.

$(\Rightarrow)$ Let $u$ be a vertex of $H_{r}$ and let $P$ be a path from $u$
to $s$ in $G_{s}\setminus{(x_{0},y)}$. Since $r$ is a marked vertex of
$G_{s}$, by Lemma A.5 we have that there is a path $Q$ from $s$ to $d(r)$ that
avoids every vertex of $D(r)$. In particular, $Q$ does not use the edge
$(x_{0},y)$. Let $P^{\prime}=P+Q$ be the concatenation of $P$ and $Q$ in
$G_{s}$. This is a path from $u$ to $d(r)$ in $G_{s}\setminus{(x,y)}$. Now
consider the corresponding path $P_{H}$ of $P^{\prime}$ in $H_{r}$. $P_{H}$
has the same endpoints as $P^{\prime}$. Thus, if $P_{H}$ avoids the edge
$(x,y)$ of $H_{r}$, then we are done. Otherwise, this means that $P^{\prime}$
uses an edge $(x_{1},y)$ of $G_{s}$, distinct from $(x_{0},y)$ (although we
may have $x_{1}=x_{0}$, since we allow multiple edges), such that $x_{1}$ is a
descendant of $x$ in $D(G_{s})$. But then we must have that $(x,y)$ is a
double edge of $H_{r}$, and therefore $H_{r}\setminus{(x,y)}$ is strongly
connected (since $H_{r}$ is strongly connected, by Corollary A.7). Thus $u$
can reach $s$ in $H_{r}\setminus{(x,y)}$.
$(\Leftarrow)$ Let $u$ be a vertex of $H_{r}$ that cannot reach $d(r)$ in
$H_{r}\setminus{(x,y)}$. Let us assume, for the sake of contradiction, that
$u$ reaches $s$ in $G_{s}\setminus{(x_{0},y)}$. This means that there is a
path $P$ in $G_{s}\setminus{(x_{0},y)}$ that starts from $u$ and ends in $s$.
Then we can argue as in the previous direction, in order to establish the
existence of a path $P^{\prime}$ in $G_{s}\setminus{(x_{0},y)}$ that starts
from $u$ and ends in $d(r)$. Now consider the corresponding path $P_{H}$ of
$P^{\prime}$ in $H_{r}$. Then $P_{H}$ has the same endpoints as $P^{\prime}$,
and so it must necessarily use the edge $(x,y)$ of $H_{r}$. But the existence
of this edge in $P_{H}$ implies that there is an edge $(x_{1},y)$ in $G_{s}$,
distinct from $(x_{0},y)$ (although we may have $x_{1}=x_{0}$, since we allow
multiple edges), such that $x_{1}$ is a descendant of $x$ in $D(G_{s})$. But
then we must have that $(x,y)$ is a double edge of $H_{r}$, and therefore
$H_{r}\setminus{(x,y)}$ is strongly connected (since $H_{r}$ is strongly
connected, by Corollary A.7). This contradicts the fact that $d(r)$ is
unreachable from $u$ in $H_{r}\setminus{(x,y)}$. ∎

######  Lemma A.28.

Let $G_{s}$ be a strongly connected digraph, and let $r$ be a marked vertex of
$H_{s}^{R}$. Let $(x,y)$ be a strong bridge of $H_{sr}$ where none of $x$ and
$y$ is $d(r)$ in $H_{s}^{R}$. Then the strongly connected components of
$H_{sr}\setminus{(x,y)}$ are given by one of the following:

  1. (i)

$\\{x\\}$ and $H_{sr}\setminus\\{x\\}$, where $x$ is auxiliary in $H_{s}$ and
$y=d(x)$ in $G_{s}$ (see case $(1.3)$ below)

  2. (ii)

$\\{x\\}$ and $H_{sr}\setminus\\{x\\}$, where $x$ is auxiliary in $H_{sr}$ and
$(x,y)$ is the only outgoing edge of $x$ in $H_{sr}$ (see case $(3.3)$ below)

  3. (iii)

$\\{y\\}$ and $H_{sr}\setminus\\{y\\}$, where $y$ is auxiliary in $H_{sr}$ and
$x=d(y)$ in $H_{s}^{R}$ (see cases $(2.1)$ and $(2.2)$ below)

  4. (iv)

$\\{x\\}$, $\\{y\\}$ and $H_{sr}\setminus\\{x,y\\}$, where $x$ is auxiliary in
$H_{s}$, $y$ is auxiliary in $H_{sr}$, $x=d(y)$ in $H_{s}^{R}$ and $y=d(x)$ in
$G_{s}$ (see case $(2.3)$ below)

###### Proof.

Let $(x,y)$ be an edge of $H_{sr}$, where none of $x$ and $y$ is $d(r)$ in
$H_{s}^{R}$. We distinguish four different cases, depending on whether $x$ and
$y$ are ordinary or auxiliary vertices of $H_{sr}$.

$(1)$ Let both $x$ and $y$ be ordinary vertices of $H_{sr}$. This implies that
$(y,x)$ is an edge in $H_{s}$. Here we distinguish four cases, depending on
whether $x$ and $y$ are ordinary or auxiliary in $H_{s}$. $(1.1)$ Let $x$ be
$\mathit{oo}$ and $y$ be $\mathit{oo}$. Then, by Lemma A.17 we have that $s$
can reach all vertices of $H_{s}$ in $H_{s}\setminus{(y,x)}$. This implies
that $s$ can be reached by all vertices of $H_{s}^{R}$ in
$H_{s}^{R}\setminus{(x,y)}$. Then Lemma A.26 implies that all vertices of
$H_{sr}$ can reach $d(r)$ in $H_{sr}\setminus{(x,y)}$. Conversely, as an
implication of Lemma A.17, we have that $d(r)$ can reach every vertex of
$H_{rs}$ in $H_{sr}\setminus{(x,y)}$. We conclude that
$H_{sr}\setminus{(x,y)}$ is strongly connected. $(1.2)$ Let $x$ be
$\mathit{oo}$ and $y$ be $\mathit{oa}$. Then we can argue as in $(1.1)$ in
order to conclude that $H_{sr}\setminus{(x,y)}$ is strongly connected. $(1.3)$
Let $x$ be $\mathit{oa}$ and $y$ be $\mathit{oo}$. Since $H_{s}$ contains no
critical vertex, we have that $x$ is a marked vertex of $G_{s}$ and $y=d(x)$
in $G_{s}$. Then, by Lemma A.18 we have that $s$ can reach all vertices of
$H_{s}$ in $H_{s}\setminus{(y,x)}$, except $x$, which is unreachable from $s$
in $H_{s}\setminus{(y,x)}$. This implies that $s$ is reachable from all
vertices of $H_{s}^{R}$ in $H_{s}^{R}\setminus{(x,y)}$, except from $x$, which
cannot reach $s$ in $H_{s}^{R}\setminus{(x,y)}$. Then Lemma A.26 implies that
all vertices of $H_{sr}$ can reach $d(r)$ in $H_{sr}\setminus{(x,y)}$, except
$x$, which cannot reach $d(r)$ in $H_{sr}\setminus{(x,y)}$. Now, as an
implication of Lemma A.17, we have that $d(r)$ can reach all vertices of
$H_{sr}$ in $H_{sr}\setminus{(x,y)}$. We conclude that the strongly connected
components of $H_{sr}\setminus{(x,y)}$ are $\\{x\\}$ and
$H_{sr}\setminus\\{x\\}$. $(1.4)$ Let $x$ be $\mathit{oa}$ and $y$ be
$\mathit{oa}$. But this implies that both $x$ and $y$ are auxiliary vertices
of $H_{s}$, which is impossible to occur.

$(2)$ Let $x$ be an ordinary vertex of $H_{sr}$ and let $y$ be an auxiliary
vertex of $H_{sr}$. Since $y\neq d(r)$ in $H_{s}^{R}$, this means that $y$ is
a marked vertex of $H_{s}^{R}$ and $x=d(y)$ in $H_{s}^{R}$. Thus $(y,x)$ is an
edge of $H_{s}$. Now we distinguish four different cases, depending on whether
$x$ and $y$ are ordinary or auxiliary in $H_{s}$. $(2.1)$ Let $x$ be
$\mathit{oo}$ and $y$ be $\mathit{ao}$. Then we can argue as in $(1.1)$ in
order to show that $d(r)$ is reachable from every vertex of $H_{sr}$ in
$H_{sr}\setminus{(x,y)}$. Now, as an implication of Lemma A.18, we have that
$d(r)$ reaches every vertex of $H_{sr}$ in $H_{sr}\setminus{(x,y)}$, except
$y$, which is unreachable from $d(r)$ in $H_{sr}\setminus{(x,y)}$. Thus we
conclude that the strongly connected components of $H_{sr}\setminus{(x,y)}$
are $\\{y\\}$ and $H_{sr}\setminus\\{y\\}$. $(2.2)$ Let $x$ be $\mathit{oo}$
and $y$ be $\mathit{aa}$. Then we can argue as in $(2.1)$ in order to conclude
that the strongly connected components of $H_{sr}\setminus{(x,y)}$ are
$\\{y\\}$ and $H_{sr}\setminus\\{y\\}$. $(2.3)$. Let $x$ be $\mathit{oa}$ and
$y$ be $\mathit{ao}$. Then, by Lemma A.18 we have that $s$ can reach all
vertices of $H_{s}$ in $H_{s}\setminus{(y,x)}$, except $x$, which is
unreachable from $s$ in $H_{s}\setminus{(y,x)}$. This implies that $s$ can be
reached by all vertices of $H_{s}^{R}$ in $H_{s}^{R}\setminus{(x,y)}$, except
from $x$, which cannot reach $s$ in $H_{s}^{R}\setminus{(x,y)}$. By Lemma
A.26, this implies that $d(r)$ is reachable from all vertices of $H_{sr}$ in
$H_{sr}\setminus{(x,y)}$, except from $x$, which cannot reach $d(r)$ in
$H_{sr}\setminus{(x,y)}$. Now, as an implication of Lemma A.18 we have that
$d(r)$ can reach all vertices of $H_{sr}$ in $H_{sr}\setminus{(x,y)}$, except
$y$, which is unreachable from $d(r)$ in $H_{sr}\setminus{(x,y)}$. We conclude
that the strongly connected components of $H_{sr}\setminus{(x,y)}$ are
$\\{x\\}$, $\\{y\\}$ and $H_{sr}\setminus\\{x,y\\}$. $(2.4)$ Let $x$ be
$\mathit{oa}$ and $y$ be $\mathit{aa}$. But this implies that both $x$ and $y$
are auxiliary vertices of $H_{s}$, which is impossible to occur.

$(3)$ Let $x$ be an auxiliary vertex of $H_{sr}$ and let $y$ be an ordinary
vertex of $H_{sr}$. Since $x\neq d(r)$ in $H_{s}^{R}$, this means that $x$ is
a marked vertex of $H_{s}^{R}$ with $d(x)\in T(r)$ in $H_{s}^{R}$. Now we
distinguish four different cases, depending on whether $x$ and $y$ are
ordinary or auxiliary in $H_{s}$. In any case, as an implication of Lemma A.17
we have that $d(r)$ can reach every vertex of $H_{sr}$ in
$H_{sr}\setminus{(x,y)}$. $(3.1)$ Let $x$ be $\mathit{ao}$ and $y$ be
$\mathit{oo}$. Let $(x_{0},y)$ be an edge of $H_{s}^{R}$ that corresponds to
$(x,y)$ in $H_{sr}$. Then $(y,x_{0})$ is an edge of $H_{s}$. If $x_{0}$ is an
ordinary vertex of $H_{s}$, then by Lemma A.17 we have that $s$ reaches all
vertices of $H_{s}$ in $H_{s}\setminus{(y,x_{0})}$. This implies that every
vertex of $H_{s}^{R}$ can reach $s$ in $H_{s}^{R}\setminus{(x_{0},y)}$. Then
Lemma A.27 implies that every vertex of $H_{sr}$ can reach $d(r)$ in
$H_{sr}\setminus{(x,y)}$, and so we have that $H_{sr}\setminus{(x,y)}$ is
strongly connected. Similarly, if $x_{0}$ is an auxiliary vertex of $H_{s}$,
then, by Lemma A.18, we have that $s$ reaches all vertices of $H_{s}$ in
$H_{s}\setminus{(y,x_{0})}$, except $x_{0}$, which is unreachable from $s$ in
$H_{s}\setminus{(y,x_{0})}$. This implies that every vertex of $H_{s}^{R}$ can
reach $s$ in $H_{s}^{R}\setminus{(x_{0},y)}$, except $x_{0}$, which cannot
reach $s$ in $H_{s}^{R}\setminus{(x_{0},y)}$. Since $x$ is an ordinary vertex
of $H_{s}$, we have that $x\neq x_{0}$, and so $x$ can reach $s$ in
$H_{s}^{R}\setminus{(x_{0},y)}$. Then Lemma A.27 implies that every vertex of
$H_{sr}$ can reach $d(r)$ in $H_{sr}\setminus{(x,y)}$, and so we have that
$H_{sr}\setminus{(x,y)}$ is strongly connected. $(3.2)$ Let $x$ be
$\mathit{ao}$ and $y$ be $\mathit{oa}$. Let $\\{(x_{1},y),\dots,(x_{k},y)\\}$
be the set of all the incoming edges to $y$ in $H_{s}^{R}$. Then
$\\{(y,x_{1}),\dots,(y,x_{k})\\}$ is a collection of edges of $H_{s}$ that
stem from $y$. Since $H_{s}$ contains no critical vertex, we have that $y$ is
a marked vertex of $G_{s}$ with $d(y)\in T(s)$. By Lemma A.20 we have that $s$
can reach all vertices of $H_{s}$ in
$H_{s}\setminus\\{(y,x_{1}),\dots,(y,x_{k})\\}$. This implies that $s$ can be
reached from all vertices of $H_{s}^{R}$ in
$H_{s}^{R}\setminus\\{(x_{1},y),\dots,(x_{k},y)\\}$. Furthermore, since $y$ is
dominated by $d(r)$ in $H_{s}^{R}$, we have that there is a path from $s$ to
$d(r)$ in $H_{s}^{R}$ that avoids $y$; therefore, this path also avoids all
edges $\\{(x_{1},y),\dots,(x_{k},y)\\}$. Thus we infer that $d(r)$ is
reachable from all vertices of $H_{s}^{R}$ in
$H_{s}^{R}\setminus\\{(x_{1},y),\dots,(x_{k},y)\\}$. In particular, let $P$ be
a path from $x$ to $d(r)$ in
$H_{s}^{R}\setminus\\{(x_{1},y),\dots,(x_{k},y)\\}$. Then, by Lemma A.6 the
corresponding path $P_{H}$ in $H_{sr}$ has the same endpoints as $P$ and
avoids the edge $(x,y)$. Thus, even by removing $(x,y)$ from $H_{sr}$, all
vertices from $H_{sr}$ can reach $d(r)$. We conclude that
$H_{sr}\setminus{(x,y)}$ is strongly connected. $(3.3)$ Let $x$ be
$\mathit{aa}$ and $y$ be $\mathit{oo}$. Let $(x_{0},y)$ be an edge of
$H_{s}^{R}$ that corresponds to $(x,y)$ in $H_{sr}$. Then $(y,x_{0})$ is an
edge of $H_{s}$. Now, if $x_{0}$ is ordinary in $H_{s}$ or it is auxiliary in
$H_{s}$ but $x_{0}\neq x$, then we can argue as in $(3.1)$ in order to
establish that $H_{sr}\setminus{(x,y)}$ is strongly connected. Otherwise,
suppose that $x_{0}=x$. Then, since $x$ is auxiliary in $H_{s}$ and $y$ is
ordinary in $H_{s}$ (and $H_{s}$ contains no marked vertex), we have that
$y=d(x)$ in $G_{s}$. Now, by Lemma A.18 we have that $s$ reaches all vertices
of $H_{s}$ in $H_{s}\setminus{(y,x)}$, except $x$, which is unreachable from
$s$ in $H_{s}\setminus{(y,x)}$. This implies that every vertex of $H_{s}^{R}$
can reach $s$ in $H_{s}^{R}\setminus{(x,y)}$, except $x$, which cannot reach
$s$ in $H_{s}^{R}\setminus{(x,y)}$. Now Lemma A.27 implies that every vertex
of $H_{sr}$ can reach $d(r)$ in $H_{sr}\setminus{(x,y)}$, except $x$, which
cannot reach $d(r)$ in $H_{sr}$. Thus, we have that the strongly connected
components of $H_{sr}\setminus{(x,y)}$ are $\\{x\\}$ and
$H_{sr}\setminus\\{x\\}$. $(3.4)$ Let $x$ be $\mathit{aa}$ and $y$ be
$\mathit{oa}$. Then we can use the same argument that we used in $(3.2)$ in
order to conclude that $H_{sr}\setminus{(x,y)}$ is strongly connected.

$(4)$ Since $y\neq d(r)$ in $H_{s}^{R}$, it is impossible that both $x$ and
$y$ are auxiliary in $H_{sr}$. ∎

######  Lemma A.29.

Let $G_{s}$ be a strongly connected digraph, let $r$ be a marked vertex of
$G_{s}$, and let $r^{\prime}$ be a marked vertex of $H_{r}^{R}$. Let $(x,y)$
be a strong bridge of $H_{rr^{\prime}}$ such that neither $x$ nor $y$ is
$d(r^{\prime})$ in $H_{r}^{R}$. Furthermore, if $r^{\prime}=d(r)$ in $G_{s}$,
then we also demand that neither $x$ nor $y$ is $r^{\prime}$. Then the
strongly connected components of $H_{rr^{\prime}}\setminus{(x,y)}$ are given
by one of the following:

  1. (i)

$\\{x\\}$ and $H_{rr^{\prime}}\setminus\\{x\\}$, where $x$ is auxiliary in
$H_{r}$ and $y=d(x)$ in $G_{s}$ (see case $(1.3)$ below)

  2. (ii)

$\\{x\\}$ and $H_{rr^{\prime}}\setminus\\{x\\}$, where $x$ is auxiliary in
$H_{rr^{\prime}}$ and $(x,y)$ is the only outgoing edge of $x$ in
$H_{rr^{\prime}}$ (see case $(3.3)$ below)

  3. (iii)

$\\{y\\}$ and $H_{rr^{\prime}}\setminus\\{y\\}$, where $y$ is auxiliary in
$H_{rr^{\prime}}$ and $x=d(y)$ in $H_{r}^{R}$ (see cases $(2.1)$ and $(2.2)$
below)

  4. (iv)

$\\{x\\}$, $\\{y\\}$ and $H_{rr^{\prime}}\setminus\\{x,y\\}$, where $x$ is
auxiliary in $H_{r}$, $y$ is auxiliary in $H_{rr^{\prime}}$, $x=d(y)$ in
$H_{r}^{R}$ and $y=d(x)$ in $G_{s}$ (see case $(2.3)$ below)

  5. (v)

$\\{x\\}$, $\\{y\\}$, $\\{d(r)\\}$ and $\\{r\\}$, where $r^{\prime}=d(r)$, $x$
is auxiliary in $H_{r}$, $y$ is auxiliary in $H_{rr^{\prime}}$, $x=d(y)$ in
$H_{r}^{R}$, $y=d(x)$ in $G_{s}$, and $(d(r),x)$ is the only kind of outgoing
edge of $d(r)$ in $H_{rr^{\prime}}$ (see case $(2.3)$ below)

###### Proof.

Let $(x,y)$ be an edge of $H_{rr^{\prime}}$ such that neither $x$ nor $y$ is
$d(r^{\prime})$ in $H_{r}^{R}$, and also, if $r^{\prime}=d(r)$ in $G_{s}$,
then neither $x$ nor $y$ is $r^{\prime}$. Notice that, if $r^{\prime}=d(r)$ in
$G_{s}$, then $r^{\prime}$ is auxiliary in $H_{r}$, and therefore $r^{\prime}$
is an $\mathit{oa}$-vertex of $H_{rr^{\prime}}$. Conversely, $d(r)$ appears as
an ordinary vertex in $H_{rr^{\prime}}$ only when $r^{\prime}=d(r)$.
Therefore, if $x$ or $y$ is ordinary in $H_{rr^{\prime}}$, then we can
immediately infer, due to our demand in the statement of the Lemma, that $x$
or $y$, respectively, is not $d(r)$. Now we distinguish four cases, depending
on whether $x$ and $y$ are ordinary or auxiliary in $H_{rr^{\prime}}$.

$(1)$ Let both $x$ and $y$ be ordinary vertices of $H_{rr^{\prime}}$. This
implies that $(x,y)$ is also an edge of $H_{r}^{R}$, and therefore $(y,x)$ is
an edge of $H_{r}$. Now we distinguish four cases, depending on whether $x$
and $y$ are ordinary or auxiliary in $H_{r}$. Notice that, in any case, as an
implication of Lemma A.17, we have that $d(r^{\prime})$ reaches all vertices
of $H_{rr^{\prime}}$ in $H_{rr^{\prime}}\setminus{(x,y)}$. $(1.1)$ Let $x$ be
$\mathit{oo}$ and $y$ be $\mathit{oo}$. Then, as an implication of Lemma A.17,
we have that $d(r)$ reaches all vertices of $H_{r}$ in
$H_{r}\setminus{(y,x)}$. This implies that all vertices of $H_{r}^{R}$ can
reach $d(r)$ in $H_{r}^{R}\setminus{(x,y)}$. By Lemma A.26, this implies that
all vertices of $H_{rr^{\prime}}$ can reach $d(r^{\prime})$ in
$H_{rr^{\prime}}$ in $H_{rr^{\prime}}\setminus{(x,y)}$. We conclude that
$H_{rr^{\prime}}\setminus{(x,y)}$ is strongly connected. $(1.2)$ Let $x$ be
$\mathit{oo}$ and $y$ be $\mathit{oa}$. Then we can argue as in $(1.1)$ in
order to conclude that $H_{rr^{\prime}}\setminus{(x,y)}$ is strongly
connected. $(1.3)$ Let $x$ be $\mathit{oa}$ and $y$ be $\mathit{oo}$. Since
$x\neq d(r)$, we must have that $x$ is a marked vertex of $G_{s}$ and $y=d(x)$
in $G_{s}$. Then, by Lemma A.18, we have that $r$ can reach every vertex of
$H_{r}$ in $H_{r}\setminus{(y,x)}$, except $x$, which is unreachable from $r$
in $H_{r}\setminus{(y,x)}$, and possibly $d(r)$. This implies that $r$ is
reachable from every vertex of $H_{r}^{R}$ in $H_{r}^{R}\setminus{(x,y)}$,
except from $x$, which cannot reach $r$ in $H_{r}^{R}\setminus{(x,y)}$, and
possibly $d(r)$. Now let us assume, for the sake of contradiction, that $d(r)$
cannot reach $r$ in $H_{r}^{R}\setminus{(x,y)}$, and also that $d(r)\in
H_{rr^{\prime}}$. Since $r$ is reachable from every vertex of
$H_{r}^{R}\setminus\\{x,d(r)\\}$ in $H_{r}^{R}\setminus{(x,y)}$, we must have
that $(d(r),x)$ is the only kind of outgoing edge of $d(r)$ in $H_{r}^{R}$.
Now, since $x\in H_{rr^{\prime}}$ and the immediate dominator of $d(r)$ in
$H_{r}^{R}$ is $r$, we have that $x$ is dominated by $d(r)$ in $H_{r}^{R}$;
and since $(d(r),x)$ is an edge of $H_{r}^{R}$, we must have that $d(r)$ is
the immediate dominator of $x$ in $H_{r}^{R}$. Now, since $y\in
H_{rr^{\prime}}$, we must also have that $y$ is dominated by $d(r)$ in
$H_{r}^{R}$. And then, since $(d(r),x)$ is the only kind of outgoing edge of
$d(r)$ in $H_{r}^{R}$, and $(x,y)$ is the only outgoing edge of $x$ in
$H_{r}^{R}$ (since $x$ is marked in $G_{s}$ and $y=d(x)$ in $G_{s}$), we must
have that $(x,y)$ is a bridge of $H_{r}^{R}$, and so $y$ is a marked vertex of
$H_{r}^{R}$ and $x$ is the immediate dominator of $y$ in $H_{r}^{R}$. Since
$y$ is a marked vertex of $H_{r}^{R}$, but also $y$ is ordinary in
$H_{rr^{\prime}}$, we must have that $r^{\prime}=y$. But then $x$ is the
critical vertex of $r^{\prime}$ in $H_{rr^{\prime}}$ \- which contradicts the
fact that $x$ is ordinary in $H_{rr^{\prime}}$. Thus we have that either
$d(r)$ can reach $r$ in $H_{r}^{R}\setminus{(x,y)}$, or that $d(r)\notin
H_{rr^{\prime}}$. In any case, since $r$ is reachable from every vertex of
$H_{r}^{R}$ in $H_{r}^{R}\setminus{(x,y)}$, except from $x$, which cannot
reach $r$ in $H_{r}^{R}\setminus{(x,y)}$, by Lemma A.26 we must have that
$d(r^{\prime})$ is reachable from every vertex of $H_{rr^{\prime}}$ in
$H_{rr^{\prime}}\setminus{(x,y)}$, except from $x$, which cannot reach
$d(r^{\prime})$ in $H_{rr^{\prime}}\setminus{(x,y)}$. We conclude that the
strongly connected components of $H_{rr^{\prime}}\setminus{(x,y)}$ are
$\\{x\\}$ and $H_{rr^{\prime}}\setminus\\{x\\}$. $(1.4)$ Let $x$ be
$\mathit{oa}$ and $y$ be $\mathit{oa}$. This means that both $x$ and $y$ are
auxiliary in $H_{r}$, which implies that $y=d(r)$ in $G_{s}$. But since $y$ is
ordinary in $H_{rr^{\prime}}$, this case is not permitted to occur.

$(2)$ Let $x$ be an ordinary vertex of $H_{rr^{\prime}}$ and let $y$ be an
auxiliary vertex of $H_{rr^{\prime}}$. Since $y\neq d(r^{\prime})$ in
$H_{r}^{R}$, this means that $y$ is a marked vertex of $H_{r}^{R}$ and
$x=d(y)$ in $H_{r}^{R}$. Thus $(y,x)$ is an edge of $H_{r}$. Now we
distinguish four different cases, depending on whether $x$ and $y$ are
ordinary or auxiliary in $H_{r}$. $(2.1)$ Let $x$ be $\mathit{oo}$ and $y$ be
$\mathit{ao}$ in $H_{rr^{\prime}}$. Then we can argue as in $(1.1)$ in order
to get that all vertices of $H_{rr^{\prime}}$ can reach $d(r^{\prime})$ in
$H_{rr^{\prime}}$ in $H_{rr^{\prime}}\setminus{(x,y)}$. Now, as an implication
of Lemma A.18, we have that $d(r^{\prime})$ reaches all vertices of
$H_{rr^{\prime}}$ in $H_{rr^{\prime}}\setminus{(x,y)}$, except $y$, which is
unreachable from $d(r^{\prime})$ in $H_{rr^{\prime}}\setminus{(x,y)}$. We
conclude that the strongly connected components of
$H_{rr^{\prime}}\setminus{(x,y)}$ are $\\{y\\}$ and
$H_{rr^{\prime}}\setminus\\{y\\}$. $(2.2)$ Let $x$ be $\mathit{oo}$ and $y$ be
$\mathit{ao}$ in $H_{rr^{\prime}}$. Then we can argue as in $(2.1)$ in order
to conclude that the strongly connected components of
$H_{rr^{\prime}}\setminus{(x,y)}$ are $\\{y\\}$ and
$H_{rr^{\prime}}\setminus\\{y\\}$. $(2.3)$ Let $x$ be $\mathit{oa}$ and $y$ be
$\mathit{ao}$. First observe that, as an implication of Lemma A.18, we have
that $d(r^{\prime})$ reaches all vertices of $H_{rr^{\prime}}$ in
$H_{rr^{\prime}}\setminus{(x,y)}$, except $y$, which is unreachable from
$d(r^{\prime})$ in $H_{rr^{\prime}}\setminus{(x,y)}$. Now, we can argue as in
$(1.3)$ in order to get that $r$ is reachable from every vertex of $H_{r}^{R}$
in $H_{r}^{R}\setminus{(x,y)}$, except from $x$, which cannot reach $r$ in
$H_{r}^{R}\setminus{(x,y)}$, and possibly $d(r)$. Then, if we have that either
$d(r)$ can also reach $r$ in $H_{r}^{R}\setminus{(x,y)}$, or $d(r)\notin
H_{rr^{\prime}}$, by Lemma A.26 we must have that $d(r^{\prime})$ is reachable
from every vertex of $H_{rr^{\prime}}$ in $H_{rr^{\prime}}\setminus{(x,y)}$,
except from $x$, which cannot reach $d(r^{\prime})$ in
$H_{rr^{\prime}}\setminus{(x,y)}$. Thus, the strongly connected components of
$H_{rr^{\prime}}\setminus{(x,y)}$ in this case are $\\{x\\}$, $\\{y\\}$ and
$H_{rr^{\prime}}\setminus\\{x,y\\}$. Otherwise, let us assume that $d(r)$
cannot reach $r$ in $H_{r}^{R}\setminus{(x,y)}$, and also that $d(r)\in
H_{rr^{\prime}}$. Since $r$ is reachable from every vertex of
$H_{r}^{R}\setminus\\{x,d(r)\\}$ in $H_{r}^{R}\setminus{(x,y)}$, we must have
that $(d(r),x)$ is the only kind of outgoing edge of $d(r)$ in $H_{r}^{R}$.
Now, since $x\in H_{rr^{\prime}}$ and the immediate dominator of $d(r)$ in
$H_{r}^{R}$ is $r$, we have that $x$ is dominated by $d(r)$ in $H_{r}^{R}$;
and since $(d(r),x)$ is an edge of $H_{r}^{R}$, we must have that $d(r)$ is
the immediate dominator of $x$ in $H_{r}^{R}$. Now, since $y\in
H_{rr^{\prime}}$, we must also have that $y$ is dominated by $d(r)$ in
$H_{r}^{R}$. And then, since $(d(r),x)$ is the only kind of outgoing edge of
$d(r)$ in $H_{r}^{R}$, and $(x,y)$ is the only outgoing edge of $x$ in
$H_{r}^{R}$ (since $x$ is marked in $G_{s}$ and $y=d(x)$ in $G_{s}$), we must
have that $(x,y)$ is a bridge of $H_{r}^{R}$, and so $y$ is a marked vertex of
$H_{r}^{R}$ and $x$ is the immediate dominator of $y$ in $H_{r}^{R}$. Since
$x$ is an ordinary vertex of $H_{rr^{\prime}}$, and $y$ is marked vertex of
$H_{r}^{R}$ such that $x=d(y)$ in $H_{r}^{R}$, we must have that either $x$ is
marked in $H_{r}^{R}$ and $r^{\prime}=x$, or that $r^{\prime}=d(x)$ in
$H_{r}^{R}$. In any case, recall that $(d(r),x)$ is the only kind of outgoing
edge of $d(r)$ in $H_{r}^{R}$, and $(x,y)$ is the only outgoing edge of $x$ in
$H_{r}^{R}$. Thus, if $r^{\prime}=x$, then the vertex set of $H_{rr^{\prime}}$
is $\\{d(r),x,y\\}$. Furthermore, the strongly connected components of
$H_{rr^{\prime}}\setminus{(x,y)}$ in this case are $\\{x\\}$, $\\{y\\}$ and
$\\{d(r)\\}$ ($=H_{rr^{\prime}}\setminus{(x,y)}$). Otherwise, if
$r^{\prime}=d(r)$, then the vertex set of $H_{rr^{\prime}}$ is
$\\{r,d(r),x,y\\}$. Furthermore, the strongly connected components of
$H_{rr^{\prime}}\setminus{(x,y)}$ in this case are $\\{x\\}$, $\\{y\\}$,
$\\{d(r)\\}$ and $\\{r\\}$. $(2.4)$ Let $x$ be $\mathit{oa}$ and $y$ be
$\mathit{aa}$. This means that both $x$ and $y$ are auxiliary in $H_{r}$,
which implies that $x=d(r)$ in $G_{s}$. But since $x$ is ordinary in
$H_{rr^{\prime}}$, this case is not permitted to occur.

$(3)$ Let $x$ by an auxiliary vertex of $H_{rr^{\prime}}$ and let $y$ be an
ordinary vertex of $H_{rr^{\prime}}$. Since $x\neq d(r^{\prime})$ in
$H_{r}^{R}$, this means that $x$ is a marked vertex of $H_{r}^{R}$ with
$d(x)\in T(r^{\prime})$ in $H_{r}^{R}$. Now we distinguish four different
cases, depending on whether $x$ and $y$ are ordinary or auxiliary in $H_{r}$.
In any case, as an implication of Lemma A.17, we have that $d(r^{\prime})$ can
reach every vertex of $H_{rr^{\prime}}$ in $H_{rr^{\prime}}\setminus{(x,y)}$.
$(3.1)$ Let $x$ be $\mathit{ao}$ and $y$ be $\mathit{oo}$. Let $(x_{0},y)$ be
an edge of $H_{r}^{R}$ that corresponds to $(x,y)$ in $H_{rr^{\prime}}$. Then
$(y,x_{0})$ is an edge of $H_{r}$. If $x_{0}$ is an ordinary vertex of
$H_{r}$, then by Lemma A.17 we have that $r$ reaches all vertices of $H_{r}$
in $H_{r}\setminus{(y,x_{0})}$. This implies that every vertex of $H_{r}^{R}$
can reach $r$ in $H_{r}^{R}\setminus{(x_{0},y)}$. Then Lemma A.27 implies that
every vertex of $H_{rr^{\prime}}$ can reach $d(r^{\prime})$ in
$H_{rr^{\prime}}\setminus{(x,y)}$, and so we have that
$H_{rr}\setminus{(x,y)}$ is strongly connected. Similarly, if $x_{0}$ is an
auxiliary vertex of $H_{r}$, then, by Lemma A.18, we have that $r$ reaches all
vertices of $H_{r}$ in $H_{r}\setminus{(y,x_{0})}$, except $x_{0}$, which is
unreachable from $r$ in $H_{r}\setminus{(y,x_{0})}$, and possibly $d(r)$. This
implies that every vertex of $H_{r}^{R}$ can reach $r$ in
$H_{r}^{R}\setminus{(x_{0},y)}$, except $x_{0}$, which cannot reach $r$ in
$H_{r}^{R}\setminus{(x_{0},y)}$, and possibly $d(r)$. Since $x$ is an ordinary
vertex of $H_{r}$, we have that $x\neq x_{0}$, and so $x$ can reach $r$ in
$H_{r}^{R}\setminus{(x_{0},y)}$. Now Lemma A.27 implies that $x$ can reach
$d(r^{\prime})$ in $H_{rr^{\prime}}\setminus{(x,y)}$. Thus, every vertex of
$H_{rr^{\prime}}$ can reach $d(r^{\prime})$ in
$H_{rr^{\prime}}\setminus{(x,y)}$, and so we have that
$H_{rr^{\prime}}\setminus{(x,y)}$ is strongly connected. $(3.2)$ Let $x$ be
$\mathit{ao}$ and $y$ be $\mathit{oa}$. Let $\\{(x_{1},y),\dots,(x_{k},y)\\}$
be the set of all the incoming edges to $y$ in $H_{r}^{R}$. Then
$\\{(y,x_{1}),\dots,(y,x_{k})\\}$ is a collection of edges of $H_{r}$ that
stem from $y$. Since $y$ is auxiliary in $H_{r}$ and ordinary in
$H_{rr^{\prime}}$, we have that $y\neq d(r)$ in $G_{s}$, and therefore $y$ is
a marked vertex of $G_{s}$ such that $d(y)\in T(r)$. Thus, by Lemma A.20, we
have that $r$ can reach all vertices of $H_{r}$ in
$H_{r}\setminus\\{(y,x_{1}),\dots,(y,x_{k})\\}$. This implies that $r$ can be
reached from all vertices of $H_{r}^{R}$ in
$H_{r}^{R}\setminus\\{(x_{1},y),\dots,(x_{k},y)\\}$. Furthermore, since $y$ is
dominated by $d(r^{\prime})$ in $H_{r}^{R}$, we have that there is a path from
$r$ to $d(r^{\prime})$ in $H_{r}^{R}$ that avoids $y$; therefore, this path
also avoids all edges $\\{(x_{1},y),\dots,(x_{k},y)\\}$. Thus we infer that
$d(r^{\prime})$ is reachable from all vertices of $H_{r}^{R}$ in
$H_{r}^{R}\setminus\\{(x_{1},y),\dots,(x_{k},y)\\}$. In particular, let $P$ be
a path from $x$ to $d(r^{\prime})$ in
$H_{r}^{R}\setminus\\{(x_{1},y),\dots,(x_{k},y)\\}$. Then, by Lemma A.6 the
corresponding path $P_{H}$ in $H_{rr^{\prime}}$ has the same endpoints as $P$
and avoids the edge $(x,y)$. Thus, even by removing $(x,y)$ from
$H_{rr^{\prime}}$, all vertices from $H_{rr^{\prime}}$ can reach
$d(r^{\prime})$. We conclude that $H_{rr^{\prime}}\setminus{(x,y)}$ is
strongly connected. $(3.3)$ Let $x$ be $\mathit{aa}$ and $y$ be $\mathit{oo}$.
Let $(x_{0},y)$ be an edge of $H_{r}^{R}$ that corresponds to $(x,y)$ in
$H_{rr^{\prime}}$. Then $(y,x_{0})$ is an edge of $H_{r}$. Now, if $x_{0}$ is
ordinary in $H_{r}$ or it is auxiliary in $H_{r}$ but $x_{0}\neq x$, then we
can argue as in $(3.1)$ in order to establish that
$H_{rr^{\prime}}\setminus{(x,y)}$ is strongly connected. Otherwise, suppose
that $x_{0}=x$. First, let us assume that $d(r)\notin H_{rr^{\prime}}$. Now,
since $x$ is auxiliary in $H_{r}$ and $y$ is ordinary in $H_{r}$ (and $x\neq
d(r)$), we have that $y=d(x)$ in $G_{s}$. Now, by Lemma A.18 we have that $r$
reaches all vertices of $H_{r}$ in $H_{r}\setminus{(y,x)}$, except $x$, which
is unreachable from $r$ in $H_{r}\setminus{(y,x)}$, and possibly $d(r)$. This
implies that every vertex of $H_{r}^{R}$ can reach $r$ in
$H_{r}^{R}\setminus{(x,y)}$, except $x$, which cannot reach $r$ in
$H_{r}^{R}\setminus{(x,y)}$, and possibly $d(r)$. Now Lemma A.27 implies that
every vertex of $H_{rr^{\prime}}$ can reach $d(r^{\prime})$ in
$H_{rr^{\prime}}\setminus{(x,y)}$, except $x$, which cannot reach
$d(r^{\prime})$ in $H_{rr^{\prime}}$, and possibly $d(r)$. Since we have
assumed that $d(r)\notin H_{rr^{\prime}}$, we conclude that the strongly
connected components of $H_{rr^{\prime}}\setminus{(x,y)}$ are $\\{x\\}$ and
$H_{rr^{\prime}}\setminus\\{x\\}$. Now let us assume that $d(r)\in
H_{rr^{\prime}}$. There are two cases to consider: either $r^{\prime}=d(r)$,
or $d(r)$ is the immediate dominator of $r^{\prime}$ in $H_{r}^{R}$, and so it
is contained in $H_{rr^{\prime}}$ as the critical vertex. In either case, we
have that $x\neq d(r)$. Thus we can argue as previously, in order to get that
every vertex of $H_{rr^{\prime}}$ can reach $d(r^{\prime})$ in
$H_{rr^{\prime}}\setminus{(x,y)}$, except $x$, which cannot reach
$d(r^{\prime})$ in $H_{rr^{\prime}}$, and possibly $d(r)$. Now, if $d(r)$ is
the critical vertex of $H_{rr^{\prime}}$, then we have that
$d(r)=d(r^{\prime})$, and so we conclude that the strongly connected
components of $H_{rr}\setminus{(x,y)}$ are $\\{x\\}$ and
$H_{rr}\setminus\\{x\\}$. Otherwise, let $r^{\prime}=d(r)$. Then, since
$H_{rr^{\prime}}$ is strongly connected, we have that every vertex of
$H_{rr^{\prime}}$ reaches $d(r^{\prime})$ in $H_{rr^{\prime}}$. And since
$y=d(r)$ is forbidden (since $r^{\prime}=d(r)$), we have that $(x,y)$ is not
an incoming edge to $d(r)$. Thus, every vertex of $H_{rr^{\prime}}$ can reach
$d(r^{\prime})$ in $H_{rr^{\prime}}\setminus{(x,y)}$, except possibly $x$. We
conclude that the strongly connected components of
$H_{rr^{\prime}}\setminus{(x,y)}$ are $\\{x\\}$ and
$H_{rr^{\prime}}\setminus\\{x\\}$. $(3.4)$ Let $x$ be $\mathit{aa}$ and $y$ be
$\mathit{oa}$. Then we can use the same argument that we used in $(3.2)$ in
order to conclude that $H_{rr^{\prime}}\setminus{(x,y)}$ is strongly
connected.

$(4)$ Since $y\neq d(r^{\prime})$ in $H_{r}^{R}$, it is impossible that both
$x$ and $y$ are auxiliary in $H_{rr^{\prime}}$. ∎

The following Lemma shows that the $S$-operation maintains the strongly
connected components of a digraph upon removal of strong bridges.

######  Lemma A.30.

Let $G$ be a strongly connected digraph and let $(x,y)$ be a strong bridge of
$G$. Let $C$ be a strongly connected component of $G\setminus{(x,y)}$, and let
$C^{\prime}$ be the corresponding graph in $S(G,(x,y))$. Let $e$ be an edge of
$C^{\prime}$.

  1. (1)

Suppose first that both endpoints of $e$ lie in $C$. Then $e$ is a strong
bridge of $C^{\prime}$ if and only if $e$ is a strong bridge of $G$.
Furthermore, let $C_{1},\dots,C_{k}$ be the strongly connected components of
$G\setminus{e}$. Then at most one of $C_{1},\dots,C_{k}$ contains both $x$ and
$y$. All the other strongly connected components of $G\setminus{e}$ either lie
entirely within $C$, or they do not intersect with $C^{\prime}$ at all. Now
let $i\in\\{1,\dots,k\\}$. Then, if $C_{i}$ contains both $x$ and $y$, but no
vertex of $C$, then $\\{x\\}$ and $\\{y\\}$ are two distinct strongly
connected components of $C^{\prime}\setminus{e}$. Otherwise, $C_{i}\cap
C^{\prime}$ (if it is non-empty) is a strongly connected component of
$C^{\prime}\setminus{e}$.

  2. (2)

Now suppose that at least one endpoint $p$ of $e$ lies outside of $C$. Then
$e$ is a strong bridge of $C^{\prime}$ if and only if it is the only incoming
or outgoing edge of $p$ in $C^{\prime}$. Furthermore, the strongly connected
components of $C^{\prime}\setminus{e}$ are $\\{x\\}$ (if $x\notin C$),
$\\{y\\}$ (if $y\notin C$), and $C$.

###### Proof.

$(1)$ Let $e$ be an edge of $C^{\prime}$ such that both endpoints of $e$ lie
in $C$. Let $u,v$ be two vertices of $C$. Then, as a consequence of Lemma
A.11, we have that $u$ reaches $v$ in $C^{\prime}\setminus{e}$ if and only if
$u$ reaches $v$ in $G\setminus{e}$ $(*)$. This implies that $e$ is a strong
bridge of $C^{\prime}$ if and only if $e$ is a strong bridge of $G$. Now let
$C_{0}$ be a strongly connected component of $G\setminus{e}$. First, let us
assume that $C_{0}$ contains both $x$ and $y$, but no vertex of $C$. This
means that neither $x$ nor $y$ is a vertex of $C$. Then, by the definition of
$C^{\prime}$, we have that $(y,x)$ is not an edge of $C^{\prime}$. However,
since both endpoints of $e$ lie in $C$, we have that $e\neq(x,y)$, and so
$(x,y)\in C^{\prime}\setminus{e}$. Now let’s assume, for the sake of
contradiction, that $y$ can reach $x$ in $C^{\prime}\setminus{e}$. Then there
must be vertices $z,w\in C$ such that $(y,z)\in C^{\prime}$, $(w,x)\in
C^{\prime}$, and $z,w$ remain strongly connected in $C^{\prime}\setminus{e}$.
The existence of the edge $(y,z)\in C^{\prime}$ implies that there is a path
$P_{1}$ from $y$ to $z$ in $G$, that uses no vertices of $C$ except $z$.
Similarly, the existence of the edge $(w,x)\in C^{\prime}$ implies that there
is a path $P_{2}$ from $w$ to $x$ in $G$, that uses no vertices of $C$ except
$w$. Now, since $z$ can reach $w$ in $C^{\prime}\setminus{e}$, Lemma A.11
implies that there is a path $P$ from $z$ to $w$ in $G\setminus{e}$. Thus the
concatenation $P_{1}+P+P_{2}$ is a path from $y$ to $x$ in $G\setminus{e}$
that uses at least one vertex from $C$. But then the existence of $(x,y)$ in
$G\setminus{e}$ implies that $\\{x,y,z,w\\}\subseteq C_{0}$ \- a
contradiction. Thus we have that $\\{x\\}$ and $\\{y\\}$ are two distinct
strongly connected components of $C^{\prime}\setminus{e}$.

Now let us assume that $C_{0}$ contains both $x$ and $y$, and also a vertex
$z$ of $C$ (of course, it is possible that $z=x$ or $z=y$). Then $(*)$ implies
that all vertices of $C_{0}\cap C$ remain strongly connected in
$C^{\prime}\setminus{e}$. Furthermore, there is no vertex in $C\setminus
C_{0}$ that is strongly connected with vertices of $C_{0}\cap C$ in
$C^{\prime}\setminus{e}$. Now, since $z$ is strongly connected with $x$ in
$G\setminus{e}$, there is a path $P_{1}$ from $z$ to $x$ in $G\setminus{e}$.
Similarly, there is a path $P_{2}$ from $y$ to $z$ in $G\setminus{e}$. Now
consider the concatenation $P=P_{1}+(x,y)+P_{2}$, and let $\tilde{P}$ be the
compressed path of $P$ in $C^{\prime}$. Then, by Lemma A.11, $\tilde{P}$ is a
path from $z$ to $z$ in $C^{\prime}$, that uses the edge $(x,y)$ and avoids
the edge $e$. Thus, $z$ is strongly connected with both $x$ and $y$ in
$C^{\prime}\setminus{e}$. This means that $C_{0}\cap C^{\prime}$ is a strongly
connected component of $C^{\prime}\setminus{e}$.

Finally, let us assume that $C_{0}$ contains a vertex $z$ of $C$, but not both
$x$ and $y$. We will show that $C_{0}$ lies entirely within $C$. So let us
assume, for the sake of contradiction, that there is a vertex $w\in
C_{0}\setminus{C}$. Then, since $z$ and $w$ are strongly connected in
$G\setminus{e}$, there is a path $P_{1}$ from $z$ to $w$ in $G\setminus{e}$.
Similarly, there is a path $P_{2}$ from $w$ to $z$ in $G\setminus{e}$. Now,
since $z\in C$ but $w\notin C$, at least one of $P_{1}$ and $P_{2}$ must use
the edge $(x,y)$. But then the existence of the concatenation $P=P_{1}+P_{2}$
implies that $z$ is strongly connected with both $x$ and $y$ in
$G\setminus{e}$ \- a contradiction. Thus we have that $C_{0}\subseteq C$. Now
we will show that $C_{0}$ is a strongly connected component of
$C^{\prime}\setminus{e}$. By $(*)$ we have that all vertices of $C_{0}$ are
strongly connected in $C^{\prime}\setminus{e}$. Furthermore, there is no
vertex in $C\setminus C_{0}$ that is strongly connected with vertices of
$C_{0}$ in $C^{\prime}\setminus{e}$. Thus, $C_{0}$ is contained in a strongly
connected component $C_{0}^{\prime}$ of $C^{\prime}\setminus{e}$ such that
$C_{0}\subseteq C_{0}^{\prime}\subseteq C_{0}\cup\\{x,y\\}$. Now let us assume
that both $x$ and $y$ are contained in $C_{0}^{\prime}$. Then, since $z\in
C_{0}^{\prime}$, there is a path $P^{\prime}$ in $C^{\prime}\setminus{e}$ that
starts from $z$, ends in $z$, and uses the edge $(x,y)$. By Lemma A.11, there
is a path $P$ in $G$ such that $\tilde{P}=P^{\prime}$. This implies that $P$
starts from $z$, ends in $z$, uses the edge $(x,y)$ and avoids $e$. But this
means that $z$ is strongly connected with both $x$ and $y$ in
$G^{\prime}\setminus{e}$ \- a contradiction. Thus $C_{0}^{\prime}$ cannot
contain both $x$ and $y$. Now, if $C_{0}$ contains either $x$ or $y$, then
$C_{0}^{\prime}$ also contains $x$ or $y$, respectively, and we are done
(i.e., we have $C_{0}^{\prime}=C_{0}$, because $C_{0}^{\prime}$ cannot contain
both $x$ and $y$). Thus it is left to assume that $C_{0}$ contains neither $x$
nor $y$. Now there are three cases to consider: either $x\in C$ and $y\notin
C$, or $x\notin C$ and $y\in C$, or $C\cap\\{x,y\\}=\emptyset$. Let us assume
first that $x\in C$ and $y\notin C$. Now suppose, for the sake of
contradiction, that $x\in C_{0}^{\prime}$. This means that there is a path
$P^{\prime}$ from $z$ to $z$ in $C^{\prime}\setminus{e}$ that contains $x$.
Then, by Lemma A.11, we have that there is a path $P$ in $G$ such that
$\tilde{P}=P^{\prime}$. But this means that $z$ is strongly connected with $x$
in $G\setminus{e}$ \- contradicting our assumption that $x\notin C_{0}$. Thus
$x\notin C_{0}^{\prime}$. Now suppose, for the sake of contradiction, that
$y\in C_{0}^{\prime}$. But since $y\notin C$, in order for $z\in
C_{0}^{\prime}$ to reach $y$ in $C^{\prime}$, we must necessarily pass from
the edge $(x,y)$. Then we can see that $x$ and $y$ are both strongly connected
with $z$ in $C^{\prime}\setminus{e}$, contradicting the fact that
$C_{0}^{\prime}$ cannot contain both $x$ and $y$. Thus $y\notin
C_{0}^{\prime}$, and so we have that $C_{0}^{\prime}=C_{0}$. Similarly, we can
see that if $x\notin C$ and $y\in C$, then $C_{0}^{\prime}$ contains neither
$x$ nor $y$, and so we have $C_{0}^{\prime}=C_{0}$. Finally, let us assume
that neither $x$ nor $y$ is in $C$. Now, if either $x$ or $y$ is in
$C_{0}^{\prime}$, then $y$ or $x$, respectively, must also be in
$C_{0}^{\prime}$, since $(x,y)$ is the unique outgoing (resp. incoming) edge
of $x$ (resp. $y$) in $C^{\prime}$. But this contradicts the fact that
$C_{0}^{\prime}$ cannot contain both $x$ and $y$. Thus we conclude that
neither $x$ nor $y$ is in $C_{0}^{\prime}$, and so $C_{0}^{\prime}=C_{0}$.

$(2)$ Now let $e$ be an edge of $C^{\prime}$ such that at least one endpoint
$p$ of $e$ lies outside of $C$. Then we have that either $p=x$ or $p=y$. Let
us assume that $p=x$ (the case $p=y$ is treated similarly). Now suppose that
$e=(x,z)$, for some $z\in C^{\prime}$. Then, by the definition of
$C^{\prime}$, we have that $z=y$. Also, $(x,y)$ is the only outgoing edge of
$x$ in $C^{\prime}$. Thus, the strongly connected components of
$C^{\prime}\setminus{(x,y)}$ are $\\{x\\}$, $\\{y\\}$ (if $y\notin C$), and
$C$. Now suppose that $e=(z,x)$, for some $z\in C^{\prime}$. Then, by the
definition of $C^{\prime}$, we have that $z\in C$. Thus, if there is another
incoming edge $(w,x)$ of $x$ in $C^{\prime}$, then
$C^{\prime}\setminus{(z,x)}$ is not a strong bridge of $C^{\prime}$, since $z$
can still reach $w$ in $C^{\prime}\setminus{(z,x)}$ using edges of $C$. Thus
$(z,x)$ is a strong bridge of $C^{\prime}$ if and only if it is the only
incoming edge of $x$ in $C^{\prime}$. In this case, the strongly connected
components of $C^{\prime}\setminus{(z,x)}$ are $\\{x\\}$, $\\{y\\}$ (if
$y\notin C$), and $C$. ∎

######  Corollary A.31.

Let $G_{s}$ be a strongly connected digraph and let $r$ be a marked vertex of
$H_{s}^{R}$. Let $C$ be a strongly connected component of
$H_{sr}\setminus{(d(r),r)}$, and let $H$ be the corresponding graph in
$S(H_{sr},(d(r),r))$, where $d(r)$ is the immediate dominator of $r$ in
$H_{s}^{R}$. Let $e$ be a strong bridge of $H$. Then the strongly connected
components of $H\setminus{e}$ are given by one of the following:

  1. (i)

$\\{x\\}$ and $H\setminus\\{x\\}$, where $x$ is auxiliary in $H_{s}$ and
$y=d(x)$ in $G_{s}$

  2. (ii)

$\\{x\\}$ and $H\setminus\\{x\\}$, where $x$ is auxiliary in $H_{sr}$ and
$(x,y)$ is the only outgoing edge of $x$ in $H_{sr}$

  3. (iii)

$\\{y\\}$ and $H\setminus\\{y\\}$, where $y$ is auxiliary in $H_{sr}$ and
$x=d(y)$ in $H_{s}^{R}$

  4. (iv)

$\\{x\\}$, $\\{y\\}$ and $H\setminus\\{x,y\\}$, where $x$ is auxiliary in
$H_{s}$, $y$ is auxiliary in $H_{sr}$, $x=d(y)$ in $H_{s}^{R}$ and $y=d(x)$ in
$G_{s}$

  5. (v)

$\\{d(r)\\}$, $\\{r\\}$ (if $r\notin C$), and $C$

###### Proof.

Since $(d(r),r)$ is the only outgoing edge of $d(r)$ in $H_{sr}$, observe that
one of the strongly connected components of $H_{sr}\setminus{(d(r),r)}$ is
$\\{d(r)\\}$. It is trivial to verify the Corollary for this case, and so we
may assume that $C\neq\\{d(r)\\}$. Now let us assume first that both endpoints
of $e$ lie in $C$. Then case $(1)$ of Lemma A.30 applies, and thus $e$ is
subject to one of cases $(i)$ to $(iv)$ of Lemma A.28. Thus we get cases $(i)$
to $(iv)$ in the statement of the Corollary. Now, if one of the endpoints of
$e$ lies outside of $C$, then case $(2)$ of Lemma A.30 applies, and thus we
get case $(v)$ in the statement of the Corollary. ∎

######  Corollary A.32.

Let $G_{s}$ be a strongly connected digraph, let $r$ be a marked vertex of
$G_{s}$, and let $r^{\prime}$ be a marked vertex of $H_{r}^{R}$. Let $C$ be a
strongly connected component of
$H_{rr^{\prime}}\setminus{(d(r^{\prime}),r^{\prime})}$, and let $H$ be the
corresponding graph in $S(H_{rr^{\prime}},(d(r^{\prime}),r^{\prime}))$, where
$d(r^{\prime})$ is the immediate dominator of $r^{\prime}$ in $H_{r}^{R}$. Let
$e$ be a strong bridge of $H$. Then the strongly connected components of
$H\setminus{e}$ are given by one of the following:

  1. (i)

$\\{x\\}$ and $H\setminus\\{x\\}$, where $x$ is auxiliary in $H_{r}$ and
$y=d(x)$ in $G_{s}$

  2. (ii)

$\\{x\\}$ and $H\setminus\\{x\\}$, where $x$ is auxiliary in $H_{rr^{\prime}}$
and $(x,y)$ is the only outgoing edge of $x$ in $H_{rr^{\prime}}$

  3. (iii)

$\\{y\\}$ and $H\setminus\\{y\\}$, where $y$ is auxiliary in $H_{rr^{\prime}}$
and $x=d(y)$ in $H_{r}^{R}$

  4. (iv)

$\\{x\\}$, $\\{y\\}$ and $H\setminus\\{x,y\\}$, where $x$ is auxiliary in
$H_{r}$, $y$ is auxiliary in $H_{rr^{\prime}}$, $x=d(y)$ in $H_{r}^{R}$ and
$y=d(x)$ in $G_{s}$

  5. (v)

$\\{x\\}$, $\\{y\\}$, $\\{d(r)\\}$ and $\\{r\\}$, where $r^{\prime}=d(r)$, $x$
is auxiliary in $H_{r}$, $y$ is auxiliary in $H_{rr^{\prime}}$, $x=d(y)$ in
$H_{r}^{R}$, $y=d(x)$ in $G_{s}$, and $(d(r),x)$ is the only kind of outgoing
edge of $d(r)$ in $H_{rr^{\prime}}$

  6. (vi)

$\\{d(r^{\prime})\\}$, $\\{r^{\prime}\\}$ (if $r^{\prime}\notin C$), and $C$

###### Proof.

Arguing as in the proof of Corollary A.31, we can see that this Corollary is a
consequence of Lemma A.30 and Lemma A.29. ∎

##  Appendix B Computing the partition of the 2eTSCCs due to the strong
bridges

Let $G_{s}$ be a strongly connected digraph, and let $H$ be either $(1)$
$H_{ss}$, or $(2)$ $\widetilde{H}_{rr}$, or $(3)$ $S(H_{sr},(d(r),r))$, or
$(4)$ $S(H_{rr^{\prime}},(d(r^{\prime}),r^{\prime}))$ (for some marked
vertices $r$ and $r^{\prime}$ in $G_{s}$ and $H_{r}^{R}$, respectively).
Depending on whether $H$ satisfies $(1)$, $(2)$, $(3)$, or $(4)$, we have a
clear picture of the structure of the strongly connected components of $H$
upon removal of a strong bridge, thanks to Lemma A.22, Lemma A.25, Corollary
A.31, or Corollary A.32, respectively. We can apply this information in order
to compute the partition of the $2$-edge twinless strongly connected
components of $H$ due the strong bridges as follows.

Let $e=(x,y)$ be a strong bridge of $H$. Observe that in every case that
appears in Lemma A.22, Lemma A.25, Corollary A.31, or Corollary A.32, the
strongly connected components of $H\setminus{e}$ are given by one of the
following: $(i)$, $\\{x\\}$ and $H\setminus\\{x\\}$, $(ii)$, $\\{y\\}$ and
$H\setminus\\{y\\}$, $(iii)$, $\\{x\\}$, $\\{y\\}$ and $H\setminus\\{x,y\\}$,
or $(iv)$ $\\{x\\}$, $\\{y\\}$ $\\{d(r)\\}$, $\\{r\\}$. In every case in which
$\\{x\\}$ or $\\{y\\}$ appears as a separate strongly connected component, we
have that $x$, $y$, or both, respectively, are not $\mathit{oo}$ vertices, and
so they are not in the same $2$-edge twinless strongly connected component
with any $\mathit{oo}$ vertex of $H$. (We may ignore case $(iv)$, because this
is due to a singular case in which $H$ consists of four vertices, where only
one of them is $\mathit{oo}$.) Now, depending on whether we are in case $(i)$,
$(ii)$, or $(iii)$, we define $X_{e}=\\{x\\}$, $X_{e}=\\{y\\}$, or
$X_{e}=\\{x,y\\}$, respectively. In other words, $X_{e}$ is the set of the
non-$\mathit{oo}$ vertices that get (strongly) disconnected from the rest of
the graph upon removal of $e$. Then we have that $X_{e}$ satisfies the
following:

  1. (1)

$H[V\setminus{X_{e}}]$ is a strongly connected component of $H\setminus{e}$

  2. (2)

$X_{e}$ contains no $\mathit{oo}$ vertex of $H$

Now we can apply the following procedure to compute the partition of $2$-edge
twinless strongly connected components of (the $\mathit{oo}$ vertices of) $H$
due to the strong bridges. Initially, we let $\mathcal{P}$ be the trivial
partition of $V$ (i.e., $\mathcal{P}=\\{V\\}$). Now, for every strong bridge
$e$ of $H$, we compute the TSCCs of $H\setminus{X_{e}}$, and we refine
$\mathcal{P}$ according to those TSCCs. By [Rag06], the computation of the
TSCCs of $H\setminus{X_{e}}$ is equivalent to determining the $2$-edge-
connected components of $H^{u}\setminus{X_{e}}$. Observe that this procedure
does not run in linear time in total, since it has to be performed for every
strong bridge $e$ of $H$.

Our goal is to perform the above procedure for all strong bridges $e$ of $H$
at once. We can do this by first taking $H^{u}$, and then shrinking every
$X_{e}$ in $H^{u}$ into a single marked vertex, for every strong bridge $e$ of
$H$. Let $H^{\prime}$ be the resulting graph. Then we simply compute the
marked vertex-edge blocks of $H^{\prime}$. This is shown in Algorithm 5. We
note that, given an auxiliary graph $H$ as above, we can compute all sets
$X_{e}$ in linear time, by first computing all strong bridges of $H$ [ILS12],
and then checking which case of Lemma A.22, Lemma A.25, Corollary A.31, or
Corollary A.32 applies for each strong bridge (which can be easily checked in
$O(1)$ time).

The following two lemmas describe conditions under which the simultaneous
contraction of several subsets of the vertex set of an undirected graph
maintains the marked vertex-edge blocks.

######  Lemma B.1.

Let $G=(V,E)$ be a connected undirected graph and let $X_{1},\dots,X_{k}$ be a
collection of disjoint subsets of $V$, such that $G\setminus{X_{i}}$ is
connected for every $i\in\\{1,\dots,k\\}$. Let also $u$ and $v$ be two
vertices of $G$ that do not belong to any of $X_{1},\dots,X_{k}$. Suppose that
$u$ and $v$ belong to the same $2$-edge-connected component of
$G\setminus{X_{i}}$, for every $i\in\\{1,\dots,k\\}$. Now let $G^{\prime}$ be
the graph that is derived from $G$ by contracting every $X_{i}$, for
$i\in\\{1,\dots,k\\}$, into a single marked vertex. Then $u$ and $v$ belong to
the same marked vertex-edge block of $G^{\prime}$.

###### Proof.

Let $z$ be a marked vertex of $G^{\prime}$ that corresponds to a set
$X\in\\{X_{1},\dots,X_{k}\\}$. Then we have that $u$ and $v$ belong to the
same $2$-edge-connected component of $G\setminus{X}$. Thus there is a cycle
$C$ in $G\setminus{X}$ that contains $u$ and $v$, but no vertex of $X$. Then
$C$ corresponds to a cycle $C^{\prime}$ of $G^{\prime}$ that contains both $u$
and $v$ and avoids $z$. Thus $u$ and $v$ are also $2$-edge-connected in
$G^{\prime}\setminus{z}$. Due to the generality of $z$, we have that $u$ and
$v$ belong to the same marked vertex-edge block of $G^{\prime}$. ∎

######  Lemma B.2.

Let $G=(V,E)$ be a connected undirected graph and let $X_{1},\dots,X_{k}$ be a
collection of disjoint subsets of $V$, such that $G\setminus{X_{i}}$ is
connected for every $i\in\\{1,\dots,k\\}$. Let also $u$ and $v$ be two
vertices of $G$ that do not belong to any of $X_{1},\dots,X_{k}$. Suppose that
there is a $j\in\\{1,\dots,k\\}$ such that $u$ and $v$ belong to different
$2$-edge-connected components of $G\setminus{X_{j}}$. Now let $G^{\prime}$ be
the graph that is derived from $G$ by contracting every $X_{i}$, for
$i\in\\{1,\dots,k\\}$, into a single marked vertex. Then the following is a
sufficient condition to establish that $u$ and $v$ belong to different marked
vertex-edge blocks of $G^{\prime}$: Let $T$ be the tree of the $2$-edge-
connected components of $G\setminus{X_{j}}$; then, for every
$i\in\\{1,\dots,k\\}\setminus\\{j\\}$, we have that either $(1)$ $X_{i}$ lies
entirely within a node of $T$, or $(2)$ a part of $X_{i}$ constitutes a leaf
of $T$, and the remaining part of $X_{i}$ lies within the adjacent node of
that leaf in $T$.

###### Proof.

Let $z$ be the marked vertex of $G^{\prime}$ that corresponds to $X_{j}$. Let
$T^{\prime}$ be the tree of the $2$-edge-connected components of
$G^{\prime}\setminus{z}$. We will show that $u$ and $v$ belong to different
nodes of $T^{\prime}$. First, we have that $u$ and $v$ belong to different
nodes of $T$. Now, $T^{\prime}$ is derived from $T$ in the same way that
$G^{\prime}$ is derived from $G$, i.e., by contracting the nodes of $T$ that
contain all the different parts of $X_{i}$ into a single node, for every
$i\in\\{1,\dots,k\\}\setminus\\{j\\}$. Now take a
$X_{i}\in\\{X_{1},\dots,X_{k}\\}\setminus\\{X_{j}\\}$. If $(1)$ holds for
$X_{i}$, then the contraction of $X_{i}$ in $G^{\prime}$ induces no change on
$T$. If $(2)$ holds for $X_{i}$, then the contraction of $X_{i}$ in
$G^{\prime}$ induces the following change on $T$: a leaf of $T$, that contains
neither $u$ nor $v$, is contracted with its adjacent node in $T$. Thus we can
see that $u$ and $v$ belong to different nodes of $T^{\prime}$. ∎

######  Proposition B.3.

Let $G_{s}$ be a strongly connected digraph, and let $H$ be a digraph that
satisfies one of the following:

  1. (1)

$H=H_{ss}$

  2. (2)

$H=\widetilde{H}_{rr}$, where $r$ is a marked vertex of $G_{s}$

  3. (3)

$H\in S(H_{sr},(d(r),r))$, where $r$ is a marked vertex of $G_{s}$ and
$(d(r),r)$ is the critical edge of $H_{sr}$

  4. (4)

$H\in S(H_{rr^{\prime}},(d(r^{\prime}),r^{\prime}))$, where $r$ is a marked
vertex of $G_{s}$, $r^{\prime}$ is a marked vertex of $H_{r}^{R}$, and
$(d(r^{\prime}),r^{\prime})$ is the critical edge of $H_{rr^{\prime}}$

Then Algorithm LABEL:algorithm:linear correctly computes the partition of
$2$-edge twinless strongly connected components of the $\mathit{oo}$ vertices
of $H$ due to the strong bridges.

###### Proof.

We will demonstrate how to handle case $(1)$, by relying on Lemma A.22. Cases
$(2)$, $(3)$ and $(4)$ can be handled using similar arguments, by relying on
Lemma A.25, Corollary A.31, and Corollary A.32, respectively. In any case, we
have to establish the following. Let $\mathcal{E}$ be the collection of the
strong bridges of $H$. Then the collection $\\{X_{e}\mid e\in\mathcal{E}\\}$
consists of sets that are either singletons or $2$-element sets. First we show
that the $2$-element sets in $\\{X_{e}\mid e\in\mathcal{E}\\}$ are pairwise
disjoint. Then we show that, despite the simultaneous contractions of the sets
in $\\{X_{e}\mid e\in\mathcal{E}\\}$, the marked vertex-edge blocks of the
underlying graph of $H$ are maintained. This is achieved by showing that the
collection $\\{X_{e}\mid e\in\mathcal{E}\\}$ satisfies the preconditions in
Lemmas B.1 and B.2.

Now, in case $(1)$, by Lemma A.22 we have that the sets $X_{e}$, for all
strong bridges $e$ of $H_{ss}$, are given by cases $(i)$ to $(iv)$ in the
statement of this Lemma. To be precise, in cases $(i)$ and $(ii)$ we set
$X_{e}\leftarrow\\{x\\}$; in case $(iii)$ we set $X_{e}\leftarrow\\{y\\}$; and
in case $(iv)$ we set $X_{e}\leftarrow\\{x,y\\}$. Thus, the last case is the
only one in which $X_{e}$ is a $2$-element set.

Now let $e,e^{\prime}$ be two strong bridges of $H_{ss}$ such that $X_{e}$ and
$X_{e^{\prime}}$ are two distinct $2$-element sets. We will show that
$X_{e}\cap X_{e^{\prime}}=\emptyset$. So let $X_{e}=\\{x,y\\}$ and
$X_{e^{\prime}}=\\{z,w\\}$. Since these sets can occur only in case $(iv)$ of
Lemma A.22, we may assume, without loss of generality, that $e=(x,y)$ and
$e^{\prime}=(z,w)$. Then we have that $y$ and $w$ are auxiliary, but not
critical, vertices of $H_{ss}$. Since, then, $y$ and $w$ have only one
incoming edge in $H_{ss}$, we must have that either $y=w$ and $x=z$, or $y\neq
w$. The first case means that $e=e^{\prime}$, and so it is rejected. Thus we
have $y\neq w$. By Lemma A.22, we have that $y=d(x)$ in $G_{s}$ and $w=d(z)$
in $G_{s}$. Thus, $y\neq w$ implies that $x\neq z$. Now, each of the cases
$x=w$ and $y=z$ is rejected, because there is no edge between auxiliary but
not critical vertices. We conclude that $\\{x,y\\}\cap\\{z,w\\}=\emptyset$.

Now let $H^{\prime}$ be the graph that is derived from $H^{u}$ after we have
contracted every $X_{e}$ into a single marked vertex. We will show that two
$\mathit{oo}$-vertices of $H_{ss}$ are twinless strongly connected in
$H_{ss}\setminus{e}$ for any strong bridge $e$, if and only if they belong to
the same marked vertex-edge block of $H^{\prime}$. So let $u,v$ be two
$\mathit{oo}$-vertices of $H_{ss}$ that are twinless strongly connected in
$H_{ss}\setminus{e}$ for any strong bridge $e$. Then, by [Rag06] we have that,
for every strong bridge $e$ of $H_{ss}$, $u$ and $v$ belong to the same
$2$-edge-connected component of $H_{ss}^{u}\setminus{X_{e}}$. Then Lemma B.1
implies that $u$ and $v$ belong to the same marked vertex-edge block of
$H^{\prime}$. Conversely, let $u,v$ be two $\mathit{oo}$-vertices of $H_{ss}$
such that there is a strong bridge $e$ for which $u$ and $v$ are not twinless
strongly connected in $H_{ss}\setminus{e}$. By [Rag06], this means that $u$
and $v$ belong to different $2$-edge-connected components of
$H_{ss}^{u}\setminus{X_{e}}$. Now let $e^{\prime}$ be a strong bridge of
$H_{ss}$ such that $X_{e^{\prime}}\neq X_{e}$. We will show that
$X_{e^{\prime}}$ satisfies one of conditions $(1)$ and $(2)$ of Lemma B.2.
Now, if $X_{e^{\prime}}$ is a singleton set, then there is nothing to show,
since there is no contraction induced by $X_{e^{\prime}}$ in this case. So let
$X_{e^{\prime}}=\\{x,y\\}$. This can occur only in case $(iv)$, and so we may
assume, without loss of generality, that $e^{\prime}=(x,y)$. Now, if $x$ and
$y$ belong to the same twinless strongly connected component of
$H_{ss}\setminus{e}$, then condition $(1)$ of Lemma B.2 is satisfied.
Otherwise, since $x$ and $y$ are connected with the edge $(x,y)$, we must have
that $(y,x)$ exists. But since $(x,y)$ is the only incoming edge of $y$ in
$H_{ss}$ (since $x=d(y)$ in $H_{s}^{R}$), we must have that $\\{y\\}$
constitutes a singleton twinless strongly connected component of
$H_{ss}\setminus{e}$, and so condition $(2)$ of Lemma B.2 is satisfied. Thus,
Lemma B.2 ensures that, by contracting every $\\{X_{e}\mid e\in\mathcal{E}\\}$
into a single marked vertex in $H^{u}$, $u$ and $v$ belong to different marked
vertex-edge blocks of $H^{\prime}$. ∎