For positive integers $t,p$, define $f(t,p)=2^{\mathcal{R}^{\prime}(2t)}\cdot
f(t,p-1)+\mathcal{R}^{\prime}(2t)$ when $p>1$ and $f(t,1)=t$.

######  Lemma 4.9 (Simplifying a biclique).

Let $D$ be a directed graph and $t$ be a positive integer. Suppose there
exists ordered sets $A,B\subseteq V(D)$ such that $|A|=|B|\geq f(t,2t+2)$,
$D^{\star}$ contains an $(A,B)$-induced-biclique and the matching edges of
$(A,B)$ are minimal in $D$,. Then, one can obtain $\widehat{D}$ from $D$ by
contraction, such that either

  1. 1.

$\widehat{D}$ contains an ordered $t$-tough-pair, or

  2. 2.

$\widehat{D}^{*}$ contains a $t$-induced-biclique whose edges are minimal in
$\widehat{D}$.

###### Proof of Lemma 4.1.

We now give a proof of Lemma 4.1 using the lemmas stated earlier. The proofs
of the those lemmas appear in their respective sections.

Set $t_{1}=\max\\{\textnormal{{cor}}(9t),9t\\}$,
$t_{2}=\max\\{f(t_{1},2t_{1}+2),\textnormal{{cor}}(9t_{1}),9t_{1}\\}$ where
$f$ is defined as in Lemma 4.9 and cor is defined in Corollary 4.7. Then,
define $t^{\prime}=\mathcal{R}(2t_{2},9)$. We will now show that if $D$
contains a $t^{\prime}$-tough-pair, then there exists
$D^{\prime}\in\mathcal{D}$ that is a $t$-hard-pattern.

Given $D$, let $(X,Y)$ be a $t^{\prime}$-tough-pair in $D$. Let $D_{1}$ be a
spanning subgraph of $D$ such that $D_{1}$ is reachability-minimal, $D_{1}$ is
transitively equivalent to $D$ and $(X,Y)$ is a $t^{\prime}$-tough-pair in
$D_{1}$. Observe that such a graph $D_{1}$ exists and can be obtained by
starting with the edge set $E_{0}=X\cup Y$ and adding an edge of $D$ to
$E_{0}$ as long as $D[E_{0}]$ remains reachability-minimal.

Using Lemma 4.3 on $D_{1}$, we conclude that either $D_{1}$ contains an
ordered $t_{2}$-tough-pair, or a $t_{2}$-biclique, or there exists
$A,B\subseteq V(D_{1})$ such that $|A|=|B|=t_{2}$ and $D_{1}$ contains an
$(A,B)$-induced-matching and $D_{1}^{\star}$ contains an $(A,B)$-induced-
biclique.

In the first case, by applying Corollary 4.7 on $D^{\star}_{1}$, we either get
$D_{2}\in\mathcal{D}$ such that $D_{2}$ is some $t$-hard-matching-pattern, or
conclude that $D^{\star}_{1}$ contains a $9t$-induced-biclique whose edges are
minimal in $D_{1}$. Then applying Lemma 4.8 to $D_{1}$ gives some $t$-hard-
biclique-pattern in $\mathcal{D}$. In the second case, again by applying Lemma
4.8 to $D_{1}$ gives some $t$-hard-biclique-pattern in $\mathcal{D}$.

In the third case, by applying Lemma 4.9 we conclude that there exists
$D_{2}\in\mathcal{D}$ such that either $D_{2}$ contains an ordered
$t_{1}$-tough-pair, in which case a further application of Corollary 4.7 on
$D^{\star}_{2}$ either yields a $D_{3}\in\mathcal{D}$ which is a $t$-hard-
matching-pattern, or we conclude that $D^{\star}_{2}$ contains a $9t$-induced-
biclique whose edges are minimal in $D_{2}$. In the remaining cases, applying
Lemma 4.8 yields a $D_{4}\in\mathcal{D}$ which is some $t$-hard-biclique-
pattern. ∎

##### Basic terminology for the remaining section.

Throughout the remaining section, we use the following basic notation. For two
integers $i,j$, $[i]$ denotes the set $\\{1,\ldots,i\\}$ and $[i,j]$ denotes
the set $\\{i,i+1,\ldots,j\\}$. For any (di)graph $D$ and sets $S,T\subseteq
V(D)$, an $(S,T)$-path in $D$ is a path in $D$ from some vertex of $S$ to some
vertex of $T$. If $S$ or $T$ is singleton, say $S=\\{v\\}$, then we use the
notation $(v,T)$-path. Let $e\in E(D)$, let $D/e$ represents the (di)graph
obtained after contracting $e$, that is, by deleting the endpoints of $e$ and
adding a new vertex $x_{e}$ such that the set of in-neighbours (resp. out-
neighbours) of $x_{e}$ is the union of the set of in-neighbours (resp. out-
neighbours) of the end points of $e$ in $D$. For $E^{\prime}\subseteq E(D)$,
$V(E^{\prime})\subseteq V(G)$ is the set of vertices that are endpoints of
some edge in $E^{\prime}$. If $D$ is a digraph, the for any $v\in V(D)$,
$N^{-}_{D}(v)$ denotes the set of in-neighbours if $v$ in $D$, $N^{+}_{D}(v)$
denotes the set of out-neighbours if $v$ in $D$ and $N_{D}(v)$ denotes the set
of in-neighbours and out-neighbours, called the neighbours, of $v$ in $D$. We
say that a digraph $D$ is connected if its underlying undirected graph is
connected.

###  4.1 Simplifying the $t$-tough-pair

In this section we prove Lemma 4.3 restated below. See 4.3

###### Proof.

Let $(E_{1},E_{2})$ be an $\mathcal{R}(2t,9s)$-tough-pair in $D$. Let
$t^{\prime}=\mathcal{R}(2t,9)$. Fix an arbitrary ordering of the edges of
$E_{1}$ and $E_{2}$. Let $E_{1}=(e^{1}_{1},\ldots,e^{1}_{t^{\prime}})$ and let
$E_{2}=(e^{2}_{1},\ldots,e^{2}_{t^{\prime}})$. Fix $i\in[2]$. We will use
Ramsey arguments to prove the lemma. Towards this, construct an auxiliary
undirected, complete, edge-colored graph $\textnormal{{Aux}}_{i}$ as follows.
The vertex set of $\textnormal{{Aux}}_{i}$ corresponds to the edges of
$E_{i}$, that is, for each $e\in E_{i}$ there is a vertex corresponding to
$e$. For the sake of simplicity we denote the vertex of
$\textnormal{{Aux}}_{i}$ that correspond to the edge $e$ of $E_{i}$, by $e$
itself. The coloring function $\texttt{col}_{i}$ on the edges of
$\textnormal{{Aux}}_{i}$ (equivalently on the pair of distinct edges of
$E_{i}$) is defined based on the following. Fix any two distinct edges
$e=(u,v),e^{\prime}=(u^{\prime},v^{\prime})\in E_{i}$. The coloring function
$\texttt{col}_{i}(e,e^{\prime})$ is defined based on the existence of the
edges $(u,v^{\prime})$ and $(u^{\prime},v)$ in $D$ and $D^{\star}$. Below we
describe $\texttt{col}_{i}(e,e^{\prime})$.

  1. 1.

If $(u,v^{\prime})\in E(D)$, and

    1. (a)

$(u^{\prime},v)\in E(D)$, then $\texttt{col}_{i}(e,e^{\prime})=(1,1)$,

    2. (b)

$(u^{\prime},v)\in E(D^{\star})\setminus E(D)$, then
$\texttt{col}_{i}(e,e^{\prime})=(1,2)$,

    3. (c)

$(u^{\prime},v)\not\in E(D)$, $(u^{\prime},v)\not\in E(D^{\star})$, then
$\texttt{col}_{i}(e,e^{\prime})=(1,3)$.

  2. 2.

If $(u,v^{\prime})\in E(D^{\star})\setminus E(D)$, and

    1. (a)

$(u^{\prime},v)\in E(D)$, then $\texttt{col}_{i}(e,e^{\prime})=(2,1)$,

    2. (b)

$(u^{\prime},v)\in E(D^{\star})\setminus E(D)$, then
$\texttt{col}_{i}(e,e^{\prime})=(2,2)$,

    3. (c)

$(u^{\prime},v)\not\in E(D)$, $(u^{\prime},v)\not\in E(D^{\star})$, then
$\texttt{col}_{i}(e,e^{\prime})=(2,3)$.

  3. 3.

If $(u,v^{\prime})\not\in E(D)$, $(u,v^{\prime})\not\in E(D^{\star})$, and

    1. (a)

$(u^{\prime},v)\in E(D)$, then $\texttt{col}_{i}(e,e^{\prime})=(3,1)$,

    2. (b)

$(u^{\prime},v)\in E(D^{\star})\setminus E(D)$, then
$\texttt{col}_{i}(e,e^{\prime})=(3,2)$,

    3. (c)

$(u^{\prime},v)\not\in E(D)$, $(u^{\prime},v)\not\in E(D^{\star})$, then
$\texttt{col}_{i}(e,e^{\prime})=(3,3)$.

We now use a Ramsey argument on the $t^{\prime}$-vertex graph
$\textnormal{{Aux}}_{i}$ with edge-coloring function $\texttt{col}_{i}$ (that
uses at most $9$ different colors). Using Ramsey arguments, we conclude that
there exists a monochromatic clique in $\textnormal{{Aux}}_{i}$ of size $2t$.
Below we show how one can get one of the three outcomes in the lemma statement
based of the color of the monochromatic clique. Say edges of $E_{i}$ that
correspond to this monochromatic clique in $\textnormal{{Aux}}_{i}$ are
$E^{\prime}_{i}=\\{e^{i}_{j_{1}},e^{i}_{j_{2}},\ldots,e^{i}_{j_{t}}\\}$ such
that $j_{1}<\ldots<j_{t}$ (recall we fixed an ordering of the edges of
$E_{i}$). For the ease of notation later, we assume that the sets
$E^{\prime}_{i}$ are ordered with the ordering as described in the previous
line.

######  Claim 4.10.

If for each $i\in[2]$, the color of the monochromatic clique in
$\textnormal{{Aux}}_{i}$ is $(j,3)$ or $(3,j)$ for any $j\in[3]$, then
$(E^{\prime}_{1},E^{\prime}_{2})$ form an ordered $2t$-tough-pair in $D$.

###### Proof.

Since $(E_{1},E_{2})$ is a tough-pair and $E^{\prime}_{i}\subseteq E_{i}$,
$(E^{\prime}_{1},E^{\prime}_{2})$ is also a tough-pair (of size $t$). If
$\texttt{col}_{i}$ colors the clique corresponding to the edges of
$E^{\prime}_{i}$ with the color $(j,3)$, then consider the ordering
$(e^{i}_{j_{1}},e^{i}_{j_{2}},\ldots,e^{i}_{j_{t}})$ of $E^{\prime}_{i}$,
otherwise (when $\texttt{col}_{i}$ colors the monochromatic clique with color
$(3,j)$), then consider the ordering $(e^{i}_{j_{t}},\ldots,e^{i}_{j_{1}})$ of
$E^{\prime}_{i}$. Then from the description of the definition of
$\texttt{col}_{i}$ corresponding to the case when $\texttt{col}_{i}$ takes
value $(3,j)$ or $(j,3)$, one concludes that $(E^{\prime}_{1},E^{\prime}_{2})$
is indeed an ordered $t$-tough-pair with the ordering described above. ∎

Note that if the graph has an ordered $2t$-tough-pair, then it also has an
ordered $t$-tough-pair.

######  Observation 4.11.

It is easy to observe that if the color of the monochromatic clique in
$\textnormal{{Aux}}_{i}$ is $(1,1)$, then
$(\text{tail}(E^{\prime}_{i}),\text{head}(E^{\prime}_{i}))$ form a
$2t$-biclique in $D$. If the color is $(2,2)$, then $D$ contains the
$(\text{tail}(E^{\prime}_{i}),\text{head}(E^{\prime}_{i}))$-induced matching
and $D^{\star}$ contains the
$(\text{tail}(E^{\prime}_{i}),\text{head}(E^{\prime}_{i}))$-biclique (thus,
the third outcome of the lemma holds).

Note that if the graph has $2t$-biclique, then it also has an ordered
$t$-biclique.

######  Claim 4.12.

If there exists $i\in[2]$ such that the color of the monochromatic clique in
$\textnormal{{Aux}}_{i}$ is $(1,2)$ or $(2,1)$, then $H$ contains a
$t$-biclique.

###### Proof.

Suppose that the color of the monochromatic clique in $\textnormal{{Aux}}_{i}$
is $(1,2)$. Recall that
$E^{\prime}_{i}=((e^{i}_{j_{1}},e^{i}_{j_{2}},\ldots,e^{i}_{j_{t}}))$ is the
ordered set of edges that correspond to the monochromatic clique. The
$(\text{tail}(\\{e^{i}_{j_{1}},\ldots,\allowbreak
e^{i}_{j_{t}}\\}),\allowbreak\text{head}(\\{e^{i}_{j_{t+1}},\ldots,\allowbreak
e^{i}_{j_{2t}}\\}))$ form a $t$-biclique in $D$.

Similarly, if the color of the monochromatic clique in
$\textnormal{{Aux}}_{i}$ is $(2,1)$, then
$(\text{tail}(\\{e^{i}_{j_{t+1}},\ldots,\allowbreak
e^{i}_{j_{2t}}\\}),\allowbreak\text{head}(\\{e^{i}_{j_{1}},\ldots,\allowbreak
e^{i}_{j_{t}}\\}))$ form a $t$-biclique in $H$. ∎

Thus, from Claims 4.12 and 4.10, and Observation 4.11, the lemma follows. ∎

###  4.2 Simplifying a biclique

In this section, we prove the following lemma. Recall that, from Section 4,
for positive integer $t,p$, $\mathcal{R}^{\prime}(t)$ is the smallest positive
integer such that any bipartite graph with a matching of size
$\mathcal{R}^{\prime}(t)$ either has an induced matching of size $t$ or a
$t$-induced-biclique. Furethermore
$f(t,p)=2^{\mathcal{R}^{\prime}(2t)}f(t,p-1)+\mathcal{R}^{\prime}(2t)$ when
$p>1$ and $f(t,1)=t$.

See 4.9

The remainder of this section is dedicated to the proof of Lemma 4.9. Recall
that $A,B$ are ordered sets. Let $g(t)=f(t,\mathcal{R}(2t,2))$. Further let
$A=(a_{1},\ldots,a_{g(t)})$ and $B=(b_{1},\ldots,b_{g(t)})$.

We begin by showing that, one can assume without loss of generality that $D$
is acyclic. Suppose that $D$ is not acyclic. First observe that for any
$a_{i},a_{j}\in A$, such that $i\neq j$, $a_{i}$ and $a_{j}$ belong to
different strongly connected components of $D$. Similarly, each vertex of $B$
belongs to a distinct strongly connected component of $D$. Further, for any
$a_{i},b_{j}$, $a_{i}$ and $b_{j}$ do not belong to the same strongly
connected component of $D$. Indeed, as otherwise there is a
$(b_{j},a_{i})$-path in $D$ contracting the definition of an $(A,B)$-biclique.
Thus, each vertex in $\\{a_{1},\ldots,a_{g(t)},b_{1},\ldots,b_{g(t)}\\}$
belong to distinct strongly connected components of $D$. Let $D^{\prime}$ be
obtained from $D$ by contracting each strongly connected component of $D$ into
a single vertex. That is, $D^{\prime}$ has a vertex for each strongly
connected component of $D$ and for two vertices $u,v$ in $D^{\prime}$, there
is an edge from $u$ to $v$ in $D^{\prime}$ if there is vertex in the strongly
connected component of $D$ which was contracted onto $u$, that has an edge in
$D$ to a vertex of the strongly connected component of $D$ which was
contracted to $v$. Let us call a vertex of $D^{\prime}$ $a_{i}$ if it is
obtained by contracting a strongly connected component containing $a_{i}$.
Similarly, let us call a vertex of $D^{\prime}$ $b_{i}$ if it is obtained by
contracting a strongly connected component containing $b_{i}$. It is easy to
observe that $D^{\prime}$ also contains an $(A,B)$-matching and
$D^{\prime\star}$ contains an $(A,B)$-induced-biclique. Indeed, since an
$(a_{i},b_{j})$-path in $D$ implies an $(a_{i},b_{j})$-path in $D^{\prime}$
and no $(a_{i},a_{j})$-path (resp. no $(b_{i},b_{j})$-path) in $D$ implies no
$(a_{i},a_{j})$-path (resp. no $(b_{i},b_{j})$-path) in $D^{\prime}$. Further
if $D^{\prime}$ contains an $(a_{i},b_{i})$-path of length strictly greater
than $1$ then so does $D$. Since $D^{\prime}$ is obtained by contraction
operation from $D$, we conclude that without loss of generality, we can assume
for the rest of the section that the input graph $D$ in Lemma 4.9 is acyclic.

We say that an edge $e\in E(D)\setminus E(A,B)$ is contraction-redundant with
respect to $(A,B)$ in $D$ if the following holds.

  1. 1.

If $D/e$ is acyclic,

  2. 2.

all the edges in $\\{(a_{i},b_{i}):i\in[g(t)]\\}$ (that is the matching edges
of $(A,B)$) are minimal edges in $D/e$, and

  3. 3.

$(D/e)^{\star}$ has an $(A,B)$-induced-biclique..

Let $D_{\textnormal{{contr}}}$ be the graph obtained from $D$ by repeatedly
contracting the contraction-redundant edges with respect to $(A,B)$ until
$D_{\textnormal{{contr}}}$ has no such edge. For the ease of notation by
$aa$-path we mean a path between two distinct vertices of $A$, by $bb$-path we
mean a path between two distinct vertices of $B$ and by
$a_{\ast}b_{\ast}$-path we mean a $(a_{i},b_{i})$-path for some $i\in[g(t)]$.
We divide the proof of Lemma 4.9 into two independent parts based on the
length of a longest path in $D_{\textnormal{{contr}}}$. In Section 4.2.1, we
consider the case when the length of a longest path in $D_{contr}$ is at least
$2t+2$. In this case, we show that $D_{\textnormal{{contr}}}$ contains an
ordered $t$-tough-pair. In Section 4.2.2, we consider the case when the length
of any longest path in $D_{\textnormal{{contr}}}$ is at most $2t+2$. In this
case, we get one of the desired outputs.

####  4.2.1 When $D_{\textnormal{{contr}}}$ has a long path

In this section, we prove Lemma 4.9 when the length of a longest path in
$D_{\textnormal{{contr}}}$ is at least $2t+2$. Let $P=(v_{1},\ldots,v_{p})$ be
a directed longest path in $D_{\textnormal{{contr}}}$ (then $p\geq 2t+2$).
Recall that none of the edges of $D_{\textnormal{{contr}}}$, and in
particular, none of the edges of $P$, are contraction-redundant with respect
to $(A,B)$.

######  Lemma 4.13.

For each $e\in E(P)$, $D_{\textnormal{{contr}}}/e$ is acyclic.

###### Proof.

Suppose, for the sake of contradiction, that there is a cycle in
$D_{\textnormal{{contr}}}/e$. Let $e=(v_{i},v_{i+1})$. Then, either there is a
$(v_{i},v_{i+1})$-path in $D_{\textnormal{{contr}}}-\\{(v_{i},v_{i+1})\\}$ or
a $(v_{i+1},v_{i})$-path in $D_{\textnormal{{contr}}}$. If there exists a
$(v_{i+1},v_{i})$-path in $D_{\textnormal{{contr}}}$ then together with the
edge $e=(v_{i},v_{i+1})$, it creates a directed closed walk in
$D_{\textnormal{{contr}}}$. This contradicts that $D_{\textnormal{{contr}}}$
is acyclic.

In the other case, suppose there exists a $(v_{i},v_{i+1})$-path, say
$P^{\prime}$ in $D_{\textnormal{{contr}}}-\\{(v_{i},v_{i+1})\\}$. We first
claim that the internal vertices of $P^{\prime}$ are disjoint from $P$.
Suppose not, let $v_{j}\in V(P)$ be the first internal vertex of $P^{\prime}$
that belongs to $P$. Then there is a $(v_{i},v_{j})$-path in
$D_{\textnormal{{contr}}}$ and $(v_{j},v_{i+1})$-path in
$D_{\textnormal{{contr}}}$. If $j<i$, then the $(v_{i},v_{j})$-path together
with the $(v_{j},v_{i})$-subpath of $P$, gives a closed walk in
$D_{\textnormal{{contr}}}$, contradicting its acyclicity. Otherwise, $j>i+1$.
In this case, the $(v_{j},v_{i+1})$-path together with the
$(v_{i+1},v_{j})$-subpath of $P$ gives a closed walk in
$D_{\textnormal{{contr}}}$, again contradicting its acyclicity. ∎

Since each edge of $D_{\textnormal{{contr}}}$, in particular, each edge of
$P$, is not contraction-redundant, from Lemma 4.13 and the definition of
contraction-redundant, for each $e\in E(P)$ either

  1. 1.

there exists an $aa$-path, or a $bb$-path in $D_{\textnormal{{contr}}}/e$
(that is, $(D_{\textnormal{{contr}}}/e)^{\star}$ does not contain the $(A,B)$
-induced-biclique), or

  2. 2.

there exists $i\in[g(t)]$ an $a_{i}b_{i}$-path in
$(D_{\textnormal{{contr}}}/e)-\\{(a_{i},b_{i})\\}$ ($(a_{i},b_{i})$ is not a
minimal edge in $D_{\textnormal{{contr}}}/e$).

######  Lemma 4.14.

Let $e=(v_{i},v_{i+1})\in E(P)$ such that $H_{contr}/e$ has an
$(a_{j},b_{j})$-path. Then there exists an $(a_{j},v_{i+1})$-path and a
$(v_{i},b_{j})$-path in $D_{\textnormal{{contr}}}$.

If $D_{\textnormal{{contr}}}/e$ has a $(a_{j},a_{\ell})$-path, for some
$a_{j},a_{\ell}\in A$, then there exists an $(a_{j},v_{i+1})$-path and a
$(v_{i},a_{\ell})$-path in $D_{\textnormal{{contr}}}$.

If $D_{\textnormal{{contr}}}/e$ has a $(b_{j},b_{\ell})$-path, for some
$b_{j},b_{\ell}\in B$, then there exists an $(b_{j},v_{i+1})$-path and
$(v_{i},b_{\ell})$-path in $D_{\textnormal{{contr}}}$.

###### Proof.

Let $e=(v_{i},v_{i+1})\in E(P)$ such that $D_{contr}/e$ has an
$(a_{j},b_{j})$-path. Then either there exists an $(a_{j},v_{i})$-path and a
$(v_{i+1},b_{j})$-path in $D_{\textnormal{{contr}}}$, or there exists an
$(a_{j},v_{i+1})$-path and $(v_{i},b_{j})$-path in $D_{\textnormal{{contr}}}$.
In the later case, we are done. The former case implies an
$(a_{j},b_{j})$-path in $D_{\textnormal{{contr}}}$ of length at least three
(with at least three edges), which contradicts that $(a_{j},b_{j})$ is a
minimal edge in $D_{\textnormal{{contr}}}$.

If $D_{contr}/e$ has an $(a_{j},a_{\ell})$-path, then either there exists an
$(a_{j},v_{i})$-path and a $(v_{i+1},a_{\ell})$-path in
$D_{\textnormal{{contr}}}$, or there exists an $(a_{j},v_{i+1})$-path and
$(v_{i},a_{\ell})$-path in $D_{\textnormal{{contr}}}$. In the later case, we
are done. The former case implies an $(a_{j},a_{\ell})$-path in
$D_{\textnormal{{contr}}}$ which contradicts that $(A,B)$ is an induced
biclique in $D_{\textnormal{{contr}}}^{\star}$ (in particular, that $A$ is an
independent set in $D_{\textnormal{{contr}}}^{\star}$). One can similarly show
that if $D_{contr}/e$ has a $(b_{j},b_{\ell})$-path, then there exists an
$(b_{j},v_{i+1})$-path and $(v_{i},b_{\ell})$-path in
$D_{\textnormal{{contr}}}$. ∎

For each $e=(v_{i},v_{i+1})\in E(P)$, we say that:

  1. 1.

$e$ is $j$-irredundant in $D_{\textnormal{{contr}}}$, if there is an
$(a_{j},v_{i+1})$-path and a $(v_{i},b_{j})$-path in
$D_{\textnormal{{contr}}}$.

  2. 2.

$e$ is $aa$-irredundant in $D_{\textnormal{{contr}}}$, if there exists
$a_{j},a_{\ell}\in A$ such that there is an $(a_{j},v_{i+1})$-path and a
$(v_{i},a_{\ell})$-path in $D_{\textnormal{{contr}}}$.

  3. 3.

$e$ is $bb$-irredundant in $D_{\textnormal{{contr}}}$, if there exists
$b_{j},b_{\ell}\in B$ such that there is an $(b_{j},v_{i+1})$-path and
$(v_{i},b_{\ell})$-path in $D_{\textnormal{{contr}}}$.

From Lemmas 4.13 and 4.18, for each $e\in E(P)$, either $e$ is
$j$-irredundant, for some $j\in[g(t)]$, or is $aa$-irredundant or is
$bb$-irredundant.

######  Lemma 4.15.

Let $e=(v_{i},v_{i+1})\in E(P)$ such that $e$ is $aa$-irredundant in
$D_{\textnormal{{contr}}}$. Then $i=1$.

###### Proof.

For the sake of contradiction, suppose that $i>1$. Let
$e^{\prime}=(v_{i-1},v_{i})$. If $e^{\prime}$ is $aa$-irredundant or
$e^{\prime}$ is $j$-irredundant for some $j\in[g(t)]$, then there exists a
path from some vertex of $A$ to $v_{i}$ in $D_{\textnormal{{contr}}}$. Also
since $e$ is $aa$-irredundant, there exists a path from $v_{i}$ to some vertex
of $A$ in $D_{\textnormal{{contr}}}$. This implies either a directed closed
walk in $D_{\textnormal{{contr}}}$, contradicting its acyclicity, or a path
between two distinct vertices of $A$ in $D_{\textnormal{{contr}}}$,
contradicting that $A$ is an independent set in
$D_{\textnormal{{contr}}}^{\star}$.

If $e^{\prime}$ is $bb$-irredundant, then there exists a path from some vertex
of $B$ to $v_{i}$. Also since $e$ is $aa$-irredundant, there exists a path
from $v_{i}$ to some vertex of $A$. This implies a path from some vertex of
$B$ to some vertex of $A$. Since $(A,B)$ is an induced biclique in
$D_{\textnormal{{contr}}}^{\star}$, that is there is a path from every vertex
of $A$ to every vertex of $B$ in $D_{\textnormal{{contr}}}$, this implies a
directed closed walk in $D_{\textnormal{{contr}}}$, contradicting its
acyclicity. ∎

######  Lemma 4.16.

Let $e=(v_{i},v_{i+1})\in E(P)$ such that $e$ is $bb$-irredundant in
$D_{\textnormal{{contr}}}$. Then $i+1=p$.

###### Proof.

For the sake of contradiction, suppose that $i+1<p$. Let
$e^{\prime}=(v_{i+1},v_{i+2})$. If $e^{\prime}$ is $bb$-irredundant or
$e^{\prime}$ is $j$-irredundant for some $j\in[g(t)]$, then there exists a
path from $v_{i+1}$ to some vertex of $B$. Also since $e$ is $bb$-irredundant,
there exists a path from some vertex of $B$ to $v_{i+1}$. This either implies
a directed closed walk in $D_{\textnormal{{contr}}}$, contradicting its
acyclicity, or a path between two distinct vertices of $B$ in
$D_{\textnormal{{contr}}}$, contradicting that $B$ is an independent set in
$D_{\textnormal{{contr}}}^{\star}$.

If $e^{\prime}$ is $aa$-irredundant, then there exists a path from $v_{i+1}$
to some vertex of $A$ in $D_{\textnormal{{contr}}}$. Also since $e$ is
$bb$-irredundant, there exists a path from some vertex of $B$ to $v_{i+1}$ in
$D_{\textnormal{{contr}}}$. This implies a path from some vertex of $B$ to
some vertex of $A$ in $D_{\textnormal{{contr}}}$. Since $(A,B)$ is an induced-
biclique in $D_{\textnormal{{contr}}}^{\star}$, this implies a directed closed
walk in $D_{\textnormal{{contr}}}$, contradicting its acyclicity. ∎

Let $P^{\prime}$ be a subpath obtained from $P$ by without the first and last
edge of $P$, that is $P^{\prime}=(v_{2},\ldots,v_{p-1})$. From Lemmas 4.15 and
4.16, each edge $e\in E(P^{\prime})$ is $j$-irredundant for some $j\in[g(t)]$.

######  Lemma 4.17.

Let $e,e^{\prime}$ be distinct edges of $P^{\prime}$ such that $e$ is
$q$-irredundant in $D_{\textnormal{{contr}}}$ and $e^{\prime}$ is
$r$-irredundant in $D_{\textnormal{{contr}}}$, for some $q,r\in[g(t)]$. Then
$q\neq r$.

###### Proof.

For the sake of contradiction, suppose that $q=r$. Without loss of generality,
let $e=(v_{i},v_{i+1})$ and $e^{\prime}=(v_{j},v_{j+1})$ such that $i<j$. Then
there exists an $(a_{q},v_{i+1})$-path and $(v_{j},b_{q})$-path in
$D_{\textnormal{{contr}}}$. Since $i<j$, there exists a path from
$(v_{i},v_{j})$ (which is the the $(v_{i+1},v_{j})$-subpath of $P^{\prime}$)
in $D_{\textnormal{{contr}}}$. This implies an $(a_{q},b_{q})$-path of length
strictly greater than one in $D_{\textnormal{{contr}}}$, contradicting that
$(a_{q},b_{q})$ is a minimal edge in $D_{\textnormal{{contr}}}$. ∎

For each $e=(v_{i},v_{i+1})\in E(P^{\prime})$, fix a $\rho(i)\in[g(t)]$, such
$e$ is $\rho(i)$-irredundant in $D_{\textnormal{{contr}}}$. The following
observation follows from Lemma 4.17.

######  Observation 4.18.

For each $v_{i}\in V(P^{\prime})$, $i\in[3,p-2]$, there exists a
$(a_{\rho(i-1)},v_{i})$-path and a $(v_{i},b_{\rho(i)})$-path in
$D_{\textnormal{{contr}}}$. Also, for $i,j\in[3,p-2]$, $i\neq j$,
$\rho(i)\neq\rho(j)$.

For each $i\in[3,p-2]$, let $P^{\texttt{a}}_{i}$ denote an (arbitrarily) fixed
$(a_{\rho(i-1)},v_{i})$-path in $D_{\textnormal{{contr}}}$ and let
$P^{\texttt{b}}_{i}$ denote an (arbitrarily) fixed $(v_{i},b_{\rho(i)})$-path
in $D_{\textnormal{{contr}}}$. Let
$E_{1}=(v_{3},b_{\rho(3)}),\allowbreak(v_{4},b_{\rho(4)}),\ldots,\allowbreak(v_{p/2-2},b_{\rho(p/2-2)})$
and let
$E_{2}=((a_{\rho(p/2-2)},v_{p/2-1}),\allowbreak(a_{\rho(p/2-1)},\allowbreak
v_{p/2}),\ldots,(a_{\rho(p-1)},\allowbreak v_{p-2})$. From Observation 4.18,
each edge of $E_{1}\cup E_{2}$ is an edge in
$D^{\star}_{\textnormal{{contr}}}$ and the endpoints of the edges in
$E_{1}\cup E_{2}$ are distinct. We will now show that $(E_{1},E_{2})$ is an
ordered $(p/2-1)$-tough-pair in $D^{\star}_{\textnormal{{contr}}}$. Since
$p\geq 2t+2$, this proves Lemma 4.9 in the case when the length of a longest
path in $D_{\textnormal{{contr}}}$ is at least $2t+2$.

######  Lemma 4.19.

$(E_{1},E_{2})$ is an ordered $(p/2-1)$-tough-pair in
$D^{\star}_{\textnormal{{contr}}}$.

###### Proof.

To prove the lemma, we prove the following claims.

######  Claim 4.20 (Weak independence of $E_{1}$ (resp. $E_{2}$)).

The edges in $E_{1}$ are pairwise weakly independent. Similarly, the edges in
$E_{2}$ are pairwise weakly independent in $D^{\star}_{\textnormal{{contr}}}$.

###### Proof.

Let $(a_{\rho(i-1)},{v}_{i}),\allowbreak(a_{\rho(j-1)},{v}_{j})\in E_{1}$. For
the sake of contradiction, say $(v_{j},a_{\rho(i-1)})\in
D_{\textnormal{{contr}}}^{\star}$. Then this implies a
$(a_{\rho(j-1},a_{\rho(i-1)})$-path in $D_{\textnormal{{contr}}}^{\star}$
contradicting that $A$ is an independent set in
$D_{\textnormal{{contr}}}^{\star}$. Using symmetric arguments one can show
that all edges in $E_{2}$ are pairwise weakly independent. ∎

######  Claim 4.21 (Orderedness on $E_{1}$ and $E_{2}$).

For any $i,j\in[3,p-2]$, $i<j$,
$(a_{\rho(j-1)},v_{i}),\allowbreak(a_{\rho(j-1)},a_{\rho(i-1)}),\allowbreak({v}_{j},\allowbreak
b_{\rho(i)}),\allowbreak(v_{j},v_{i})\not\in
E(D_{\textnormal{{contr}}}^{\star})$.

###### Proof.

Since $A$ is an independent set in $D_{\textnormal{{contr}}}^{\star}$,
$(a_{\rho(j-1)},a_{\rho(i-1)})\not\in E(D_{\textnormal{{contr}}}^{\star})$.
Since $D_{\textnormal{{contr}}}^{\star}$ is acyclic and there is a
$(v_{i},v_{j})$-path in $D_{\textnormal{{contr}}}$, we conclude that
$(v_{j},v_{i})\not\in E(D_{\textnormal{{contr}}}^{\star})$. If there is an
$(a_{\rho(j-1)},{v}_{i})$-path in $D_{\textnormal{{contr}}}$, then this
together with the $({v}_{i},v_{j-1})$-subpath of $P^{\prime}$ and the
$(v_{i-1},b_{\rho(i-1)})$ path $P^{\texttt{b}}_{i-1}$, implies a
$(a_{\rho(j-1),b_{\rho(j-1)}})$-path of length strictly greater than $1$ in
$D_{\textnormal{{contr}}}$, which is a contradiction. Using symmetric
arguments, one can show that $({v}_{j},b_{\rho(i)}),(v_{j},v_{i})\not\in
E(D_{\textnormal{{contr}}}^{\star})$. ∎

######  Claim 4.22 (Weak independence between $E_{1}$ and $E_{2}$).

Let $(v_{i},b_{\rho(i)})\in E_{1}$ and $(a_{\rho(j-1)},v_{j})\in E_{2}$. There
is $(v_{j},b_{\rho(i)}),(b_{\rho(i)},a_{\rho(i-1)})\not\in
E(D_{\textnormal{{contr}}}^{\star})$.

###### Proof.

First observe from the construction of $E_{1},E_{2}$ that $i<j$. If
$(v_{j},b_{\rho(i)})\in E(D_{\textnormal{{contr}}}^{\star})$, then the
$(a_{\rho(i)},v_{i+1})$-path $P^{\texttt{a}}_{i+1}$, together with the
$(v_{i+1},v_{j})$-subpath of $P^{\prime}$, together with the
$(v_{j},b_{\rho(i)})$-path, implies a $(a_{\rho(i)},b_{\rho(i)})$-path of
length strictly greater than $1$ in $D_{\textnormal{{contr}}}$, which is a
contradiction.

If $(b_{\rho(i)},a_{\rho(i-1)})\in E(D_{\textnormal{{contr}}}^{\star})$, then
the $(a_{rho(i-1)},b_{\rho(i)})$-path obtained by concatenating
$P^{\texttt{a}}_{i}$ and $P^{\texttt{b}}_{i}$, together with the
$(b_{\rho(i)},a_{\rho(i-1)})$-path, implies a
$(a_{\rho(i-1)},a_{\rho(j-1)})$-path in $D_{\textnormal{{contr}}}$, which
contradicts that $A$ is an independent set in $D_{\textnormal{{contr}}}$. ∎

######  Claim 4.23 (Strong independence between $E_{1}$ and $E_{2}$).

Let $(v_{i},b_{\rho(i)})\in E_{1}$ and $(a_{\rho(j-1)},v_{j})\in E_{2}$. Then
$(v_{i},a_{\rho(j-1}),\allowbreak(a_{\rho(j-1)},v_{i}),\allowbreak(b_{\rho(i)},v_{j}),\allowbreak(v_{j},b_{\rho(i)})\not\in
E(D_{\textnormal{{contr}}}^{\star})$.

###### Proof.

Recall that $i>j$. If $(v_{i},a_{\rho(j-1)})\in
E(D_{\textnormal{{contr}}}^{\star})$, then together with $P^{\texttt{a}}_{i}$,
it contradicts that $A$ is independent in $D_{\textnormal{{contr}}}^{\star}$.
Similarly, if $(b_{\rho(i)},v_{j})\in E(D_{\textnormal{{contr}}}^{\star})$,
then it contradicts the independence of $B$ in
$D_{\textnormal{{contr}}}^{\star}$.

If $(a_{\rho(j-1)},v_{i})\in E(D_{\textnormal{{contr}}}^{\star})$, then this
together with the $(v_{i},v_{j-1})$-subpath of $P^{\prime}$, together with the
path $P^{\texttt{b}}_{j-1}$, implies a $(a_{\rho(j-1)},b_{\rho(j-1)})$-path of
length strictly greater than $1$ in $D_{\textnormal{{contr}}}$, which is a
contradiction. Similarly if, $(v_{j},b_{\rho(i)})\in
E(D_{\textnormal{{contr}}}^{\star})$, then this implies a
$(a_{\rho(i)},b_{\rho(i)})$-path of length strictly greater than $1$ in
$D_{\textnormal{{contr}}}$, which is a contradiction. ∎

This concludes the proof. ∎

####  4.2.2 No long path in $D_{\textnormal{{contr}}}$

In this section, we prove Lemma 4.9 in the case when the length of a longest
path in $D_{\textnormal{{contr}}}$ is $p\leq 2t+2$. Recall that
$D_{\textnormal{{contr}}}$ contains $(A,B)$-matching and
$D_{\textnormal{{contr}}}^{\star}$ contains $(A,B)$-induced-biclique. Also,
the edges of $A\cup B$ are minimal in $D_{\textnormal{{contr}}}$. We prove
Lemma 4.9 by induction on the length of a longest $(A,B)$-path in
$D_{\textnormal{{contr}}}$. For this purpose we essentially restate Lemma 4.9
in a form that is “induction-friendly”. Observe, as a base case, that when the
length of a longest $(A,B)$-path is $1$, then since
$D_{\textnormal{{contr}}}^{\star}$ contains $(A,B)$-induced-biclique, we
conclude that $D_{\textnormal{{contr}}}$ contains $(A,B)$-induced-biclique and
the edges of the $(A,B)$-induced-biclique are minimal. In this case, we
conclude that we get the second output of Lemma 4.9.

######  Lemma 4.24.

Let $A,B\subseteq V(D_{\textnormal{{contr}}})$ be ordered sets such that the
length of a longest $(A,B)$-path in $D_{\textnormal{{contr}}}$ is $p$,
$|A|=|B|\geq f(t,p)$, $D_{\textnormal{{contr}}}^{\star}$ contains an
$(A,B)$-induced-biclique and the matching edges of $(A,B)$ are minimal in
$D_{\textnormal{{contr}}}$, then either

  1. 1.

there exist ordered sets $A^{\prime},B^{\prime}\subseteq
V(D_{\textnormal{{contr}}})$ such that the length of a longest
$(A^{\prime},B^{\prime})$-path in $D_{\textnormal{{contr}}}$ is at most $p$,
$|A^{\prime}|=|B^{\prime}|\geq f(t,p-1)$, $D_{\textnormal{{contr}}}^{\star}$
contains an $(A^{\prime},B^{\prime})$-induced-biclique and the matching edges
of $(A^{\prime},B^{\prime})$ are minimal in $D_{\textnormal{{contr}}}$, or

  2. 2.

$D_{\textnormal{{contr}}}$ contains an ordered $t$-tough-pair, or

  3. 3.

$D_{\textnormal{{contr}}}^{\star}$ contains a $t$-induced-biclique whose edges
are minimal in $D_{\textnormal{{contr}}}$.

###### Proof.

Let $L$ be the set of vertices of $D_{\textnormal{{contr}}}$ that contains the
first internal vertex on every longest $(A,B)$-path in
$D_{\textnormal{{contr}}}$.

######  Claim 4.25.

There is no $(L,L)$-path in $D_{\textnormal{{contr}}}$.

###### Proof.

For the sake of contradiction, suppose there exist $x,y\in L$ such that there
this an $(x,y)$-path in $D_{\textnormal{{contr}}}$. Note that $x\neq y$, as
otherwise, $D_{\textnormal{{contr}}}$ would contain a cycle. From the
definition of $L$, there exists $a_{i},a_{j}\in L$ ($i$ not necessarily
distinct from $j$) such that $x$ is the first internal vertex on some
$(a_{i},B)$-path, say $P_{x}$, of length $p$ and $y$ is the first internal
vertex on some $(a_{j},B)$-path, say $P_{y}$, of length $p$. Let $P_{xy}$ be
some $(x,y)$-path in $D_{\textnormal{{contr}}}$. We first claim that the set
of internal vertices of $P_{x,y}$ is disjoint from $P_{y}$. Suppose not. Let
$z$ be some internal vertex of $P_{xy}$ that is also a vertex of $P_{y}$.
Since $z\in V(P_{y})$, there exists a $(y,z)$-path in
$D_{\textnormal{{contr}}}$. Also since $z\in V(P_{x,y})$, there exists a
$(z,y)$-path in $D_{\textnormal{{contr}}}$. This implies a cycle in
$D_{\textnormal{{contr}}}$, which is a contradiction. Thus, we conclude that
the internal vertices of $P_{xy}$ are disjoint from that of $P_{y}$. Then
consider the $(x,B)$-path obtained by appending $P_{xy}$ and $P_{y}$. Note
that the length of $P_{y}$ is $p-1$ and the length of $P_{xy}$ is at least
$1$. This $(x,B)$-path, together with the edge $(a_{i},x)$, gives an
$(a_{i},B)$-path of length strictly greater than $p$ in
$D_{\textnormal{{contr}}}$, which contradicts that the length of a longest
$(A,B)$-path in $D_{\textnormal{{contr}}}$ is $p$. ∎

######  Claim 4.26.

For each $(a,x)\in E(D_{\textnormal{{contr}}})$ such that $a\in A$ and $x\in
L$, $(a,x)$ is a minimal edge of $D_{\textnormal{{contr}}}$.

###### Proof.

For the sake of contradiction, say there exists an $(a,x)$-path in
$D_{\textnormal{{contr}}}$ of length at least $2$. Let this path be $P_{ax}$.
Since $x\in L$, there exists an $(A,B)$-path of length $p$ whose first
internal vertex is $x$. Let this path be $P_{AB}$. Then the internal vertices
of $P_{ax}$ are disjoint from the internal vertices of $P_{AB}$, as otherwise
there would be a cycle in $D_{\textnormal{{contr}}}$. By appending the path
$P_{sx}$ (which is of length at least $2$) with the subpath of $P_{ABs}$
starting from $x$ (which is of length $p-1$), we get an $(A,B)$-path in
$D_{\textnormal{{contr}}}$ of length at least $p+1$, which is a contradiction.
∎

######  Claim 4.27.

Let $a\in A$ and $x\in L$, such that $(a,x)\not\in
E(D_{\textnormal{{contr}}})$. Then $(a,x)\not\in
E(D_{\textnormal{{contr}}}^{\star})$.

###### Proof.

For the sake of contradiction, suppose there exists an $(a,x)$-path, say
$P_{a,x}$ in $D_{\textnormal{{contr}}}$ of length at least two. Since $x\in
L$, there exists $a^{\prime}\in A$ ($a^{\prime}$ not necessarily distinct from
$a$) such that $x$ is the first internal vertex of a $(a^{\prime},T)$-path,
say $P_{a^{\prime}B}$, of length $p$. First observe that the internal vertices
of $P_{a,x}$ are disjoint from that of $P_{a^{\prime}B}$, as otherwise there
would be a cycle in $D_{\textnormal{{contr}}}$. The path $P_{a,x}$ appended
with the $(x,B)$-subpath of $P_{a^{\prime}B}$ gives an $(A,B)$-path in
$D_{\textnormal{{contr}}}$ of length strictly greater than $p$, which is a
contradiction. ∎

Consider the bipartite graph $D_{\texttt{bip}}=D_{\textnormal{{contr}}}[A\cup
L]$. Note, from Claim 4.26, that each edge of $D_{\texttt{bip}}$ is a minimal
edge in $D_{\textnormal{{contr}}}$. We now distinguish into two cases based on
the size of the matching in $D_{\texttt{bip}}$.

Case 1: The size of a maximum matching in $D_{\texttt{bip}}$ is at least
$\mathcal{R}^{\prime}(2t)$. In this case, from Ramsey’s Theorem, either there
exists an induced matching of size $2t$ in $D_{\texttt{bip}}$ or a
$2t$-induced-biclique. From Claim 4.26, each edge of $D_{\texttt{bip}}$ is a
minimal edge of $D_{contr}$.

In the first case, we get sets $A^{*}\subseteq A$ and $B^{*}\subseteq L$ such
that there is an $(A^{*},B^{*})$-induced-matching in $D_{\texttt{bip}}$. Since
$A$ is an independent set in $D_{\textnormal{{contr}}}^{\star}$, so is
$A^{*}$. Since $B^{*}\subseteq L$, from Claim 4.26, $B^{*}$ is an independent
set in $D_{\textnormal{{contr}}}^{\star}$. Thus, $(A^{*},B^{*})$ is an
induced-matching in $D_{\textnormal{{contr}}}$. Further, from Claim 4.27,
$(A^{*},B^{*})$ is in fact an induced matching in
$D_{\textnormal{{contr}}}^{\star}$. Observe that if a digraph has an induced-
matching of size $2t$ in its transitive closure, then it has a ordered
$t$-tough-pair. Thus, in this case we get the second outcome of the lemma.

In the second case, when $H_{\texttt{bip}}$ contains a $2t$-induced-biclique,
then this is also a $2t$-induced-biclique in $D_{\textnormal{{contr}}}$ where
all edges of the biclique are minimal edges of $D_{\textnormal{{contr}}}$.
Thus, in this case we get the third outcome of the lemma.

Case 2: The size of a maximum matching in $D_{\texttt{bip}}$ is at most
$\mathcal{R}^{\prime}(2t)$. In this case, we will find ordered sets
$A^{\prime},B^{\prime}\subseteq V(D_{\textnormal{{contr}}})$ satisfies the
properties stated in the first outcome of the lemma.

Let $Z$ be a minimum vertex cover of $D_{\texttt{bip}}$ of size at most
$\mathcal{R}^{\prime}(2t)$. Let $Z_{A}=Z\cap A$ and $Z_{L}=Z\cap L$. Let
$A^{*}=A\setminus Z_{S}$. Since $Z_{A}\cup Z_{L}$ is a vertex cover of
$D_{\texttt{bip}}$, for any $a\in A^{*}$, $N_{L}(a)\subseteq Z_{L}$. For each
subset $L^{\prime}\subseteq Z_{L}$, let $A_{L^{\prime}}\subseteq A^{*}$ such
that for each vertex $a\in A_{L^{\prime}}$, $N_{Z_{L}}(a)=L^{\prime}$ (and
hence $N_{L}(a)=L^{\prime}$).

Fix $L^{\prime}\subseteq Z_{L}$ such that $|S_{L^{\prime}}|$ is maximized.
Recall that the sets $A=(a_{1},\ldots,a_{f(t,p)})$ and
$T=(t_{1},\ldots,t_{f(t,p)})$ are ordered sets. Set
$A^{\prime}=A_{L^{\prime}}$ and $B^{\prime}$ be the corresponding vertices of
$B$, that is $b_{i}\in B^{\prime}$ if and only if $a_{i}\in A^{\prime}$. From
the choice of $L^{\prime}$,
$|A^{\prime}|=|B^{\prime}|\geq(|A|-\mathcal{R}^{\prime}(2t))/2^{\mathcal{R}^{\prime}(2t)}=f(t,p-1)$.
We will now show that the length of a longest $(A^{\prime},B^{\prime})$-path
in $D_{\textnormal{{contr}}}$ is at most $p-1$.

######  Claim 4.28.

Let $a_{i}\in A^{\prime}$ and $b_{j}\in B^{\prime}$ such that $i\neq j$. Let
$P=(a_{i},x_{1},\ldots,x_{q},b_{j})$ be a longest
$(A^{\prime},B^{\prime})$-path in $D_{\textnormal{{contr}}}$. Then
$x_{1}\not\in L$.

###### Proof.

Since $b_{j}\in B^{\prime}$, $a_{j}\in A^{\prime}$ (from construction of
$B^{\prime}$). First observe that since $b_{j}\in B^{\prime}$, then $a_{j}\in
A^{\prime}$. For the sake of contradiction, suppose $x_{1}\in L$. Since
$(a_{i},x)\in E(D_{\textnormal{{contr}}})$ and all the vertices of
$A^{\prime}$ have the same neighbourhood in $Z_{L}$ and $a_{j}\in A^{\prime}$,
we conclude that $(a_{j},x)\in E(D_{\textnormal{{contr}}})$. Thus, there is an
$(a_{j},b_{j})$-path in $D_{\textnormal{{contr}}}$ of length strictly greater
than one, which contradicts that $(a_{j},b_{j})$ is a minimal edge of
$D_{\textnormal{{contr}}}$. ∎

From Claim 4.28, the first internal vertex of every longest
$(A^{\prime},B^{\prime})$-path is not contained in $L$. Now suppose that there
exists an $(A^{\prime},B^{\prime})$-path of length $p$. Then its first
internal vertex should be in $L$ by the definition of $L$. This is a
contradiction. ∎

Lemma 4.24 proves Lemma 4.9 when the length of the longest path $p\leq 2t+2$.

###  4.3 Cleaning the ordered tough-pair

The cleaning of ordered tough-pairs is done in two steps: we first show that
an ordered tough-pair can be identified to a so-called _semi-cleaned ordered
tough-pair_ (see Section 4.3.1) and show thereafter how to further identify a
semi-cleaned ordered tough-pair to a hard matching pattern (see Section
4.3.2).

####  4.3.1 Semi-cleaning

Recall the definition of a semi-cleaned ordered $t$-tough-pair from Section 4.
The goal of this section is to prove Lemma 4.5 restated below.

See 4.5

To prove Lemma 4.5, we first define a type of a vertex in $D$ with respect to
the ordered $t$-tough-pair $(A,B)$. This is based on the neighbourhoods of a
vertex in the head sets and tail sets of $A$ and $B$. We then define a notion
of a bad type. The vertices having a bad type hinder the semi-cleaning
procedure. To overcome this, we show that if a digraph $D$ contains an ordered
$t^{2}$-tough-pair then it also contains an ordered $t$-tough-pair
$(A^{\prime},B^{\prime})$ such that there are no bad vertices with respect to
$(A^{\prime},B^{\prime})$. We then show that given such an ordered tough-pair
$(A^{\prime},B^{\prime})$ we can identify the remaining vertices to one of the
endpoints of $A^{\prime}\cup B^{\prime}$.

##### Bad vertices with respect to the ordered tough-pair $(A,B)$.

Given an ordered tough-pair $(A,B)$ in a digraph $D$, we say that a vertex
$v\in V(D)\setminus V(A\cup B)$ is bad with respect to $(A,B)$ if $v\in
N^{+}_{D^{\star}}(\text{tail}(A))\cap N^{-}_{D^{\star}}(\text{head}(A))\cap
N^{+}_{D^{\star}}(\text{tail}(B))\cap N^{-}_{D^{\star}}(\text{head}(B))$.

######  Lemma 4.29 (Eliminating bad vertices).

Let $D$ be a digraph such that $D$ contains an ordered $t^{2}$-tough-pair.
Then $D$ contains an ordered $t$-tough-pair $(A^{\prime},B^{\prime})$ such
that there is no bad vertex in $V(D)\setminus V(A^{\prime}\cup B^{\prime})$
with respect to $(A^{\prime},B^{\prime})$.

###### Proof.

Let $(A,B)$ be an ordered $t^{2}$-tough-pair in $D$ and let
$t^{\prime}=t^{2}$. Let
$A=((w_{1},x_{1}),\ldots,(w_{t^{\prime}},x_{t^{\prime}}))$ and
$B=((y_{1},z_{1}),\ldots,(y_{t^{\prime}},z_{t^{\prime}}))$. For each vertex
$v\in V(H)\setminus V(A\cup B)$ which is bad with respect to $(A,B)$, let
$W(v)$ be the largest index in $[t^{\prime}]$ such that $(a_{W(v)},v)\in
E(D)$, $X(v)$ be the smallest index in $[t^{\prime}]$ such that
$(v,b_{X(v)})\in E(D)$, $Y(v)$ be the largest index in $[t^{\prime}]$ such
that $(c_{Y(v)},v)\in E(D)$, and $Z(v)$ be the smallest index in
$[t^{\prime}]$ such that $(v,d_{Z(v)})\in E(D)$. For every
$p,q\in[\sqrt{t^{\prime}}]$, let $V_{p,q}$ be the set of bad vertices $v$ with
respect to $(A,B)$ such that
$W(v),X(v)\in\\{(p-1)\sqrt{t^{\prime}}+1,\ldots,p\sqrt{t^{\prime}}\\}$, and
$Y(v),Z(v)\in\\{(q-1)\sqrt{t^{\prime}},\ldots,q\sqrt{t^{\prime}}\\}$.

If there exists $p,q\in[\sqrt{t^{\prime}}]$ such that $V_{pq}=\emptyset$, then
let
$A^{\prime}=((w_{(p-1)\sqrt{t^{\prime}}+1},x_{(p-1)\sqrt{t^{\prime}}}+1),\ldots,(x_{p\sqrt{t^{\prime}}},x_{p\sqrt{t^{\prime}}}))$
and
$B^{\prime}=((c_{(q-1)\sqrt{t^{\prime}}+1},z_{(q-1)\sqrt{t^{\prime}}+1}),\ldots,(c_{q\sqrt{t^{\prime}}},z_{q\sqrt{t^{\prime}}}))$.
Then from the definition of $V_{p,q}$, $(A^{\prime},B^{\prime})$ is an ordered
$\sqrt{t^{\prime}}$-tough-pair such that there are no bad vertices with
respect to it.

Without loss of generality, assume that for each $p,q\in[\sqrt{t^{\prime}}]$,
$V_{pq}\neq\emptyset$. Let $v_{p,q}$ denote an arbitrarily fixed vertex in
$V_{pq}$. Let
$A^{\prime}=((w_{W(v_{2,1}},v_{2,1}),\ldots,(w_{W(v_{\sqrt{t^{\prime}},1})},v_{\sqrt{t^{\prime}},1}))$
and
$B^{\prime}=((y_{Y(v_{1,2})},v_{1,2}),\ldots,(y_{Y(v_{\sqrt{t^{\prime}},1})},v_{1,\sqrt{t^{\prime}}}))$.
We will now show that $(A^{\prime},B^{\prime})$ is an ordered tough-pair in
$D$. Moreover, we will show that there is no
$(\text{tail}(B^{\prime}),\text{head}(A^{\prime}))$-path in $D$, thereby
concluding that there is no bad vertex with respect to
$(A^{\prime},B^{\prime})$. Note that the edges of $A^{\prime},B^{\prime}$ are
minimal edges because they belong to $D$ which is a reachability minimal
digraph.

##### Weak independence of $A^{\prime}$ (resp. $B^{\prime}$).

We show that there is no $(\text{head}(A^{\prime}),\text{tail}(A^{\prime}))$
path (resp. no $(\text{head}(B^{\prime}),\text{tail}(B^{\prime}))$ path) in
$D$. Recall that every vertex in $\text{head}(A^{\prime})$ is a bad vertex
with respect to $(A,B)$. Thus, each vertex of $\text{tail}(A^{\prime})$ is an
out-neighbour of some vertex of $\text{tail}(B^{\prime})$. Thus, a
$(\text{head}(A^{\prime}),\text{tail}(A^{\prime}))$-path in $D$ implies a
$(\text{tail}(B),\text{tail}(A^{\prime}))$-path in $D$. Since
$\text{tail}(A^{\prime})\subseteq\text{tail}(A)$, this contradicts that every
edge of $A$ is strongly independent with every edge of $B$. The other case is
symmetric.

##### Weak independence between $A^{\prime}$ and $B^{\prime}$.

We show that a pair of edges containing an edge of $A^{\prime}$ and an edge of
$B^{\prime}$ is weakly independent. To see that there is no
$(\text{head}(B^{\prime}),\text{tail}(A^{\prime}))$-path, recall that every
vertex of $\text{head}(B^{\prime})$ is a bad vertex with respect to $(A,B)$.
Thus, each vertex of $\text{head}(B^{\prime})$ is an out-neighbour of some
vertex of $\text{tail}(B)$. Thus, a
$(\text{head}(B^{\prime}),\text{tail}(A^{\prime}))$-path in $D$ implies a
$(\text{tail}(B),\text{head}(A^{\prime}))$-path in $D$. Since
$\text{tail}(A^{\prime})\subseteq\text{tail}(A)$, this is a contradiction. One
can symmetrically prove that there is no
$(\text{head}(A^{\prime}),\text{tail}(B^{\prime}))$-path.

##### Strong independence of $A^{\prime}$ and $B^{\prime}$.

We prove the following three statements.

There is no $(\text{tail}(A^{\prime}),\text{tail}(B^{\prime}))$-path and no
$(\text{tail}(B^{\prime}),\text{tail}(A^{\prime}))$-path. Since
$\text{tail}(A^{\prime})\subseteq\text{tail}(A)$ and
$\text{tail}(B^{\prime})\subseteq\text{tail}(B)$, and $(A,B)$ is a tough-pair,
we conclude that there is no
$(\text{tail}(A^{\prime}),\allowbreak\text{tail}(B^{\prime}))$-path and no
$(\text{tail}(B^{\prime}),\text{tail}(A^{\prime}))$-path.

There is no $(\text{head}(A^{\prime}),\text{head}(B^{\prime}))$-path. For the
sake of contradiction, suppose there exists
$v_{i,1}\in\text{head}(B^{\prime})$ and $v_{1,j}\in\text{head}(B^{\prime})$,
$i,j\neq 1$, such that there exists a $(v_{i,1},v_{1,j})$-path in $D$. By
definition $w(v_{i,1})\in\\{2\sqrt{t^{\prime}}+1,\ldots,t^{\prime}\\}$ and
$X(v_{1,j})\in\\{1,\ldots,\sqrt{t^{\prime}}\\}$. Also,
$(w_{W(v_{i,1})},v_{i,1})\in E(D)$ and $(v_{1,j},x_{X(v_{1,j})})\in E(D)$.
Thus, a $(v_{i,1},v_{1,j})$-path in $D$ implies a
$(w_{W(v_{i,1})},y_{Y(v_{1,j})})$-path in $D$. Since $X(v_{1,j})<W(v_{i,1})$,
this is a contradiction.

There is no $(\text{head}(B^{\prime}),\text{head}(A^{\prime}))$-path. For the
sake of contradiction, suppose there exists
$v_{i,1}\in\text{head}(A^{\prime})$ and $v_{1,j}\in\text{head}(B^{\prime})$,
$i,j\neq 1$, such that there exists a $(v_{1,j},v_{i,1})$-path in $D$. By
definition $Y(v_{1,j})\in\\{2\sqrt{t^{\prime}}+1,\ldots,t^{\prime}\\}$ and
$Z(v_{i,1})\in\\{1,\ldots,\sqrt{t^{\prime}}\\}$. Also,
$(y_{Y(v_{1,j})},v_{1,j})\in E(D)$ and $(v_{i,1},z_{Z(v_{i,1})})\in E(D)$.
Thus, a $(v_{1,j},v_{i,1})$-path in $D$ implies a
$(y_{Y(v_{1,j})},z_{Z(v_{i,1})})$-path in $D$. Since $Z(v_{i,1})<Y(v_{1,j})$,
this is a contradiction.

##### Ordered condition on $A^{\prime}$ (resp. $B^{\prime}$).

Consider vertices $v_{i,1}$ and $v_{j,1}$ such that $i\leq j$. Suppose for the
sake of contradiction that there exists a $(v_{j,1},v_{i,1})$-path in $D$.
Recall $(w_{W(v_{j,1})},v_{j,1})\in E(D)$ and $(v_{i,1},x_{X(v_{i,1})})\in
E(D)$. Thus, there exists a $(w_{W(v_{j,1})},y_{Y(v_{i,1})})$-path in $D$.
Since $i\leq j$, $W(v_{j,1})\leq X(v_{i,1})$. This is a contradiction. The
other case can be proved symmetrically.

##### There is no $(\text{tail}(B^{\prime}),\text{head}(A^{\prime}))$-path.

For the sake of contradiction, let $v_{i,1}\in\text{head}(A^{\prime})$, $i\neq
1$, and $y_{j}\in\text{tail}(B^{\prime})$ such that there exists a
$(y_{j},v_{i,1})$-path in $D$. Since $y_{j}\in\text{tail}(B^{\prime})$,
$j\in\\{2\sqrt{t^{\prime}}+1,\ldots,t^{\prime}\\}$. Also
$Z(v_{i,1})\in\\{1,\ldots,\sqrt{t}\\}$. Since $(v_{i,1},z_{Z(v_{i,1})})\in
E(D)$, we conclude that there is a $(y_{j},z_{Z(v_{i,1})})$-path. This is a
contradiction which concludes the proof. ∎

######  Lemma 4.30.

Let $D$ be a directed graph and let $(A,B)$ be an ordered $t$-tough-pair in
$D$ such that there are no bad vertices with respect to $(A,B)$ in $D$. Then
one can obtain a semi-cleaned ordered $t$-tough-pair from $D$ by
identification.

The remainder of this section is devoted to the proof of Lemma 4.30. Note that
Lemma 4.30, together with Lemma 4.29, proves Lemma 4.5.

Recall that $A,B$ are ordered sets. Let
$\text{tail}(A)=W=(w_{1},\ldots,w_{t})$,
$\text{head}(A)=X=(x_{1},\ldots,x_{t})$,
$\text{tail}(B)=Y=(y_{1},\ldots,y_{t})$ and
$\text{head}(B)=Z=(z_{1},\ldots,z_{t})$. We will now describe a procedure of
identifying vertices in $V(D)\setminus V(A\cup B)$ onto the vertices of
$V(A\cup B)$, as long as there is a vertex that has both an in-neighbour and
an out-neighbour in $V(A\cup B)=W\cup X\cup Y\cup Z$ in the graph $D^{*}$,
while maintaining the invariants that after the identification $(A,B)$ remains
an ordered tough-pair in the new graph, no vertex in the new graph is bad with
respect to $(A\cup B)$ and the new graph is acyclic. We will apply these
identification rules exhaustively, in order.

######  Invariants.

If $\widehat{D}$ is the graph obtained after identification, then $(A,B)$ is
an ordered tough-pair in $\widehat{D}$, and there are no bad vertices with
respect to $(A,B)$ in $\widehat{D}$.

######  Identification Rule 1.

If there exists $v\in V(D)\setminus(W\cup X\cup Y\cup Z)$ such that
$N_{D^{\star}}^{+}(v)\cap W\neq\emptyset$ and $N_{D^{\star}}^{-}(v)\cap
W\neq\emptyset$, then let $i\in[t]$ be the largest index such that
$(w_{i},v)\in E(D^{\star})$. Identify $v$ onto $w_{i}$.

######  Lemma 4.31.

Let $\widehat{D}$ be the graph obtained after the application of
Identification Rule 1. Then, the invariants are satisfied.

###### Proof.

Since $N_{D^{\star}}^{+}(v)\cap W\neq\emptyset$ and $N_{D^{\star}}^{-}(v)\cap
W\neq\emptyset$, there is a $(v,W)$-path, say $P_{\texttt{out}}$, and a
$(W,v)$-path say $P_{\texttt{in}}$ in $D$.

Weak independence of $A$ in $\widehat{D}$. For the sake of contradiction, say
there is a $(X,w_{i})$-path in $\widehat{D}$. Then there exists a $(X,v)$-path
in $D$. This, together with the $(v,W)$-path $P_{\texttt{out}}$, implies an
$(X,W)$-path in $D$, which is a contradiction to the weak independence of the
edges of $A$ in $D$.

Weak independence between $A,B$ in $\widehat{D}$. For the sake of
contradiction, say there is a $(Z,w_{i})$-path in $\widehat{D}$. Then there
exists a $(Z,v)$-path in $D$. This, together with $(v,W)$-path
$P_{\texttt{out}}$, implies an $(Z,W)$-path in $D$, which is a contradiction
to the weak independence between the edges of $A,B$ in $D$.

Strong independence between $A,B$ in $\widehat{D}$. For the sake of
contradiction, say there is a $(w_{i},Y)$-path in $\widehat{D}$. Then there
exists a $(v,Y)$-path in $D$. This, together with the $(W,v$-path
$P_{\texttt{in}}$ in $D$, implies an $(W,Y)$-path in $D$, which is a
contradiction to the strong independence between the edges of $A,B$ in $D$.

For the sake of contradiction, say there is a $(Y,w_{i})$-path in
$\widehat{D}$. Then there exists a $(Y,v)$-path in $D$. This, together with
the $(v,W)$-path $P_{\texttt{out}}$, implies an $(Y,W)$-path in $D$, which is
a contradiction to the strong independence between the edges of $A,B$ in $D$.

Orderedness. Fix $j<i$. Suppose, for the sake of contradiction, that there is
a $(w_{i},w_{j})$-path in $\widehat{D}$. Then, there is a $(v,w_{j})$-path in
$D$. This, together with the $(w_{i},v)$-path in $D$, implies a
$(w_{i},w_{j})$-path in $D$, contradicting the ordered-ness condition on the
edges of $A$.

For the sake of contradiction, for $j<i$, say there is a $(w_{i},x_{j})$-path
in $\widehat{D}$. Then there is a $(v,x_{j})$-path in $D$, which together with
the $(w_{i},v)$-path in $D$ contradicts the ordered-ness condition on the
edges of $A$.

No bad vertices. For the sake of contradiction, say there exists a bad vertex
$u$ with respect to $(A,B)$ in $\widehat{D}$, that is,
$N_{\widehat{D}^{\star}}^{-}(u)\cap W,N_{\widehat{D}^{\star}}^{+}(u)\cap
X,N_{\widehat{D}^{\star}}^{-}(u)\cap Y,N_{\widehat{D}^{\star}}^{+}(u)\cap
Z\neq\emptyset$. Then, considering that $\widehat{D}$ is obtained from $D$ by
only identifying $v$ onto $w_{i}$, we get that $N_{D^{\star}}^{+}(u)\cap
X,N_{D^{\star}}^{-}(u)\cap Y,N_{D^{\star}}^{+}(u)\cap Z\neq\emptyset$ and
$(v,u)\in E(D^{\star})$. The $(v,u)$-path, together with the $(W,v)$-path
$P_{\in}$, implies a $(W,u)$-path in $D$, that is $N_{D^{\star}}^{-}(u)\cap
W\neq\emptyset$. That is, $u$ is a bad vertex with respect to $(A,B)$ in $D$,
which is a contradiction. ∎

Identification Rule 2 is the analogue of Identification Rule 1.

######  Identification Rule 2.

If there exists $v\in V(D)\setminus(W\cup X\cup Y\cup Z)$ such that
$N_{D^{\star}}^{+}(v)\cap Y\neq\emptyset$ and $N_{D^{\star}}^{-}(v)\cap
Y\neq\emptyset$, then let $i\in[t]$ be the largest index such that
$(y_{i},v)\in E(D^{\star})$. Identify $v$ onto $y_{i}$.

Symmetrically to Lemma 4.31, the following holds.

######  Lemma 4.32.

Let $\widehat{D}$ be the graph obtained after the application of
Identification Rule 2. Then, the invariants are satisfied.

######  Identification Rule 3.

If there exists $v\in V(D)\setminus(W\cup X\cup Y\cup Z)$ such that
$N_{D^{\star}}^{-}(v)\cap X\neq\emptyset$ and $N_{D^{\star}}^{+}(v)\cap
X\neq\emptyset$, then let $i\in[t]$ be the largest index such that either
$(w_{i},v)\in E(D^{\star})$ or $(x_{i},v)\in E(D^{\star})$. Identify $v$ onto
$x_{i}$.

######  Lemma 4.33.

Let $\widehat{D}$ be the graph obtained after the application of
Identification Rule 3. Then, the invariants are satisfied.

###### Proof.

Since $N_{D^{\star}}^{-}(v)\cap X\neq\emptyset$ and $N_{D^{\star}}^{+}(v)\cap
X\neq\emptyset$, here is a $(X,v)$-path, say $P_{\texttt{in}}$, and a
$(v,X)$-path say $P_{\texttt{out}}$ in $D$.

Weak independence of $A$ in $\widehat{D}$. For the sake of contradiction, say
there is a $(x_{i},w_{j})$-path in $\widehat{D}$. Then there exists a
$(v,w_{j})$-path, say $P$, in $D$. From the choice of $i$ and since
$N_{D^{\star}}^{-}(v)\cap X\neq\emptyset$, there exists $i^{\prime}\leq i$,
such that there is a $(x_{i^{\prime}},v)$-path in $D$. This implies a
$(x_{i^{\prime}},w_{j})$-path in $D$. Since $i^{\prime}<i$ and $A$ is weakly
independent in $D$, $j<i$.

From the choice of $i$, either $(w_{i},v)\in E(D^{*})$, in which case the
existence of $P$ implies a $(w_{i},w_{j})$-path, $j<i$, in $D$, contradicting
the weak independence of $A$ in $D$. Or, $(x_{i},v)\in E(D^{\star})$, in which
case $P$ implies a $(x_{i},w_{j})$-path, $i<i$ in $D$, again contradicting the
weak independence of $A$ in $D$.

Weak independence between $A,B$ in $\widehat{D}$. For the sake of
contradiction, say there is a $(x_{i},Y)$-path in $\widehat{D}$. Then there
exists a $(v,Y)$-path in $D$. This, together with $(X,v)$-path
$P_{\texttt{in}}$, implies an $(X,Y)$-path in $D$, which is a contradiction to
the weak independence between the edges of $A,B$ in $D$.

Strong independence between $A,B$ in $\widehat{D}$. For the sake of
contradiction, say there is a $(Z,x_{i})$-path in $\widehat{D}$. Then there
exists a $(Z,v)$-path in $D$. This, together with the $(v,X)$-path
$P_{\texttt{out}}$ in $D$, implies an $(Z,X)$-path in $D$, which is a
contradiction to the strong independence between the edges of $A,B$ in $D$.

For the sake of contradiction, say there is a $(x_{i},Z)$-path in
$\widehat{D}$. Then there exists a $(v,Z)$-path in $D$. This, together with
the $(X,v)$-path $P_{\texttt{in}}$, implies an $(X,Z)$-path in $D$, which is a
contradiction to the strong independence between the edges of $A,B$ in $D$.

Orderedness. Suppose, for the sake of contradiction, that there is a
$(w_{j},x_{i})$-path in $\widehat{D}$ for $j>i$. Then, there is a
$(w_{j},v)$-path in $D$. Since $j>i$, this contradicts the choice of $i$.

For the sake of contradiction, say there is a $(x_{j},x_{i})$-path in
$\widehat{D}$ for $j>i$. Then, there is a $(x_{j},v)$-path in $D$. Since
$j>i$, this contradicts the choice of $i$.

For the sake of contradiction, say there is a $(x_{i},x_{j})$-path in
$\widehat{D}$ for $j<i$. Then, there is a $(v,x_{j})$-path in $D$. This
together with either the $(x_{i},v)$-path or the $(w_{i},v)$-path, implies
either a $(x_{i},x_{j})$-path or a $(w_{i},x_{j})$-path in $D$, contradicting
the ordered-ness condition on $A$.

No bad vertices. For the sake of contradiction, say there exists a bad vertex
$u$ with respect to $(A,B)$ in $\widehat{D}$, that is,
$N_{\widehat{D}^{\star}}^{-}(u)\cap W,N_{\widehat{D}^{\star}}^{+}(u)\cap
X,N_{\widehat{D}^{\star}}^{-}(u)\cap Y,N_{\widehat{D}^{\star}}^{+}(u)\cap
Z\neq\emptyset$. Then, considering that $\widehat{D}$ is obtained from $D$ by
only identifying $v$ onto $x_{i}$, we get that $N_{D^{\star}}^{-}(u)\cap
W,N_{D^{\star}}^{-}(u)\cap Y,N_{D^{\star}}^{+}(u)\cap Z\neq\emptyset$ and
$(u,v)\in E(D^{\star})$. The $(u,v)$-path, together with the $(v,X)$-path
$P_{\texttt{out}}$, implies a $(u,X)$-path in $D$, that is
$N_{D^{\star}}^{+}(u)\cap X\neq\emptyset$. That is, $u$ is a bad vertex with
respect to $(A,B)$ in $D$, which is a contradiction. ∎

Identification Rule 4 is the analogue of Identification Rule 3.

######  Identification Rule 4.

If there exists $v\in V(D)\setminus(W\cup X\cup Y\cup Z)$ such that
$N_{D^{\star}}^{-}(v)\cap Z\neq\emptyset$ and $N_{D^{\star}}^{+}(v)\cap
Z\neq\emptyset$, then let $i\in[t]$ be the largest index such that either
$(y_{i},v)\in E(D^{\star})$ or $(z_{i},v)\in E(D^{\star})$. Identify $v$ onto
$z_{i}$.

Symmetrically to Lemma 4.34, the following holds.

######  Lemma 4.34.

Let $\widehat{D}$ be the graph obtained after the application of
Identification Rule 3. Then, the invariants are satisfied.

The remaining identification rules are applied on a vertex $v$ when the (in
and out) neighbourhood of $v$ is empty in one of the sets $W,X,Y$ or $Z$.

######  Identification Rule 5.

If $N_{D^{\star}}(v)\cap W=\emptyset$ and $\emptyset\neq
N_{D^{\star}}^{-}(v)\cap(X\cup W\cup Y\cup Z)\subseteq Y$, then let $i\in[t]$
be the largest integer such that $(y_{i},v)\in E(D^{*})$. Identify $v$ onto
$y_{i}$.

######  Lemma 4.35.

Let $\widehat{D}$ be the graph obtained after the application of
Identification 5. Then, $\widehat{D}$ satisfies the invariants.

###### Proof.

Weak independence of $B$ in $\widehat{D}$. For the sake of contradiction, say
there is a $(Z,y_{i})$-path in $\widehat{D}$. Then there exists a
$(Z,v)$-path, in $D$, which is a contradiction (to the assumptions of
Identification Rule 5).

Weak independence between $A,B$ in $\widehat{D}$. For the sake of
contradiction, say there is a $(X,y_{i})$-path in $\widehat{D}$. Then there
exists a $(X,v)$-path in $D$, which is a contradiction (to the assumptions of
Identification Rule 5).

Strong independence between $A,B$ in $\widehat{D}$. For the sake of
contradiction, say there is a $(W,y_{i})$-path in $\widehat{D}$. Then there
exists a $(W,v)$-path in $D$, which is a contradiction (to the assumptions of
Identification Rule 5). Similarly, if there is a $(y_{i},W)$-path in
$\widehat{D}$, then there exists a $(v,W)$-path in $D$, which is again a
contradiction.

Orderedness. Fix $j<i$. For the sake of contradiction,say there is a
$(y_{i},y_{j})$-path in $\widehat{D}$. Then, there is a $(v,y_{j})$-path in
$D$. This together with the $(y_{i},v)$-path implies a $(y_{i},y_{j})$-path in
$D$, which contradicts the ordered-ness condition on $B$.

Similarly, if there is a $(y_{i},z_{j})$-path in $\widehat{D}$, then there is
a $(v,z_{j})$-path in $D$. This, together with the $(y_{i},v)$-path, implies a
$(y_{i},z_{j})$-path in $D$, again contradicting the ordered-ness condition on
$B$.

No bad vertices. For the sake of contradiction, say there exists a bad vertex
$u$ with respect to $(A,B)$ in $\widehat{D}$, that is,
$N_{\widehat{D}^{\star}}^{-}(u)\cap W,N_{\widehat{D}^{\star}}^{+}(u)\cap
X,N_{\widehat{D}^{\star}}^{-}(u)\cap Y,N_{\widehat{D}^{\star}}^{+}(u)\cap
Z\neq\emptyset$. Then, considering that $\widehat{D}$ is obtained from $D$ by
only identifying $v$ onto $y_{i}$, we get that $N_{D^{\star}}^{-}(u)\cap
W,N_{D^{\star}}^{+}(u)\cap X,N_{D^{\star}}^{+}(u)\cap Z\neq\emptyset$ and
$(v,u)\in E(D^{\star})$. The $(v,u)$-path, together with the $(v,y_{i})$-path,
implies a $(u,Y)$-path in $D$, that is $N_{D^{\star}}^{-}(u)\cap
Y\neq\emptyset$. That is, $u$ is a bad vertex with respect to $(A,B)$ in $D$,
which is a contradiction. ∎

The following identification rule is symmetric to 5.

######  Identification Rule 6.

If $N_{D^{\star}}(v)\cap Y=\emptyset$ and $\emptyset\neq
N_{D^{\star}}^{-}(v)\cap(X\cup W\cup Y\cup Z)\subseteq W$, then let $i\in[t]$
be the largest integer such that $(x_{i},v)\in E(D^{*})$. Identify $v$ onto
$w_{i}$.

Similarly to Lemma 4.35, we can prove the following.

######  Lemma 4.36.

Let $\widehat{D}$ be the graph obtained after the application of
Identification 6. Then, $\widehat{D}$ satisfies the invariants.

######  Identification Rule 7.

If $N_{D^{\star}}(v)\cap X=\emptyset$ and $\emptyset\neq
N_{D^{\star}}^{+}(v)\cap(X\cup W\cup Y\cup Z)\subseteq Z$, then let $i\in[t]$
be the smallest integer such that $(v,z_{i})\in E(D^{*})$. Identify $v$ onto
$z_{i}$.

######  Lemma 4.37.

Let $\widehat{D}$ be the graph obtained after the application of
Identification 7. Then, $\widehat{D}$ satisfies the invariants.

###### Proof.

Weak independence of $B$ in $\widehat{D}$. For the sake of contradiction, say
there is a $(z_{i},Y)$-path in $\widehat{D}$. Then there exists a
$(v,Y)$-path, in $D$, which is a contradiction (to the assumptions of
Identification Rule 7).

Weak independence between $A,B$ in $\widehat{D}$. For the sake of
contradiction, say there is a $(z_{i},W)$-path in $\widehat{D}$. Then there
exists a $(v,W)$-path in $D$, which is a contradiction (to the assumptions of
Identification Rule 7).

Strong independence between $A,B$ in $\widehat{D}$. For the sake of
contradiction, say there is a $(z_{i},X)$-path in $\widehat{D}$. Then there
exists a $(v,X)$-path in $D$, which is a contradiction (to the assumptions of
Identification Rule 7). Similarly, if there is a $(X,z_{i})$-path in
$\widehat{D}$, then there exists a $(X,v)$-path in $D$, which is again a
contradiction.

Orderedness. For the sake of contradiction,say there is a $(z_{i},z_{j})$-path
in $\widehat{D}$ for $j<i$.. Then, there is a $(v,z_{j})$-path in $D$. This
together with the $(z_{i},v)$-path implies a $(z_{i},z_{j})$-path in $D$,
which contradicts the ordered-ness condition on $B$.

If there is a $(z_{i},y_{j})$-path in $\widehat{D}$, then there is a
$(v,y_{j})$-path in $D$. This, together with the $(y_{i},v)$-path, implies a
$(y_{i},y_{j})$-path in $D$, again contradicting the ordered-ness condition on
$B$.

No bad vertices. For the sake of contradiction, say there exists a bad vertex
$u$ with respect to $(A,B)$ in $\widehat{D}$, that is,
$N_{\widehat{D}^{\star}}^{-}(u)\cap W,N_{\widehat{D}^{\star}}^{+}(u)\cap
X,N_{\widehat{D}^{\star}}^{-}(u)\cap Y,N_{\widehat{D}^{\star}}^{+}(u)\cap
Z\neq\emptyset$. Then, considering that $\widehat{D}$ is obtained from $D$ by
only identifying $v$ onto $z_{i}$, we get that $N_{D^{\star}}^{-}(u)\cap
W,N_{D^{\star}}^{+}(u)\cap X,N_{D^{\star}}^{-}(u)\cap Y\neq\emptyset$ and
$(u,v)\in E(D^{\star})$. The $(u,v)$-path, together with the $(v,z_{i})$-path,
implies a $(u,Z)$-path in $D$, that is $N_{D^{\star}}^{+}(u)\cap
Z\neq\emptyset$. That is, $u$ is a bad vertex with respect to $(A,B)$ in $D$,
which is a contradiction. ∎

The following identification rule is symmetric to 7.

######  Identification Rule 8.

If $N_{D^{\star}}(v)\cap Z=\emptyset$ and $\emptyset\neq
N_{D^{\star}}^{+}(v)\cap(X\cup W\cup Y\cup Z)\subseteq X$, then let $i\in[t]$
be the smallest integer such that $(v,x_{i})\in E(D^{*})$. Identify $v$ onto
$x_{i}$.

Similarly to Lemma 4.37, we can prove the following.

######  Lemma 4.38.

Let $\widehat{D}$ be the graph obtained after the application of
Identification 8. Then, $\widehat{D}$ satisfies the invariants.

######  Lemma 4.39.

When none of the Identification Rules 1-8 are applicable, for each vertex of
$v\in V(D)\setminus V(A\cup B)$ either $N_{D}^{-}(v)=\emptyset$ or
$N_{D}^{+}(v)=\emptyset$.

###### Proof.

To prove the lemma, we prove the following claims.

######  Claim 4.40.

If $N_{D^{\star}}^{+}(v)\cap W\neq\emptyset$, then
$N_{D^{\star}}^{-}(v)\cap(W\cup X\cup Y\cup Z)\subseteq W$.

###### Proof.

If $x_{j}\in N_{D^{\star}}^{-}(v)$ for some $j\in[t]$, then this implies a
$(X,W)$-path in $D$, contradicting the weak independence of $A$. If $y_{j}\in
N_{D^{\star}}^{-}(v)$ for some $j\in[t]$, then this implies a $(Y,W)$-path in
$D$, contradicting the strong independence between $A,B$. If $z_{j}\in
N_{D^{\star}}^{-}(v)$ for some $j\in[t]$, then this implies a $(Z,W)$-path in
$D$, contradicting the weak independence between $A,B$. ∎

Symmetrically to 4.40, the following holds.

######  Claim 4.41.

If $N_{D^{\star}}^{+}(v)\cap Y\neq\emptyset$, then
$N_{D^{\star}}^{-}(v)\cap(W\cup X\cup Y\cup Z)\subseteq Y$.

######  Claim 4.42.

If $N_{D^{\star}}^{-}(v)\cap X\neq\emptyset$, then
$N_{D^{\star}}^{+}(v)\cap(W\cup X\cup Y\cup Z)\subseteq X$.

###### Proof.

If $w_{j}\in N_{D^{\star}}^{+}(v)$ for some $j\in[t]$, then this implies a
$(X,W)$-path in $D$, contradicting the weak independence of $A$. If $y_{j}\in
N_{D^{\star}}^{+}(v)$ for some $j\in[t]$, then this implies a $(X,Y)$-path in
$D$, contradicting the weak independence between $A,B$. If $z_{j}\in
N_{D^{\star}}^{+}(v)$ for some $j\in[t]$, then this implies a $(X,Z)$-path in
$D$, contradicting the strong independence between $A,B$. ∎

Symmetrically to 4.42, the following holds.

######  Claim 4.43.

If $N_{D^{\star}}^{-}(v)\cap Z\neq\emptyset$, then
$N_{D^{\star}}^{+}(v)\cap(W\cup X\cup Y\cup Z)\subseteq Z$.

From Claims 4.40 and 4.43, if Identification Rules 1-4 are not applicable and
there exists $v\in W\cup X\cup Y\cup Z$ such that
$N_{D^{\star}}^{+}(v)\cap(W\cup X\cup Y\cup Z)\neq\emptyset$ and
$N_{D^{\star}}^{-}(v)\cap(W\cup X\cup Y\cup Z)\neq\emptyset$, then since there
are no bad vertices with respect to $(A,B)$, we conclude that either
$N_{D^{\star}}(v)\cap W=\emptyset$ or $N_{D^{\star}}(v)\cap X=\emptyset$ or
$N_{D^{\star}}(v)\cap Y=\emptyset$ or $N_{D^{\star}}(v)\cap Z=\emptyset$.
Thus, Claims 4.44-4.47 prove the lemma.

######  Claim 4.44.

If Identification Rules 1-4 are no longer applicable, $N_{D^{\star}}(v)\cap
W=\emptyset$ and $N_{D^{\star}}^{+}(v)\cap(X\cup Y\cup Z)\neq\emptyset$, then
$N_{D^{\star}}^{-}(v)\cap(X\cup Y\cup Z)\subseteq Y$.

###### Proof.

We first show that that $N_{D^{\star}}^{-}(v)\cap X=\emptyset$. For the sake
of contradiction, say $N_{D^{\star}}^{-}(v)\cap X\neq\emptyset$. Then, since
Identification Rule 2 is not applicable, $N_{D^{\star}}^{+}(v)\cap
X=\emptyset$. Also, $N_{D^{\star}}^{+}(v)\cap Y=\emptyset$, as otherwise there
is a $(X,Y)$-path in $D$, contradicting the weak independence between $A,B$.
Further, $N_{D^{\star}}^{+}(v)\cap Z=\emptyset$, as otherwise there is a
$(X,Z)$-path in $D$, contradicting the strong independence between $A,B$.

Similarly, if $N_{D^{\star}}^{-}(v)\cap Z\neq\emptyset$. Then, since
Identification Rule 2 is not applicable, $N_{D^{\star}}^{+}(v)\cap
Z=\emptyset$. Also, $N_{D^{\star}}^{+}(v)\cap X=\emptyset$, as otherwise there
is a $(Z,X)$-path in $D$, contradicting the strong independence between $A,B$.
Further, $N_{D^{\star}}^{+}(v)\cap Y=\emptyset$, as otherwise there is a
$(Z,Y)$-path in $D$, contradicting the weak independence of $B$. ∎

Similarly to 4.44, we can prove the following.

######  Claim 4.45.

If Identification Rules 1-4 are no longer applicable, $N_{D^{\star}}(v)\cap
Y=\emptyset$ and $N_{D^{\star}}^{+}(v)\cap(X\cup W\cup Z)\neq\emptyset$, then
$N_{D^{\star}}^{-}(v)\cap(W\cup X\cup Z)\subseteq W$.

######  Claim 4.46.

If Identification Rules 1-4 are no longer applicable, $N_{D^{\star}}(v)\cap
X=\emptyset$ and $N_{D^{\star}}^{-}(v)\cap(X\cup Y\cup Z)\neq\emptyset$, then
$N_{D^{\star}}^{+}(v)\cap(W\cup Y\cup Z)\subseteq Z$.

###### Proof.

We first show that that $N_{D^{\star}}^{+}(v)\cap W=\emptyset$. For the sake
of contradiction, say $N_{D^{\star}}^{+}(v)\cap W\neq\emptyset$. Then, since
Identification Rule 2 is not applicable, $N_{D^{\star}}^{-}(v)\cap
W=\emptyset$. Also, $N_{D^{\star}}^{-}(v)\cap Y=\emptyset$, as otherwise there
is a $(Y,W)$-path in $D$, contradicting the strong independence between $A,B$.
Further, $N_{D^{\star}}^{-}(v)\cap Z=\emptyset$, as otherwise there is a
$(Z,W)$-path in $D$, contradicting the weak independence between $A,B$.

Similarly, if $N_{D^{\star}}^{+}(v)\cap Y\neq\emptyset$, then since
Identification Rule 2 is not applicable, $N_{D^{\star}}^{-}(v)\cap
Y=\emptyset$. Also, $N_{D^{\star}}^{-}(v)\cap W=\emptyset$, as otherwise there
is a $(W,Z)$-path in $D$, contradicting the strong independence between $A,B$.
Further, $N_{D^{\star}}^{-}(v)\cap Z=\emptyset$, as otherwise there is a
$(Z,Y)$-path in $D$, contradicting the weak independence of $B$. ∎

Similarly to 4.46, we can prove the following.

######  Claim 4.47.

If Identification Rules 1-4 are no longer applicable, $N_{D^{\star}}(v)\cap
Z=\emptyset$ and $N_{D^{\star}}^{-}(v)\cap(X\cup Y\cup Z)\neq\emptyset$, then
$N_{D^{\star}}^{+}(v)\cap(W\cup X\cup Y)\subseteq X$.

This concludes the proof of Lemma 4.39. ∎

Now suppose that Identification Rules 1-8 are no longer applicable. From Lemma
4.39, each vertex of $V(D)\setminus(W\cup X\cup Y\cup Z)$ either has only in-
neighbours or only out-neighbours in $D^{\star}$. Let
$V_{\texttt{s}}=\\{v:v\in V(D)\setminus(W\cup X\cup Y\cup Z)\text{ and
}N_{D^{\star}}^{+}(v)\cap(W\cup X\cup Y\cup Z)\neq\emptyset\\}$ and
$V_{\texttt{t}}=V(D)\setminus(W\cup X\cup Y\cup Z\cup V_{\texttt{s}})$. Then
identify all the vertices of $V_{\texttt{s}}$ onto a new vertex s and all the
vertices of $V_{\texttt{t}}$ onto a new vertex t. The resulting graph is a
semi-cleaned ordered $t$-tough-pair.

####  4.3.2 From semi-cleaned ordered tough-pair to hard-pattern

The aim of this section is to prove Lemma 4.6. We first introduce the _almost
$t$-hard matching patterns_ which differ from the $t$-hard matching patterns
in that the source and sink vertices of items 3 and 4, respectively, in
Definition 1.4 may not have ”full” neighborhoods (recall that an $S$-source is
a source vertex $s$ such that $N^{+}(s)=S$ and that an $S$-sink is a sink
vertex such that $N^{-}(s)=S$).

######  Definition 4.48 (almost $t$-hard matching pattern).

An _almost $t$-hard matching pattern_ is an (acyclic) digraph $D$ constructed
the following way. We start with disjoint vertex sets
$W=\\{w_{1},\ldots,w_{t}\\}$, $X=\\{x_{1},\ldots,x_{t}\\}$,
$Y=\\{y_{1},\ldots,y_{t}\\}$ and $Z=\\{z_{1},\ldots,z_{t}\\}$ and introduce
the edges $(w_{i},x_{i})$ and $(y_{i},z_{i})$ for every $i\in[t]$.
Furthermore, we introduce into $D$ any combination of the following items:

  1. 1.

either the directed path $w_{1}\rightarrow w_{2}\rightarrow\ldots\rightarrow
w_{t}\rightarrow z_{1}\rightarrow z_{2}\rightarrow\ldots\rightarrow z_{t}$, or
any of the directed paths $w_{1}\rightarrow w_{2}\rightarrow\ldots\rightarrow
w_{t}$ and $z_{1}\rightarrow z_{2}\rightarrow\ldots\rightarrow z_{t}$;

  2. 2.

either the directed path $y_{1}\rightarrow y_{2}\rightarrow\ldots\rightarrow
y_{t}\rightarrow x_{1}\rightarrow x_{2}\rightarrow\ldots\rightarrow x_{t}$, or
any of the directed paths $x_{1}\rightarrow x_{2}\rightarrow\ldots\rightarrow
x_{t}$ and $y_{1}\rightarrow y_{2}\rightarrow\ldots\rightarrow y_{t}$;

  3. 3.

a vertex $s$ such that $N^{-}(s)=\emptyset$ and $N^{+}(s)\subseteq W\cup X\cup
Y\cup Z$;

  4. 4.

a vertex $t$ such that $N^{+}(t)=\emptyset$ and $N^{-}(t)\subseteq W\cup X\cup
Y\cup Z$;

  5. 5.

a vertex $r_{WZ}$ such that $N^{-}(r_{WZ})=W$ and $N^{+}(r_{WZ})=Z$;

  6. 6.

a vertex $r_{YX}$ such that $N^{-}(r_{YX})=Y$ and $N^{+}(r_{YX})=X$.

We further introduce the four canonical graphs below corresponding to ”half” a
hard matching pattern (see Figure 12 for an illustration).

######  Definition 4.49.

Let $U=\\{u_{1},\ldots,u_{t}\\}$ and $V=\\{v_{1},\ldots,v_{t}\\}$. We define
the following four reachability-minimal acyclic digraphs on vertex set $U\cup
V$.

  * •

The digraph $O_{1}^{t}$ is a $(U,V)$-induced-matching.

  * •

The digraph $O_{2}^{t}$ is a $(U,V)$-matching which further contains the
directed path on $U$ from $u_{1}$ to $u_{t}$.

  * •

The digraph $O_{3}^{t}$ is a $(U,V)$-matching which further contains the
directed path on $V$ from $v_{1}$ to $v_{t}$.

  * •

The digraph $O_{4}^{t}$ is a $(U,V)$-matching which further contains the
directed path on $U$ from $u_{1}$ to $u_{t}$ and the directed path on $V$ from
$v_{1}$ to $v_{t}$.

$O_{1}^{4}$

$O_{2}^{4}$

$O_{3}^{4}$

$O_{4}^{4}$

Figure 12: The graphs of Definition 4.49 for $t=4$.

See 4.6

###### Proof.

For every $p\geq 1$ and $j\geq 1$, let $\ell_{j}(p)$ be an integer such that
$p\geq\mathcal{R}(\ell_{j}(p),j)$. For notational convenience, we show,
instead of the above statement, that if $D$ is a semi-cleaned ordered
$t$-tough-pair then either $D^{*}$ contains a $g(t)$-induced-biclique whose
edges are minimal in $D$, or $D$ can be identified to a digraph $\hat{D}$ such
that $\hat{D}$ is transitively equivalent to a $g(t)$-hard matching pattern,
where $g(t)=(\ell_{4}(\ell_{4}(\ell_{5}(t))/2)-4)/8$ (equivalently,
$h(t)=\mathcal{R}(2\mathcal{R}(2\mathcal{R}(8t+4,4),4),5)$).

Let $D$ be a semi-cleaned ordered $t$-tough-pair and let $(A,B)$ be the
ordered $t$-tough-pair contained in $D$, where
$A=((w_{1},x_{1}),\ldots,(w_{t},x_{t}))$ and
$B=((y_{1},z_{1}),\ldots,(y_{t},z_{t}))$. Denote by
$W=\\{w_{i}~{}|~{}i\in[t]\\}$, $X=\\{x_{i}~{}|~{}i\in[t]\\}$,
$Y=\\{y_{i}~{}|~{}i\in[t]\\}$ and $Z=\\{z_{i}~{}|~{}i\in[t]\\}$. Given a
digraph $H$, we denote by $\overline{H}$ the underlying undirected graph and
by $H^{*}$ the transitive closure of $H$. Before turning to the proof of the
lemma, we first show the following claims.

######  Claim 4.50.

One of the following holds.

  * (1)

There exist subsets $X^{\prime}\subseteq X$ and $W^{\prime}\subseteq W$ such
that $|X^{\prime}|=|W^{\prime}|=\lfloor\ell_{5}(t)/2\rfloor$ and $D$ contains
a $(W^{\prime},X^{\prime})$-induced-biclique.

  * (2)

There exist a set $I\subseteq[t]$ of size $\ell_{5}(t)$ such that
$D[\\{x_{i},w_{i}~{}|~{}i\in I\\}]$ is transitively equivalent to one of
$O_{1}^{\ell_{5}(t)},O_{2}^{\ell_{5}(t)},O_{3}^{\ell_{5}(t)}$ and
$O_{4}^{\ell_{5}(t)}$.

###### Proof.

Consider the edge-coloring of the complete undirected graph $G$ on vertex set
$\\{1,\ldots,t\\}$ defined as follows: for every $i,j\in[t]$ where $i<j$, the
edge $ij\in E(G)$ receives

  * •

color 1 if $(w_{i},w_{j}),(x_{i},x_{j}),(w_{i},x_{j})\notin E(D^{*})$;

  * •

color 2 if $(w_{i},w_{j})\in E(D)$ and $(x_{i},x_{j})\notin E(D^{*})$;

  * •

color 3 if $(w_{i},w_{j})\notin E(D)$ and $(x_{i},x_{j})\in E(D^{*})$;

  * •

color 4 if $(w_{i},w_{j}),(x_{i},x_{j})\in E(D^{*})$; and

  * •

color 5 if $(w_{i},w_{j}),(x_{i},x_{j})\notin E(D^{*})$ and $(w_{i},x_{j})\in
E(D^{*})$.

Note that for any $1\leq i<j\leq t$, if $D^{*}$ contains one of
$(w_{i},w_{j})$ and $(x_{i},x_{j})$ then $D^{*}$ also contains $(w_{i},x_{j})$
and thus, each edge of $E(G)$ receives a color in the above coloring. Now by
Ramsey’s Theorem, $G$ contains a monochromatic clique of size $\ell_{5}(t)$:
let $1\leq i_{1}<\ldots<i_{\ell_{5}(t)}\leq t$ be a set of $\ell_{5}(t)$
vertices inducing a monochromatic clique in $G$. Since $(A,B)$ is an ordered
$t$-tough-pair, for every $1\leq p<q\leq\ell_{5}(t)$, there is no
$(w_{i_{q}},w_{i_{p}})$-path, no $(w_{i_{q}},x_{i_{p}})$-path and no
$(x_{i_{q}},x_{i_{p}})$-path. It follows that if the clique in $G$ on vertex
set $\\{i_{1},\ldots,i_{\ell_{5}(t)}\\}$ has

  * •

color 1 then $D[\\{w_{i_{j}},x_{i_{j}}~{}|~{}j\in[\ell_{5}(t)]\\}]$ is
transitively equivalent to $O^{\ell_{5}(t)}_{1}$;

  * •

color 2 then $D[\\{w_{i_{j}},x_{i_{j}}~{}|~{}j\in[\ell_{5}(t)]\\}]$ is
transitively equivalent to $O^{\ell_{5}(t)}_{2}$;

  * •

color 3 then $D[\\{w_{i_{j}},x_{i_{j}}~{}|~{}j\in[\ell_{5}(t)]\\}]$ is
transitively equivalent to $O^{\ell_{5}(t)}_{3}$;

  * •

color 4 then $D[\\{w_{i_{j}},x_{i_{j}}~{}|~{}j\in[\ell_{5}(t)]\\}]$ is
transitively equivalent to $O^{\ell_{5}(t)}_{4}$;

  * •

color 5 then $D$ contains a
$(\\{w_{i_{j}}~{}|~{}j\in[\lfloor\ell_{5}(t)/2\rfloor]\\},\\{x_{i_{\lfloor\ell_{5}(t)/2\rfloor+j}}~{}|~{}j\in[\lfloor\ell_{5}(t)/2\rfloor]\\})$-induced-
biclique.

Thus, if the clique in $G$ on vertex set $\\{i_{1},\ldots,i_{\ell_{5}(t)}\\}$
does not have color 5 then we may take $I=\\{i_{1},\ldots,i_{\ell_{5}(t)}\\}$
to prove our claim. ∎

Symmetrically to 4.50, we have the following.

######  Claim 4.51.

One of the following holds.

  * (1)

There exist subsets $Y^{\prime}\subseteq Y$ and $Z^{\prime}\subseteq Z$ such
that $|Y^{\prime}|=|Z^{\prime}|=\lfloor\ell_{5}(t)/2\rfloor$ and $D$ contains
a $(Y^{\prime},Z^{\prime})$-induced-biclique.

  * (2)

There exist a set $I\subseteq[t]$ of size $\ell_{5}(t)$ such that
$D[\\{y_{i},z_{i}~{}|~{}i\in I\\}]$ is transitively equivalent to one of
$O_{1}^{\ell_{5}(t)},O_{2}^{\ell_{5}(t)},O_{3}^{\ell_{5}(t)}$ and
$O_{4}^{\ell_{5}(t)}$.

######  Claim 4.52.

For any subsets $W^{\prime}\subseteq W$ and $Z^{\prime}\subseteq Z$ where
$|W^{\prime}|=|Z^{\prime}|=p$, there exist subsets $W^{\prime\prime}\subseteq
W^{\prime}$ and $Z^{\prime\prime}\subseteq Z^{\prime}$ such that
$|W^{\prime\prime}|=|Z^{\prime\prime}|=\lfloor\ell_{4}(p)/2\rfloor$ and

  * $\bullet$

either there is no edge in $D$ from a vertex of $W^{\prime\prime}$ to a vertex
of $Z^{\prime\prime}$,

  * $\bullet$

or $D^{*}$ contains a $(W^{\prime\prime},Z^{\prime\prime})$-biclique (not
necessarily induced).

###### Proof.

Let $W^{\prime}\subseteq W$ and $Z^{\prime}\subseteq Z$ be two subsets of size
$p$. We distinguish two cases depending on whether the bipartite graph
$\overline{D}[W^{\prime},Z^{\prime}]$ has a matching of size at least $p/2$ or
not.

##### Case 1. The bipartite graph $\overline{D}[W^{\prime},Z^{\prime}]$ has a
matching of size at least $p/2$.

Let $M$ be a matching in $\overline{D}[W^{\prime},Z^{\prime}]$ of size
$\lfloor p/2\rfloor$ and let $e_{1},\ldots,e_{\lfloor p/2\rfloor}$ be an
arbitrary ordering of the edges in $M$. Consider the edge-coloring of the
complete undirected graph $G$ on vertex set $\\{1,\ldots,\lfloor
p/2\rfloor\\}$ defined as follows: for every $1\leq i<j\leq\lfloor
p/2\rfloor$, the edge $ij\in E(G)$ receives

  * •

color 1 if
$(\text{tail}(e_{i}),\text{head}(e_{j})),(\text{tail}(e_{j}),\text{head}(e_{i}))\notin
E(D^{*})$;

  * •

color 2 if $(\text{tail}(e_{i}),\text{head}(e_{j}))\in E(D^{*})$ and
$(\text{tail}(e_{j}),\text{head}(e_{i}))\notin E(D^{*})$;

  * •

color 3 if $(\text{tail}(e_{i}),\text{head}(e_{j}))\notin E(D^{*})$ and
$(\text{tail}(e_{j}),\text{head}(e_{i}))\in E(D^{*})$; and

  * •

color 4 if
$(\text{tail}(e_{i}),\text{head}(e_{j})),(\text{tail}(e_{j}),\text{head}(e_{i}))\in
E(D^{*})$;

Then by Ramsey’s Theorem, $G$ contains a monochromatic clique of size
$\ell_{4}(p)$: let $1\leq i_{1}<\ldots<i_{\ell_{4}(p)}\leq p/2$ be a set of
$\ell_{4}(p)$ vertices inducing a monochromatic clique in $G$. Now if this
clique has

  * •

color 1 then by taking
$W^{\prime\prime}=\\{\text{tail}(e_{i_{j}})~{}|~{}j\in[\lfloor\ell_{4}(p)/2\rfloor]\\}$
and
$Z^{\prime\prime}=\\{\text{head}(e_{i_{j}})~{}|~{}j\in[\lfloor\ell_{4}(p)/2\rfloor]\\}$,
there is no edge from $W^{\prime\prime}$ to $Y^{\prime\prime}$ in $D^{*}$ (and
a fortiori in $D$);

  * •

color 2 then by taking
$W^{\prime\prime}=\\{\text{tail}(e_{i_{j}})~{}|~{}j\in[\lfloor\ell_{4}(p)/2\rfloor]\\}$
and
$Z^{\prime\prime}=\\{\text{head}(e_{i_{\lfloor\ell_{4}(p)/2\rfloor+j}})~{}|~{}j\in[\lfloor\ell_{4}(p)/2\rfloor]\\}$,
$D^{*}$ contains a $(W^{\prime\prime},Z^{\prime\prime})$-biclique;

  * •

color 3 then by taking
$W^{\prime\prime}=\\{\text{tail}(e_{i_{\lfloor\ell_{4}(p)/2\rfloor+j}})~{}|~{}j\in[\lfloor\ell_{4}(p)/2\rfloor]\\}$
and
$Z^{\prime\prime}=\\{\text{head}(e_{i_{j}})~{}|~{}j\in[\lfloor\ell_{4}(p)/2\rfloor]\\}$,
$D^{*}$ contains a $(W^{\prime\prime},Z^{\prime\prime})$-biclique;

  * •

color 4 then by taking
$W^{\prime\prime}=\\{\text{tail}(e_{i_{j}})~{}|~{}j\in[\lfloor\ell_{4}(p)/2\rfloor]\\}$
and
$Z^{\prime\prime}=\\{\text{head}(e_{i_{j}})~{}|~{}j\in[\lfloor\ell_{4}(p)/2\rfloor]\\}$,
$D^{*}$ contains a $(W^{\prime\prime},Z^{\prime\prime})$-biclique.

##### Case 2. The bipartite graph $\overline{D}[W^{\prime},Z^{\prime}]$ has no
matching of size at least $p/2$.

Then by König’s Theorem, $\overline{D}[W^{\prime},Z^{\prime}]$ has, in this
case, a vertex cover at size at most $p/2$: let $V\subseteq W^{\prime}\cup
Z^{\prime}$ be a minimum vertex cover of
$\overline{D}[W^{\prime},Z^{\prime}]$. Since then, $\min\\{W^{\prime}\setminus
V,Z^{\prime}\setminus
V\\}\geq\lfloor\ell_{4}(p)/2\rfloor\geq\lfloor\ell_{4}(p)/2\rfloor$, we may
take any subsets $W^{\prime\prime}\subseteq W^{\prime}\setminus V$ and
$Z^{\prime\prime}\subseteq Z^{\prime}\setminus V$ of size
$\lfloor\ell_{4}(p)/2\rfloor$ to prove the claim, as there are surely no edges
from $W^{\prime\prime}$ to $Z^{\prime\prime}$ in $D$. ∎

Symmetrically to 4.52, we have the following.

######  Claim 4.53.

For any subsets $Y^{\prime}\subseteq Y$ and $X^{\prime}\subseteq X$ where
$|Y^{\prime}|=|X^{\prime}|=p$, there exist subsets $Y^{\prime\prime}\subseteq
Y^{\prime}$ and $X^{\prime\prime}\subseteq X^{\prime}$ such that
$|Y^{\prime\prime}|=|X^{\prime\prime}|=\lfloor\ell_{4}(p)/2\rfloor$ and

  * $\bullet$

either there is no edge in $D$ from a vertex of $Y^{\prime\prime}$ to a vertex
of $X^{\prime\prime}$,

  * $\bullet$

or $D^{*}$ contains a $(Y^{\prime\prime},X^{\prime\prime})$-biclique (not
necessarily induced).

We next define partitions with respect to a set and prove thereafter useful
properties of these partitions.

######  Definition 4.54.

For any $V\in\\{W,X,Y,Z\\}$ and any $U\subseteq V$, the _partition of $V$
w.r.t. $U$_ is the partition of $V\setminus U$ into four sets
$V^{\star},V^{\circ},V^{+}$ and $V^{-}$ such that the following hold.

  * •

For every $v\in V^{\star}$, $N^{+}_{D^{*}}(v)\cap U\neq\emptyset$ and
$N^{-}_{D^{*}}(v)\cap U\neq\emptyset$.

  * •

For every $v\in V^{\circ}$, $(N^{+}_{D^{*}}(v)\cup N^{-}_{D^{*}}(v))\cap
U=\emptyset$.

  * •

For every $v\in V^{+}$, $N^{+}_{D^{*}}(v)\cap U\neq\emptyset$ and
$N^{-}_{D^{*}}(v)\cap U=\emptyset$.

  * •

For every $v\in V^{-}$, $N^{+}_{D^{*}}(v)\cap U=\emptyset$ and
$N^{-}_{D^{*}}(v)\cap U\neq\emptyset$.

Note that since $(A,B)$ is an ordered tough-pair, for any $V\in\\{W,X,Y,Z\\}$
and any $v\in V$,

  * •

if $u\in N^{-}_{D^{*}}(v)$ then $u$ has a smaller index than that of $v$, and

  * •

if $u\in N^{+}_{D^{*}}(v)$ then $u$ has a larger index than that of $v$.

######  Claim 4.55.

For any $V\in\\{W,X,Y,Z\\}$ and any $U\subseteq V$, the following hold. Let
$V^{\star},V^{\circ},V^{+}$ and $V^{-}$ be the partition of $V$ w.r.t $U$.
Then there is no edge in $D^{*}$

  * (i)

from a vertex of $V^{\star}$ to a vertex of $V^{\circ}\cup V^{+}$,

  * (ii)

from a vertex of $V^{-}$ to a vertex of $V^{\star}\cup V^{\circ}\cup V^{+}$,
and

  * (iii)

from a vertex of $V^{\circ}$ to a vertex of $V^{+}\cup V^{\star}$.

Furthermore, if $D^{*}[U]$ has no edge then $V^{\star}=\emptyset$.

###### Proof.

Consider $u\in V^{\star}$. If there exists $v\in V^{\circ}\cup V^{+}$ such
that $(u,v)\in E(D^{*})$ then in particular $\emptyset\neq
N^{-}_{D^{*}}(u)\cap U\subseteq N^{-}_{D^{*}}(v)$, a contradiction to the fact
that $v\in V^{+}\cup V^{\circ}$. Similarly, there is no edge in $D^{*}$ from a
vertex of $V^{-}$ to a vertex of $V^{+}\cup V^{\star}$: indeed, if there exist
$u\in V^{-}$ and $v\in V^{+}\cup V^{\star}$ such that $(u,v)\in E(D^{*})$ then
in particular $\emptyset\neq N^{-}_{D^{*}}(u)\cap U\subseteq
N^{-}_{D^{*}}(v)$, a contradiction to the fact that $v\in V^{+}$. Furthermore,
there is no edge from a vertex of $V^{-}$ to a vertex of $V^{\circ}$ for if
there exist $u\in V^{-}$ and $v\in V^{\circ}$ such that $(u,v)\in E(D^{*})$,
then in particular $\emptyset\neq N^{-}_{D^{*}}(u)\cap U\subseteq
N^{-}_{D^{*}}(v)$, a contradiction to the fact that $v\in V^{\circ}$. Finally,
if there exist $u\in V^{\circ}$ and $v\in V^{+}\cup V^{\star}$ such that
$(u,v)\in E(D^{*})$ then in particular $\emptyset\neq N^{+}_{D^{*}}(v)\cap
U\subseteq N^{+}_{D^{*}}(u)$, a contradiction to the fact that $u\in
V^{\circ}$. Now assume that $D^{*}[U]$ has no edge and suppose for a
contradiction that there exists $u\in V\setminus U$ such that both
$N^{-}_{D^{*}}(u)\cap U\neq\emptyset$ and $N^{+}_{D^{*}}(u)\cap
U\neq\emptyset$. Then for any $x\in N^{-}_{D^{*}}(u)\cap U$ and $y\in
N^{+}_{D^{*}}(u)\cap U$, $(x,y)\in E(D^{*})$, a contradiction to the fact that
$U$ is an independent set of $D^{*}$. ∎

######  Claim 4.56.

For any $V\in\\{W,Y\\}$ and any $U\subseteq V$, the following hold:

  * •

if there exist $u\in W\cup X\cup Y\cup Z$ and $v\in V^{+}$ such that $(u,v)\in
E(D^{*})$ then $u\in V^{+}$;

  * •

if there exist $u\in W\cup X\cup Y\cup Z$ and $v\in V^{\circ}$ such that
$(u,v)\in E(D^{*})$ then $u\in V^{\circ}\cup V^{+}$,

where $V^{\star},V^{\circ},V^{+},V^{-}$ is the partition of $V$ w.r.t $U$.

###### Proof.

Suppose that there exist $u\in W\cup X\cup Y\cup Z$ and $v\in V^{+}$ such that
$(u,v)\in E(D^{*})$. Observe first that since $V\in\\{W,Y\\}$ and $(A,B)$ is
an ordered tough-pair, necessarily $u\in V$. Now since $v\in V^{+}$, $u\notin
U$ by definition and since by 4.55, $u\notin V^{\star}\cup V^{\circ}\cup
V^{-}$, we conclude that $u\in V^{+}$. Suppose next that there exist $u\in
W\cup X\cup Y\cup Z$ and $v\in V^{\circ}$ such that $(u,v)\in E(D^{*})$. Then
as previously $u\in V$. Now since $v\in V^{\circ}$, $u\notin U$ by definition
and since by 4.55, $u\notin V^{\star}\cup V^{-}$, we conclude that $u\in
V^{\circ}\cup V^{+}$. ∎

######  Claim 4.57.

For any $V\in\\{X,Z\\}$ and any $U\subseteq V$, the following hold:

  * •

if there exist $u\in V^{-}$ and $v\in W\cup X\cup Y\cup Z$ such that $(u,v)\in
E(D^{*})$ then $v\in V^{-}$;

  * •

if there exist $v\in V^{\circ}$ and $v\in W\cup X\cup Y\cup Z$ such that
$(u,v)\in E(D^{*})$ then $u\in V^{\circ}\cup V^{-}$,

where $V^{\star},V^{\circ},V^{+},V^{-}$ is the partition of $V$ w.r.t $U$.

###### Proof.

Suppose that there exist $u\in V^{-}$ and $v\in W\cup X\cup Y\cup Z$ such that
$(u,v)\in E(D^{*})$. Observe first that since $V\in\\{X,Z\\}$ and $(A,B)$ is
an ordered tough-pair, necessarily $v\in V$. Now since $u\in V^{-}$, $v\notin
U$ by definition and since by 4.55, $v\notin V^{\star}\cup V^{\circ}\cup
V^{+}$, we conclude that $v\in V^{-}$. Suppose next that there exist $v\in
V^{\circ}$ and $v\in W\cup X\cup Y\cup Z$ such that $(u,v)\in E(D^{*})$ then
$u\in V^{\circ}\cup V^{-}$. Then as previously $v\in V$. Now since $u\in
V^{\circ}$, $v\notin U$ by definition and since by 4.55, $v\notin V^{+}\cup
V^{\star}$, we conclude that $v\in V^{\circ}\cup V^{-}$. ∎

We now turn to the proof of the lemma. We assume henceforth that $D$ contains
no $g(t)$-induced-biclique (we are done otherwise). We first prove that $D$
can be identified to a digraph which is transitively equivalent to an almost
$4g(t)$-hard matching pattern and then show how to obtain a $g(t)$-hard
matching pattern from an almost $4g(t)$-hard matching pattern.

By 4.50, there exists a set $I_{A}\subseteq[t]$ of size $\ell_{5}(t)$ such
that $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively equivalent to one
of $O_{1}^{\ell_{5}(t)},O_{2}^{\ell_{5}(t)},O_{3}^{\ell_{5}(t)}$ and
$O_{4}^{\ell_{5}(t)}$; and similarly, by 4.51, there exists a set
$I_{B}\subseteq[t]$ of size $\ell_{5}(t)$ such that
$D[\\{y_{i},z_{i}~{}|~{}i\in I_{B}\\}]$ is transitively equivalent to one of
$O_{1}^{\ell_{5}(t)},O_{2}^{\ell_{5}(t)},O_{3}^{\ell_{5}(t)}$ and
$O_{4}^{\ell_{5}(t)}$. Now by 4.52 there exist subsets $I_{A}^{1}\subseteq
I_{A}$ and $I_{B}^{1}\subseteq I_{B}$ such that
$|I_{A}^{1}|=|I_{B}^{1}|=\ell_{4}(\ell_{5}(t))/2$ and there is either no edge
or every edge in $D$ from $\\{w_{i}~{}|~{}i\in I_{A}^{1}\\}$ to
$\\{z_{i}~{}|~{}i\in I_{B}^{1}\\}$. By 4.53, there further exist subsets
$I_{A}^{2}\subseteq I_{A}^{1}$ and $I_{B}^{2}\subseteq I_{B}^{1}$ such that
$|I_{A}^{2}|=|I_{B}^{2}|=\ell_{4}(\ell_{4}(\ell_{5}(t))/2))/2=4g(t)+2$ and
there is either no edge or every edge in $D$ from $\\{y_{i}~{}|~{}i\in
I_{A}^{2}\\}$ to $\\{x_{i}~{}|~{}i\in I_{B}^{2}\\}$.

Now let $W^{\star},W^{\circ},W^{+},W^{-}$ be the partition of $W$ w.r.t.
$\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$, $X^{\star},X^{\circ},X^{+},X^{-}$ be the
partition of $X$ w.r.t $\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$,
$Y^{\star},Y^{\circ},Y^{+},Y^{-}$ be the partition of $Y$ w.r.t
$\\{y_{i}~{}|~{}i\in I_{B}^{2}\\}$ and $Z^{\star},Z^{\circ},Z^{+},Z^{-}$ be
the partition of $Z$ w.r.t $\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}$. We devise the
following identification rules.

######  Identification Rule 9.

Proceed as follows.

  1. 1.

Identify every vertex in $W^{\circ}\cup W^{+}\cup Y^{\circ}\cup Y^{+}$
(together with the source vertex s of $D$ when it exists) to a single vertex
$s$.

  2. 2.

If $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively equivalent to
$O_{1}^{\ell_{5}(t)}$, further identity every vertex in $X^{+}$ to $s$.

  3. 3.

If $D[\\{y_{i},z_{i}~{}|~{}i\in I_{B}\\}]$ is transitively equivalent to
$O_{1}^{\ell_{5}(t)}$, further identity every vertex in $Z^{+}$ to $s$.

######  Identification Rule 10.

Proceed as follows.

  1. 1.

Identify every vertex in $X^{\circ}\cup X^{-}\cup Z^{\circ}\cup Z^{-}$
(together with the sink vertex t of $D$ when it exists) to a single vertex
$t$.

  2. 2.

If $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively equivalent to
$O_{1}^{\ell_{5}(t)}$, further identity every vertex in $W^{-}$ to $t$.

  3. 3.

If $D[\\{y_{i},z_{i}~{}|~{}i\in I_{B}\\}]$ is transitively equivalent to
$O_{1}^{\ell_{5}(t)}$, further identity every vertex in $Y^{-}$ to $t$.

######  Identification Rule 11.

For every consecutive $i<i^{\prime}\in I_{A}^{2}\cup\\{1,t\\}$ $($that is,
$(I_{A}^{2}\cup\\{1,t\\})\cap[i,i^{\prime}]=\\{i,i^{\prime}\\})$ and every
$j\in[i,i^{\prime}]$, proceed as follows.

  1. 1.

$D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively equivalent to
$O_{2}^{\ell_{5}(t)}$: if $w_{j}\in W^{\star}\cup W^{-}$ then identify $w_{j}$
to $w_{i}$ and if $x_{j}\in X^{+}$ then identify $x_{j}$ to $w_{i^{\prime}}$.

  2. 2.

$D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively equivalent to
$O_{3}^{\ell_{5}(t)}$: if $w_{j}\in W^{-}$ then identify $w_{j}$ to $x_{i}$
and if $x_{j}\in X^{\star}\cup X^{+}$ then identify $x_{j}$ to
$x_{i^{\prime}}$.

  3. 3.

$D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively equivalent to
$O_{4}^{\ell_{5}(t)}$: if $w_{j}\in W^{\star}\cup W^{-}$ then identify $w_{j}$
to $w_{i}$ and if $x_{j}\in X^{\star}\cup X^{+}$ then identify $x_{j}$ to
$x_{i^{\prime}}$.

######  Identification Rule 12.

For every consecutive $i<i^{\prime}\in I_{B}^{2}\cup\\{1,t\\}$ and every
$j\in[i,i^{\prime}]$, proceed as follows.

  1. 1.

$D[\\{y_{i},z_{i}~{}|~{}i\in I_{B}\\}]$ is transitively equivalent to
$O_{2}^{\ell_{5}(t)}$: if $y_{j}\in Y^{\star}\cup Y^{-}$ then identify $y_{j}$
to $y_{i}$ and if $z_{j}\in Z^{+}$ then identify $z_{j}$ to $y_{i^{\prime}}$.

  2. 2.

$D[\\{y_{i},x_{i}~{}|~{}i\in I_{B}\\}]$ is transitively equivalent to
$O_{3}^{\ell_{5}(t)}$: if $y_{j}\in Y^{-}$ then identify $y_{j}$ to $z_{i}$
and if $z_{j}\in Z^{\star}\cup Z^{+}$ then identify $z_{j}$ to
$z_{i^{\prime}}$.

  3. 3.

$D[\\{y_{i},z_{i}~{}|~{}i\in I_{B}\\}]$ is transitively equivalent to
$O_{4}^{\ell_{5}(t)}$: if $y_{j}\in Y^{\star}\cup Y^{-}$ then identify $y_{j}$
to $y_{i}$ and if $z_{j}\in Z^{\star}\cup Z^{+}$ then identify $z_{j}$ to
$z_{i^{\prime}}$.

Let $D_{I}$ be the digraph resulting from an exhaustive application of
Identification Rules 9-12. We aim to show that $D_{I}$ can be identified to a
digraph which is transitively equivalent to an almost $4g(t)$-hard matching
pattern. To this end, we first prove the following claims and then distinguish
cases depending on the graphs to which $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$
and $D[\\{y_{i},z_{i}~{}|~{}i\in I_{B}\\}]$ are transitively equivalent, and
whether there is no edge or every edge in $D$ from $\\{w_{i}~{}|~{}i\in
I_{A}^{2}\\}$ to $\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}$ (from $\\{y_{i}~{}|~{}i\in
I_{A}^{2}\\}$ to $\\{x_{i}~{}|~{}i\in I_{B}^{2}\\}$, respectively).

######  Claim 4.58.

The vertex set of $D_{I}$ consists of $\\{w_{i},x_{i}~{}|~{}i\in
I_{A}^{2}\\}\cup\\{y_{i},z_{i}~{}|~{}i\in I_{B}^{2}\\}$ together with possibly
$s$ or $t$.

###### Proof.

We first prove that $V(D_{I})\cap W=\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$.
Clearly, after 9.1 has been applied, there are no more vertices from
$W^{\circ}\cup W^{+}$ left. Now if $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is
transitively equivalent to $O_{1}^{\ell_{5}(t)}$ then $W^{\star}=\emptyset$ by
4.55 and once 10.2 has been applied, there are no more vertices from $W^{-}$
left. Similarly, if $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively
equivalent to $O_{3}^{\ell_{5}(t)}$ then $W^{\star}=\emptyset$ by 4.55 and
once 11.2 has been exhaustively applied, there are no more vertices from
$W^{-}$ left. Otherwise, $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is
transitively equivalent to either $O_{2}^{\ell_{5}(t)}$ or
$O_{4}^{\ell_{5}(t)}$ in which case, an exhaustive application of 11.1 and
11.3, respectively, leaves no vertex from $W^{\star}\cup W^{-}$. We conclude
symmetrically that $V(D_{I})\cap Y=\\{y_{i}~{}|~{}i\in I_{B}^{2}\\}$.

Second, let us show that $V(D_{I})\cap X=\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$.
Clearly, after 10.1 has been applied, there are no more vertices from
$X^{\circ}\cup X^{-}$ left. Now if $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is
transitively equivalent to $O_{1}^{\ell_{5}(t)}$ then $X^{\star}=\emptyset$ by
4.55 and once 9.2 has been applied, there are no more vertices from $X^{+}$
left. Similarly, if $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively
equivalent to $O_{2}^{\ell_{5}(t)}$ then $X^{\star}=\emptyset$ by 4.55 and
once 11.1 has been exhaustively applied, there are no more vertices from
$X^{+}$ left. Otherwise, $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is
transitively equivalent to either $O_{3}^{\ell_{5}(t)}$ or
$O_{4}^{\ell_{5}(t)}$ in which case, an exhaustive application of 11.2 and
11.3, respectively, leaves no vertex from $X^{\star}\cup X^{+}$. We conclude
symmetrically that $V(D_{I})\cap Z=\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}$. ∎

######  Claim 4.59.

If $s$ exists then $d^{-}_{D_{I}}(s)=0$ and if $t$ exists then
$d^{+}_{D_{I}}(t)=0$.

###### Proof.

Assume that $s$ exists and suppose to the contrary that there exists $u\in
V(D_{I})$ such that $u\in N^{-}_{D_{I}}(s)$. Then there exist $v_{s},v_{u}\in
V(D)$ such that $v_{s}$ has been identified to $s$, $v_{u}$ has been
identified to $u$ and $(v_{u},v_{s})\in E(D)$. Since the source vertex s of
$D$ (if any) has in-degree zero in $D$, necessarily $v_{s}\neq\texttt{s}$.
Furthermore, $v_{s}$ cannot belong to $W^{\circ}\cup W^{+}\cup Y^{\circ}\cup
Y^{+}$: indeed, if, say, $v_{s}\in W^{\circ}\cup W^{+}$ (the case where
$v_{s}\in Y^{\circ}\cup Y^{+}$ is symmetric) then by 4.56, $v_{u}\in
W^{\circ}\cup W^{+}$, a contradiction as $v_{u}$ is not identified to $s$.
Thus, it must be that $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively
equivalent to $O_{1}^{\ell_{5}(t)}$ and $v_{s}\in X^{+}$, or
$D[\\{y_{i},x_{i}~{}|~{}i\in I_{B}\\}]$ is transitively equivalent to
$O_{1}^{\ell_{5}(t)}$ and $v_{s}\in Z^{+}$. Assume without loss of generality
that the latter holds (the other case is symmetric). Then since $(A,B)$ is an
ordered tough-pair, necessarily $v_{u}\in Y\cup Z$. However, since $v_{u}$ is
not identified to $s$, $v_{u}\notin Y^{\circ}\cup Y^{+}$ and since
$D*[\\{y_{i}|~{}i\in I_{B}\\}]$ has no edge, $Y^{\star}=\emptyset$ by 4.55.
Furthermore, $v_{u}$ cannot belong to $\\{y_{i}~{}|~{}i\in I_{A}^{2}\\}\cup
Y^{-}$ for otherwise, since $v_{s}\in Z^{+}$ and $(A,B)$ is an ordered tough-
pair, there exist $i,j\in I_{A}^{2}$ such that $i<j$ and $(y_{i},z_{j})\in
E(D^{*})$, a contradiction to the fact that $D[\\{y_{i},x_{i}~{}|~{}i\in
I_{B}\\}]$ is transitively equivalent to $O_{1}^{\ell_{5}(t)}$. Thus, it must
be that $v_{u}\in Z$. However, since $v_{s}\in Z^{+}$, $v_{u}\notin
Z^{\star}\cup Z^{-}\cup Z^{\circ}$ by 4.55 and $v_{u}\notin\\{z_{i}~{}|~{}i\in
I_{B}^{2}\\}$ by definition of $Z^{+}$. Thus, we conclude that $v_{u}\in
Z^{+}$, a contradiction since $v_{u}$ is not identified to $s$.

Assume now that $t$ exists and suppose to the contrary that there exists $u\in
V(D_{I})$ such that $u\in N^{+}_{D_{I}}(t)$. Then there exist $v_{t},v_{u}\in
V(D)$ such that $v_{t}$ is identified to $t$, $v_{u}$ is identified to $u$ and
$(v_{t},v_{u})\in E(D)$. Since the sink vertex t of $D$ (if any) has
out0degree zero in $D$, necessarily $v_{t}\neq\texttt{t}$. Furthermore,
$v_{t}$ cannot belong to $X^{\circ}\cup X^{-}\cup Z^{\circ}\cup Z^{-}$:
indeed, if, say, $v_{t}\in X^{\circ}\cup X^{-}$ (the case where $v_{t}\in
Z^{\circ}\cup Z^{-}$ is symmetric) then by 4.57, $v_{u}\in X^{\circ}\cup
X^{-}$, a contradiction since $v_{u}$ is not identified to $t$. Thus, it must
be that $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively equivalent to
$O_{1}^{\ell_{5}(t)}$ and $v_{t}\in W^{-}$, or $D[\\{y_{i},z_{i}~{}|~{}i\in
I_{B}\\}]$ is transitively equivalent to $O_{1}^{\ell_{5}(t)}$ and $v_{t}\in
Y^{-}$. Assume without loss of generality that the latter holds (the other
case is symmetric). Then since $(A,B)$ is an ordered tough-pair, necessarily
$v_{u}\in Y\cup Z$. However, since $v_{u}$ is not identified to $t$,
$v_{u}\notin Z^{\circ}\cup Z^{-}$ and since $D*[\\{z_{i}|~{}i\in I_{B}\\}]$
has no edge, $Z^{\star}=\emptyset$ by 4.55. Furthermore, $v_{u}$ cannot belong
to $\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}\cup Z^{+}$ for otherwise, since $v_{t}\in
Y^{-}$ and $(A,B)$ is an ordered tough-pair, there exist $i,j\in I_{B}^{2}$
such that $i<j$ and $(y_{i},z_{j})\in E(D^{*})$, a contradiction to the fact
that $D[\\{y_{i},x_{i}~{}|~{}i\in I_{B}\\}]$ is transitively equivalent to
$O_{1}^{\ell_{5}(t)}$. Thus, it must be that $v_{u}\in Y$. However, since
$v_{t}\in Y^{-}$, $v_{u}\notin Y^{\star}\cup Y^{\circ}\cup Y^{+}$ by 4.55 and
$v_{u}\notin\\{y_{i}~{}|~{}i\in I_{B}^{2}\\}$ by definition of $Y^{-}$. Thus,
we conclude that $v_{u}\in Y^{-}$, a contradiction since $v_{u}$ is not
identified to $t$. ∎

######  Claim 4.60.

For any $i\in[4]$, if $D[\\{w_{j},x_{j}~{}|~{}j\in I_{A}\\}]$ is transitively
equivalent to $O_{i}^{\ell_{5}(t)}$ then $D_{I}[\\{w_{j},x_{j}~{}|~{}j\in
I_{A}^{2}\\}]$ is transitively equivalent to $O_{i}^{4g(t)+2}$.

###### Proof.

Let us first show that if $D[\\{w_{i}~{}|~{}i\in I_{A}\\}]$ has no edge then
$D_{I}[\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}]$ has no edge as well. Assume that
$D[\\{w_{i}~{}|~{}i\in I_{A}\\}]$ has no edge, that is,
$D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively equivalent to
$O_{1}^{\ell_{5}(t)}$ or $O_{3}^{\ell_{5}(t)}$. Then by 4.55,
$W^{\star}=\emptyset$. Suppose first that $D[\\{w_{i},x_{i}~{}|~{}i\in
I_{A}\\}]$ is transitively equivalent to $O_{1}^{\ell_{5}(t)}$. Then every
vertex in $W^{\circ}\cup W^{+}$ is identified to $s$ and every vertex in
$W^{-}$ is identified to $t$ where $d^{-}_{D_{I}}(s)=d^{+}_{D_{I}}(t)=0$ by
4.59. Since, in this case, every vertex in $X$ is identified either to $s$,
$t$ or itself and no other identification may create an edge between two
vertices of $\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$, we conclude that
$D_{I}[\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}]$ has no edge. Suppose second that
$D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively equivalent to
$O_{3}^{\ell_{5}(t)}$. Then every vertex in $W^{\circ}\cup W^{+}$ is
identified to $s$ and every vertex in $X^{\circ}\cup X^{-}$ is identified to
$t$ where $d^{-}_{D_{I}}(s)=d^{+}_{D_{I}}(t)=0$ by 4.59. Since every vertex in
$W^{-}\cup X^{\star}\cup X^{+}$ is identified to a vertex in
$\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$ and no other identification may create an
edge between two vertices of $\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$, we conclude
that $D_{I}[\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}]$ has no edge.

Second, let us show that if $D[\\{w_{i}~{}|~{}i\in I_{A}\\}]$ is transitively
equivalent to the directed path $w_{\min I_{A}}\rightarrow w_{\min
I_{A}+1}\rightarrow\ldots\rightarrow w_{\max I_{A}}$ then
$D_{I}[\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}]$ is transitively equivalent to the
directed path $w_{\min I_{A}^{2}}\rightarrow w_{\min
I_{A}^{2}+1}\rightarrow\ldots\rightarrow w_{\max I_{A}^{2}}$. Assume that
$D[\\{w_{i}~{}|~{}i\in I_{A}\\}]$ is transitively equivalent to this directed
path, that is, $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively
equivalent to $O_{2}^{\ell_{5}(t)}$ or $O_{4}^{\ell_{5}(t)}$. Note that since
$I_{A}^{2}\subseteq I_{A}$, it is enough to show that no edge from a vertex in
$\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$ to a vertex in $\\{w_{i}~{}|~{}i\in
I_{A}^{2}\\}$ of smaller index is created (we refer to such an edge as a _bad
edge_ in the following). First, since every vertex $w_{j}\in W^{\star}\cup
W^{-}$ is identified to the vertex $w_{j^{\prime}}\in\\{w_{i}~{}|~{}i\in
I_{A}^{2}\\}$ such that $j^{\prime}=\max\\{i\in I_{A}^{2}~{}:~{}i\leq j\\}$,
no bad edge is created here. Now if $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is
transitively equivalent to $O_{2}^{\ell_{5}(t)}$ (note that, in this case,
$X^{\star}=\emptyset$ by 4.55), then every vertex $x_{j}\in X^{+}$ is
identified to the vertex $w_{j^{\prime}}\in\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$
such that $j^{\prime}=\min\\{i\in I_{A}^{2}~{}:~{}j\leq i\\}$ and so, no bad
edge is created here; and if $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is
transitively equivalent to $O_{4}^{\ell_{5}(t)}$, then every vertex in
$X^{\star}\cup X^{+}$ is identified to a vertex in $\\{x_{i}~{}|~{}i\in
I_{A}^{2}\\}$ and thus, no bad edge is created here as well. Since every
vertex in $W^{\circ}\cup W+$ is identified to $s$ and every vertex in
$X^{\circ}\cup X^{-}$ is identified to $t$ where
$d^{-}_{D_{I}}(s)=d^{+}_{D_{I}}(t)=0$ by 4.59, no bad edge is created with
these identifications; and since no other identification may create a bad
edge, we conclude that $D_{I}[\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}]$ is indeed
transitively equivalent to the directed path $w_{\min
I_{A}^{2}}\rightarrow\ldots\rightarrow w_{\max I_{A}^{2}}$.

Consider next $X$. As in the case of $W$, let us first show that if
$D[\\{x_{i}~{}|~{}i\in I_{A}\\}]$ has no edge then $D_{I}[\\{x_{i}~{}|~{}i\in
I_{A}^{2}\\}]$ has no edge as well. Assume that $D[\\{x_{i}~{}|~{}i\in
I_{A}\\}]$ has no edge, that is, $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is
transitively equivalent to $O_{1}^{\ell_{5}(t)}$ or $O_{2}^{\ell_{5}(t)}$.
Then by 4.55, $X^{\star}=\emptyset$. Now if $D[\\{w_{i},x_{i}~{}|~{}i\in
I_{A}\\}]$ is transitively equivalent to $O_{1}^{\ell_{5}(t)}$, we conclude,
symmetrically to the case of $W$, that $D_{I}[\\{x_{i}~{}|~{}i\in
I_{A}^{2}\\}]$ has no edge. Suppose therefore that
$D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively equivalent to
$O_{2}^{\ell_{5}(t)}$. Since then, every vertex in $X^{\circ}\cup X^{-}$ is
identified to $t$, every vertex in $W^{\circ}\cup W^{+}$ is identified to $s$
where $d^{-}_{D_{I}}(s)=d^{+}_{D_{I}}(t)=0$ by 4.59, and every vertex in
$X^{+}\cup W^{\star}\cup W^{-}$ is identified to a vertex in
$\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$, no edge between two vertices in
$\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$ is created with these identifications.
Since no other identification may create an edge between two vertices in
$\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$, we conclude that
$D_{I}[\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}]$ has no edge in this case as well.

Let us next show that if $D[\\{x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively
equivalent to the directed path $x_{\min I_{A}}\rightarrow x_{\min
I_{A}+1}\rightarrow\ldots\rightarrow x_{\max I_{A}}$ then
$D_{I}[\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}]$ is transitively equivalent to the
directed path $x_{\min I_{A}^{2}}\rightarrow x_{\min
I_{A}^{2}+1}\rightarrow\ldots\rightarrow x_{\max I_{A}^{2}}$. Assume that
$D[\\{x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively equivalent to this directed
path, that is, $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is transitively
equivalent to $O_{3}^{\ell_{5}(t)}$ or $O_{4}^{\ell_{5}(t)}$. Note that since
$I_{A}^{2}\subseteq I_{A}$, it is enough to show that no edge from a vertex in
$\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$ to a vertex in $\\{x_{i}~{}|~{}i\in
I_{A}^{2}\\}$ of smaller index is created (we refer to such an edge as a _bad
edge_ in the following). First, since every vertex $x_{j}\in X^{\star}\cup
X^{+}$ is identified to the vertex $x_{j^{\prime}}\in\\{w_{i}~{}|~{}i\in
I_{A}^{2}\\}$ such that $j^{\prime}=\min\\{i\in I_{A}^{2}~{}:~{}j\leq i\\}$,
no bad edge is created here. Now if $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is
transitively equivalent to $O_{3}^{\ell_{5}(t)}$ (note that, in this case,
$W^{\star}=\emptyset$ by 4.55), then every vertex $w_{j}\in W^{-}$ is
identified to the vertex $x_{j^{\prime}}\in\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$
such that $j^{\prime}=\max\\{i\in I_{A}^{2}~{}:~{}i\leq j\\}$ and so, no bad
edge is created here; and if $D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}\\}]$ is
transitively equivalent to $O_{4}^{\ell_{5}(t)}$, then every vertex in
$W^{\star}\cup W^{-}$ is identified to a vertex in $\\{w_{i}~{}|~{}i\in
I_{A}^{2}\\}$ and thus, no bad edge is created here as well. Since every
vertex in $X^{\circ}\cup X^{-}$ is identified to $t$ and every vertex in
$W^{\circ}\cup W+$ is identified to $s$ where
$d^{-}_{D_{I}}(s)=d^{+}_{D_{I}}(t)=0$ by 4.59, no bad edge is created with
these identifications; and since no other identification may create a bad
edge, we conclude that $D_{I}[\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}]$ is indeed
transitively equivalent to the directed path $x_{\min
I_{A}^{2}}\rightarrow\ldots\rightarrow x_{\max I_{A}^{2}}$.

By combining the above four properties, we conclude that if
$D[\\{w_{j},x_{j}~{}|~{}j\in I_{A}\\}]$ is transitively equivalent to
$O_{i}^{\ell_{5}(t)}$ for some $i\in[4]$, then
$D_{I}[\\{w_{j},x_{j}~{}|~{}j\in I_{A}^{2}\\}]$ is transitively equivalent to
$O_{i}^{|I_{A}^{2}|}$; and since $|I_{A}^{2}|=4g(t)+2$, the claims follows. ∎

Symmetrically to 4.60, we have the following.

######  Claim 4.61.

For any $i\in[4]$, if $D[\\{y_{j},z_{j}~{}|~{}j\in I_{B}\\}]$ is transitively
equivalent to $O_{i}^{\ell_{5}(t)}$ then $D_{I}[\\{y_{j},z_{j}~{}|~{}j\in
I_{B}^{2}\\}]$ is transitively equivalent to $O_{i}^{4g(t)+2}$.

Now note that since every vertex in $A$ ($B$, respectively) is identified
either to $s$, $t$ or a vertex in $A$ ($B$, respectively) and
$d^{-}_{D_{I}}(s)=d^{+}_{D_{I}}(t)=0$ by 4.59, no edge between $A$ and $B$ is
created by these identifications that didn’t already exist. This implies in
particular that if there is no edge in $D$ from $\\{w_{i}~{}|~{}i\in
I_{A}^{2}\\}$ to $\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}$ and from
$\\{y_{i}~{}|~{}i\in I_{B}^{2}\\}$ to $\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$ then
by Claims 4.60 and 4.61, $D_{I}-\\{s,t\\}$ is transitively equivalent to the
disjoint union of $O_{i}^{4g(t)+2}$ and $O_{j}^{4g(t)+2}$, where
$O_{i}^{4g(t)+2}$ ($O_{j}^{4g(t)+2}$, respectively) is the digraph to which
$D[\\{w_{a},x_{a}~{}|~{}a\in I_{A}\\}]$ ($D[\\{y_{a},z_{a}~{}|~{}a\in
I_{B}^{2}\\}]$, respectively) is transitively equivalent. Thus, since we may
safely identify, e.g., the two first edges of $D[\\{w_{i},x_{i}~{}|~{}i\in
I_{A}^{2}\\}]$ (that is, $(w_{\min I_{A}^{2}},x_{\min I_{A}^{2}})$ and
$(w_{\min I_{A}^{2}+1},x_{\min I_{A}^{2}+1})$) to the third edge of
$D[\\{w_{i},x_{i}~{}|~{}i\in I_{A}^{2}\\}]$ and proceed similarly with
$D[\\{y_{i},z_{i}~{}|~{}i\in I_{B}^{2}\\}]$, we conclude that, in this case,
$D_{I}$ can be identified to an almost $4g(t)$-hard matching pattern. Note
that, more generally, if there is no edge in $D$ from $\\{w_{i}~{}|~{}i\in
I_{A}^{2}\\}$ to $\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}$ then
$D_{I}[\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}\cup\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}]$
is transitively equivalent to the disjoint union of $D_{I}[\\{w_{i}~{}|~{}i\in
I_{A}^{2}\\}]$ and $D_{I}[\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}]$ (in particular,
no vertex $r_{WZ}$ may be created by identifications); and the same holds for
$\\{y_{i}~{}|~{}i\in I_{B}^{2}\\}$ and $\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$.

Assume henceforth that there is every edge either from $\\{w_{i}~{}|~{}i\in
I_{A}^{2}\\}$ to $\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}$, from $\\{y_{i}~{}|~{}i\in
I_{B}^{2}\\}$ to $\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$, or both. Note that since
we assume $D$ not to contain a $g(t)$-induced-biclique, if there is every edge
from $\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$ to $\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}$
then at least one of $D_{I}[\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}]$ and
$D_{I}[\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}]$ has edges (in fact, is transitively
equivalent to a directed path by Claims 4.60 and 4.61); and the same holds for
$\\{y_{i}~{}|~{}i\in I_{B}^{2}\\}$ and $\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$. Now
if there is every edge in $D$ from $\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$ to
$\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}$ and both $D_{I}[\\{w_{i}~{}|~{}i\in
I_{A}^{2}\\}]$ and $D_{I}[\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}]$ are transitively
equivalent to a directed path, then $D_{I}\\{w_{i}~{}|~{}i\in
I_{A}^{2}\\}\cup\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}]$ is transitively equivalent
to the directed path $w_{\min I_{A}^{2}}\rightarrow\ldots\rightarrow w_{\max
I_{A}^{2}}\rightarrow z_{\min I_{B}^{2}}\rightarrow\ldots\rightarrow z_{\max
I_{B}^{2}}$ in which case we need not introduce the vertex $r_{WZ}$; and we
conclude symmetrically with $\\{y_{i}~{}|~{}i\in I_{B}^{2}\\}$ and
$\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$.

By the above discussion, there remains to consider the case where every edge
in $D$ from $\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$ to $\\{z_{i}~{}|~{}i\in
I_{B}^{2}\\}$ (or from $\\{y_{i}~{}|~{}i\in I_{B}^{2}\\}$ to
$\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$) exist and exactly one of
$D_{I}[\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}]$ and $D_{I}[\\{z_{i}~{}|~{}i\in
I_{B}^{2}\\}]$ ($D_{I}[\\{y_{i}~{}|~{}i\in I_{B}^{2}\\}]$ and
$D_{I}[\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}]$, respectively) has no edge. In this
case, we devise the following identification rules (for simplicity, we still
call $D_{I}$ the graph resulting from these identifications).

######  Identification Rule 13.

If there is every edge from $\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$ to
$\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}$ in $D_{I}$ and exactly one of
$D_{I}^{*}[\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}]$ and
$D_{I}^{*}[\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}]$ has no edge, then proceed as
follows.

  1. 1.

If $D_{I}^{*}[\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}]$ has no edge then identify
$y_{\min I_{B}^{2}}$ to $s$ and rename $z_{\min I_{B}^{2}}$ as $r_{WZ}$.

  2. 2.

If $D_{I}^{*}[\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}]$ has no edge then identify
$x_{\max I_{A}^{2}}$ to $t$ and rename $w_{\max I_{A}^{2}}$ as $r_{WZ}$.

######  Claim 4.62.

If 13 has been applied then it still holds that
$d^{-}_{D_{I}}(s)=d^{+}_{D_{I}}(t)=0$. Furthermore,
$N^{-}_{D_{I}}(r_{WZ})\setminus\\{s\\}=\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$ and
$N^{+}_{D_{I}}(r_{WZ})\setminus\\{t\\}=\\{z_{i}~{}|~{}i\in
I_{B}^{2}\setminus\\{\min I_{B}^{2}\\}\\}$.

###### Proof.

Assume that 13 has been applied and that $D_{I}^{*}[\\{w_{i}~{}|~{}i\in
I_{A}^{2}\\}]$ has no edge (the case where $D_{I}^{*}[\\{z_{i}~{}|~{}i\in
I_{B}^{2}\\}]$ has no edge is symmetric). Then, by assumption,
$D_{I}^{*}[\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}]$ must have edges; and in fact, by
4.61 and definition of $I_{B}^{2}$, $D_{I}^{*}[\\{z_{i}~{}|~{}i\in
I_{B}^{2}\\}]$ must be transitively equivalent to the directed path $z_{\min
I_{B}^{2}}\rightarrow z_{\min I_{B}^{2}+1}\rightarrow\ldots\rightarrow z_{\max
I_{B}^{2}}$. It follows that
$N^{+}_{D_{I}}(r_{WZ})\setminus\\{t\\}=N^{+}_{D_{I}}(z_{\min
I_{B}^{2}})\setminus\\{t\\}=\\{z_{i}~{}|~{}i\in I_{B}^{2}\setminus\\{\min
I_{B}^{2}\\}\\}$ and since, by assumption, there is every from
$\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$ to $\\{z_{i}~{}|~{}i\in I_{B}^{2}\\}$ in
$D_{I}$, we conclude that
$N^{-}_{D_{I}}(r_{WZ})\setminus\\{s\\}=\\{w_{i}~{}|~{}i\in I_{A}^{2}\\}$.
Finally to see that $d^{-}_{D_{I}}(s)=d^{+}_{D_{I}}(t)=0$, note that by
construction, the only possible in-neighbor for $y_{\min I_{B}^{2}}$ is $s$
and the only possible out-neighbor for $x_{\max I_{A}^{2}}$ is $t$. ∎

######  Identification Rule 14.

If there is every edge from $\\{y_{i}~{}|~{}i\in I_{B}^{2}\\}$ to
$\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$ in $D_{I}$ and exactly one of
$D_{I}^{*}[\\{y_{i}~{}|~{}i\in I_{B}^{2}\\}]$ and
$D_{I}^{*}[\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}]$ has no edge, then proceed as
follows.

  1. 1.

If $D_{I}^{*}[\\{y_{i}~{}|~{}i\in I_{B}^{2}\\}]$ has no edge then identify
$w_{\min I_{A}^{2}}$ to $s$ and rename $x_{\min I_{A}^{2}}$ as $r_{YX}$.

  2. 2.

If $D_{I}^{*}[\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}]$ has no edge then identify
$z_{\max I_{B}^{2}}$ to $t$ and rename $y_{\max I_{B}^{2}}$ as $r_{YX}$.

Symmetrically to 4.62, we have the following.

######  Claim 4.63.

If 14 has been applied then it still holds that
$d^{-}_{D_{I}}(s)=d^{+}_{D_{I}}(t)=0$. Furthermore,
$N^{-}_{D_{I}}(r_{YX})\setminus\\{s\\}=\\{y_{i}~{}|~{}i\in
I_{B}^{2}\setminus\\{\max I_{B}^{2}\\}\\}$ and
$N^{+}_{D_{I}}(r_{YX})\setminus\\{t\\}=\\{x_{i}~{}|~{}i\in I_{A}^{2}\\}$.

Note finally that 13 reduces the size of $E(D_{I}-\\{s,t\\})$ by one as does
14 (it may be that the size of $\\{(w_{i},x_{i})~{}|~{}i\in I_{A}^{2}\\}$
reduces by two while the size of $\\{(y_{i},z_{i})~{}|~{}i\in I_{B}^{2}\\}$
remains the same if 13.2 and 14.1 are applied, and vice-versa). Since we may
always safely identify consecutive edges in $\\{(w_{i},x_{i})~{}|~{}i\in
I_{A}^{2}\\}$ or $\\{(y_{i},z_{i})~{}|~{}i\in I_{B}^{2}\\}$ to reduce their
size to $4g(t)$ (as done above), we conclude that $D_{I}$ can be identified to
a digraph transitively equivalent to an almost $4g(t)$-hard matching pattern.

There remains to show how to obtain a $g(t)$-hard matching pattern from an
almost $4g(t)$-hard matching pattern. To this end, let $H$ be an almost
$4g(t)$-hard matching pattern. We first show how to handle the source vertex
from item 3 in Definition 4.48 and then how to handle the sink vertex from
item 4 in Definition 4.48.

Let $s$ be the vertex of $H$ such that $N^{-}(s)=\emptyset$ and
$N^{+}(s)\subseteq W\cup X\cup Y\cup Z$. Suppose first that $N^{+}(s)\cap
W\neq\emptyset$ and let $I_{1}\subseteq[4g(t)]$ be the set of indices such
that $N^{+}(s)\cap W=\\{w_{i}~{}|~{}i\in I_{1}\\}$. By the pigeonhole
principle, either (1) $|I_{1}|\geq 4g(t)/2$ or (2) $|[4g(t)]\setminus
I_{1}|\geq 4g(t)/2$. If (1) holds then we proceed as follows.

  * •

For every $j<\min I_{1}$, we identify $w_{j}$ and $x_{j}$ to $w_{\min I_{1}}$
and $x_{\min I_{1}}$, respectively.

  * •

For every consecutive $i<i^{\prime}\in I_{1}$ and for every
$j\in]i,i^{\prime}[$, we identify $w_{j}$ and $x_{j}$ with $w_{i}$ and
$x_{i}$, respectively.

  * •

For every $j>\max I_{1}$, we identify $w_{j}$ and $x_{j}$ to $w_{\max I_{1}}$
and $x_{\max I_{1}}$, respectively.

Suppose next that (2) holds. If $H$ contains the path $w_{1}\rightarrow
w_{2}\rightarrow\ldots\rightarrow w_{4g(t)}$ then we simply identify $s$ to
$w_{1}$. Let us therefore assume that $H$ does not contain this path. If $H$
contains the path $x_{1}\rightarrow x_{2}\rightarrow\ldots\rightarrow
x_{4g(t)}$ then for every $i\in I_{1}$, we identify $w_{i}$ to $x_{i}$ and
further identify $s$ to $x_{1}$. Finally, if $H$ does not contain this path
then we identify every vertex in $\\{w_{i},x_{i}~{}|~{}i\in
I_{1}\\}\cup\\{s\\}$ to $w_{1}$.

Now suppose that $N^{+}(s)\cap W=\emptyset$ and $N^{+}(s)\cap X\neq\emptyset$.
Let $I_{1}\subseteq[4g(t)]$ be the set of indices such that $N^{+}(s)\cap
W=\\{w_{i}~{}|~{}i\in I_{1}\\}$. By the pigeonhole principle, either (1)
$|I_{1}|\geq 4g(t)/2$ or (2) $|[4g(t)]\setminus I_{1}|\geq 4g(t)/2$. If (1)
holds then we proceed as follows.

  * •

For every $j<\min I_{1}$, we identify $w_{j}$ and $x_{j}$ to $w_{\min I_{1}}$
and $x_{\min I_{1}}$, respectively.

  * •

For every consecutive $i<i^{\prime}\in I_{1}$ (that is,
$I_{1}\cap[i,^{\prime}i]=\\{i,i^{\prime}\\}$) and for every
$j\in]i,i^{\prime}[$, we identify $w_{j}$ and $x_{j}$ with $w_{i}$ and
$x_{i}$, respectively.

  * •

For every $j>\max I_{1}$, we identify $w_{j}$ and $x_{j}$ to $w_{\max I_{1}}$
and $x_{\max I_{1}}$, respectively.

Suppose next that (2) holds. If $H$ contains the path $x_{1}\rightarrow
x_{2}\rightarrow\ldots\rightarrow x_{4g(t)}$ then we simply identify $s$ to
$x_{1}$. Let us therefore assume that $H$ does not contain this path. If $H$
contains the path $w_{1}\rightarrow w_{2}\rightarrow\ldots\rightarrow
w_{4g(t)}$ then for every $i\in I_{1}$, we identify $x_{i}$ to $w_{i}$ and
further identify $s$ to $w_{1}$. Finally, if $H$ does not contain this path
then we identify every vertex in $\\{w_{i},x_{i}~{}|~{}i\in
I_{1}\\}\cup\\{s\\}$ to $w_{1}$.

By proceeding symmetrically with $Y$ and $Z$, we may identify $H$ to an almost
$2g(t)$-hard matching pattern $H_{1}$ in which $s$ satisfies item 3 of
Definition 1.5. Now let $t$ be the vertex of $H$ (and of $H_{1}$) such that
$N^{+}(t)=\emptyset$ and $N^{-}(t)\subseteq W\cup X\cup Y\cup Z$. Then using
similar arguments, we may further identify $H_{1}$ to an almost $g(t)$-hard
matching pattern $H_{2}$ in which $s$ still satisfies item 3 of Definition 1.5
and $t$ satisfies item 4 of Definition 1.5, that is, $H_{2}$ is a $g(t)$-hard
matching pattern which concludes the proof. ∎

###  4.4 Cleaning the induced-biclique with minimal edges

In this section, we prove Lemma 4.8 restated below.

See 4.8

###### Proof.

Let $(A,B)$ be a $9t$-biclique in $D$ such the edges of $A\cup B$ are minimal
edges of $D$, and such that $(A,B)$ is a $9t$-induced-biclique in $D^{\star}$.
Then $A,B$ are independent sets in $D^{\star}$.

We first claim that for any $v\in V(D)\setminus(A\cup B)$, it is not the case
that $N^{-}_{D^{\star}}(v)\cap(A\cup B)\neq\emptyset$ and
$N^{+}_{D^{\star}}(v)\cap(A\cup B)\neq\emptyset$. For the sake of
contradiction, say it is the case. Let $x\in N^{-}_{D^{\star}}(v)\cap(A\cup
B)$ and let $y\in N^{+}_{D^{\star}}(v)\cap(A\cup B)$. Then there exists an
$(x,y)$-path in $D$ of length strictly greater than $1$. If $x,y\in A$ (resp.
$x,y\in B$), then this contradicts that $A$ (resp. $B$) is an independent set
in $D^{*}$. If $x\in A$ and $y\in B$, then this contradicts the minimality of
the edges of the $(A,B)$-biclique. If $x\in B$ and $y\in A$, then this
contradicts the definition of an $(A,B)$-biclique.

Let $V_{\texttt{s}}\subseteq V(D)\setminus(A\cup B)$ such that for each $v\in
V_{\texttt{s}}$, $N^{+}_{D^{\star}}(v)\neq\emptyset$ and
$N^{-}_{D^{\star}}(v)\cap(A\cup B)=\emptyset$. Let
$V_{\texttt{t}}=V(D)\setminus(A\cup B\cup V_{\texttt{s}})$. Then from the
claim in the above paragraph, for each $v\in V_{\texttt{t}}$,
$N^{+}_{D^{\star}}(v)\cap(A\cup B)=\emptyset$. Observe that
$V_{\texttt{s}}\uplus V_{\texttt{t}}$ partition the vertex set
$V(D)\setminus(A\cup B)$. If $V_{\texttt{s}}\neq\emptyset$, then identify the
vertices of $V_{\texttt{s}}$ into s, if $V_{\texttt{t}}\neq\emptyset$, then
identify the vertices of $V_{\texttt{t}}$ into t. Let $\widehat{D}$ be the
resulting digraph. We now show that
$E(V_{\texttt{t}},V_{\texttt{s}})=\emptyset$. For the sake of contradiction,
say $u\in V_{\texttt{t}}$ and $v\in V_{\texttt{s}}$ such that $(u,v)\in
E(D^{\star})$. Then $N^{+}_{D^{\star}}(u)\cap(A\cup B)\neq\emptyset$. Since
$u\not\in V_{\texttt{s}}$, $N^{-}_{D^{\star}}(u)\neq\emptyset$. But this
contradicts the claim in the second paragraph. Thus, we conclude that
$N^{-}_{\widehat{D}}(\texttt{s}),N^{+}_{\widehat{D}}(\texttt{t})=\emptyset$.

Now let $t^{\prime}=9t$. Recall that $A,B$ are ordered sets, say
$A=(a_{1},\ldots,a_{t^{\prime}})$ and $B=(b_{1},\ldots,b_{t^{\prime}})$. Let
$I_{1}\subseteq[t^{\prime}]$ such that for $i\in I_{1}$,
$(\texttt{s},a_{i})\in E(\widehat{D})$. Let $I_{2}\subseteq[t^{\prime}]$ such
that for each $i\in I_{2}$, $(\texttt{s},a_{i})\not\in E(\widehat{D})$ and
$(\texttt{s},b_{i})\in E(\widehat{D})$. Let $I_{3}\subseteq[t^{\prime}]$ such
that for each $i\in I_{3}$, $(\texttt{s},a_{i}),(\texttt{s},b_{i})\not\in
E(\widehat{D})$. Observe that $[t^{\prime}]=I_{1}\uplus I_{2}\uplus I_{3}$.
Let $J_{1}\subseteq[t^{\prime}]$ such that for each $j\in J_{1}$,
$(b_{j},\texttt{t})\in E(\widehat{D})$. Let $J_{2}\subseteq[t^{\prime}]$ such
that for each $j\in J_{2}$, $(b_{j},\texttt{t})\not\in E(\widehat{D})$ and
$(a_{j},\texttt{t})\in E(\widehat{D})$. Let $J_{3}\subseteq[t^{\prime}]$ such
that for each $j\in J_{3}$, $(b_{j},\texttt{t}),(a_{j},\texttt{t})\not\in
E(\widehat{D})$. Observe that $[t^{\prime}]=J_{1}\uplus J_{2}\uplus J_{3}$.

By the pigeon-hole principle, either $|I_{1}|\geq t^{\prime}/3$ or
$|I_{2}|\geq t^{\prime}/3$ or $|I_{3}|\geq t^{\prime}/3$. We consider these
three cases separately.

Case 1. $|I_{1}|\geq t^{\prime}/3$. Suppose first that $|J_{1}\cap
I_{1}|\geq|I_{1}|/3$. Let $A^{\prime}=\\{a_{i}:i\in J_{1}\cap I_{1}\\}$ and
$B^{\prime}=\\{b_{i}:i\in J_{1}\cap I_{1}\\}$. Observe that
$|A^{\prime}|=|B^{\prime}|\geq t^{\prime}/3$. Identify the vertices of
$(A\setminus A^{\prime})\cup(B\setminus B^{\prime})$ with s. Let the resulting
digraph be $\widehat{D^{\prime}}$. Observe that $A^{\prime}\subseteq
N^{+}_{\widehat{D^{\prime}}}(\texttt{s}),B^{\prime}\subseteq
N^{-}_{\widehat{D^{\prime}}}(\texttt{t})$ and $(\texttt{t},\texttt{s})\not\in
E(\widehat{D^{\prime}})$.

Suppose next that $|J_{2}\cap I_{1}|\geq|I_{1}|/3$. Let
$A^{\prime}=\\{a_{i}:i\in J_{2}\cap I_{1}\\}$ and $B^{\prime}=\\{b_{i}:i\in
J_{2}\cap I_{1}\\}$. Observe that $|A^{\prime}|=|B^{\prime}|\geq
t^{\prime}/3$. Identify the vertices of $(A\setminus
A^{\prime})\cup(B\setminus B^{\prime})$ with s. Let the resulting digraph be
$\widehat{D^{\prime}}$. Observe that $A^{\prime}\subseteq
N^{+}_{\widehat{D^{\prime}}}(\texttt{s}),A^{\prime}=N^{-}_{\widehat{D^{\prime}}}(\texttt{t})$
and $(\texttt{t},\texttt{s})\not\in E(\widehat{D^{\prime}})$.

Suppose finally that $|J_{3}\cap I_{1}|\geq|I_{1}|/3$. Let
$A^{\prime}=\\{a_{i}:i\in J_{3}\cap I_{1}\\}$ and $B^{\prime}=\\{b_{i}:i\in
J_{3}\cap I_{1}\\}$. Observe that $|A^{\prime}|=|B^{\prime}|\geq
t^{\prime}/3$. Identify the vertices of $(A\setminus
A^{\prime})\cup(B\setminus B^{\prime})\cup\texttt{t}$ with s. Let the
resulting digraph be $\widehat{D^{\prime}}$. Observe that $A^{\prime}\subseteq
N^{+}_{\widehat{D^{\prime}}}(\texttt{s})$.

Case 2. $|I_{2}|\geq t^{\prime}/3$. Suppose first that $|J_{1}\cap
I_{2}|\geq|I_{2}|/3$. Let $A^{\prime}=\\{a_{i}:i\in J_{1}\cap I_{2}\\}$ and
$B^{\prime}=\\{b_{i}:i\in J_{1}\cap I_{2}\\}$. Observe that
$|A^{\prime}|=|B^{\prime}|\geq t^{\prime}/3$. Identify the vertices of
$(A\setminus A^{\prime})\cup(B\setminus B^{\prime})$ with s. Let the resulting
digraph be $\widehat{D^{\prime}}$. Observe that
$B^{\prime}=N^{+}_{\widehat{D^{\prime}}}(\texttt{s}),B^{\prime}\subseteq
N^{-}_{\widehat{D^{\prime}}}(\texttt{t})$ and $(\texttt{t},\texttt{s})\not\in
E(\widehat{D^{\prime}})$.

Suppose next that $|J_{2}\cap I_{2}|\geq|I_{2}|/3$. Let
$A^{\prime}=\\{a_{i}:i\in J_{2}\cap I_{2}\\}$ and $B^{\prime}=\\{b_{i}:i\in
J_{2}\cap I_{2}\\}$. Observe that $|A^{\prime}|=|B^{\prime}|\geq
t^{\prime}/3$. Identify the vertices of $(A\setminus
A^{\prime})\cup(B\setminus B^{\prime})$ with s. Let the resulting digraph be
$\widehat{D^{\prime}}$. Observe that
$B^{\prime}=N^{+}_{\widehat{D^{\prime}}}(\texttt{s}),A^{\prime}=N^{-}_{\widehat{D^{\prime}}}(\texttt{t})$
and $(\texttt{t},\texttt{s})\not\in E(\widehat{D^{\prime}})$.

Suppose finally that $|J_{3}\cap I_{2}|\geq|I_{2}|/3$. Let
$A^{\prime}=\\{a_{i}:i\in J_{3}\cap I_{2}\\}$ and $B^{\prime}=\\{b_{i}:i\in
J_{3}\cap I_{2}\\}$. Observe that $|A^{\prime}|=|B^{\prime}|\geq
t^{\prime}/3$. Identify the vertices of $(A\setminus
A^{\prime})\cup(B\setminus B^{\prime})\cup\texttt{t}$ with s. Let the
resulting digraph be $\widehat{D^{\prime}}$. Observe that
$B^{\prime}=N^{+}_{\widehat{D^{\prime}}}(\texttt{s})$.

Case 3. $|I_{3}|\geq t^{\prime}/3$. Suppose first that $|J_{1}\cap
I_{3}|\geq|I_{3}|/3$. Let $A^{\prime}=\\{a_{i}:i\in J_{1}\cap I_{3}\\}$ and
$B^{\prime}=\\{b_{i}:i\in J_{1}\cap I_{3}\\}$. Observe that
$|A^{\prime}|=|B^{\prime}|\geq t^{\prime}/3$. Identify the vertices of
$(A\setminus A^{\prime})\cup(B\setminus B^{\prime})$, if any, with s. Let the
resulting digraph be $\widehat{D^{\prime}}$. Observe that if $(A\setminus
A^{\prime})\cup(B\setminus B^{\prime})=\emptyset$, then then
$\texttt{s}\not\in V(\widehat{D^{\prime}})$ and $B\subseteq
N^{-}_{\widehat{D^{\prime}}}(\texttt{t})$. Otherwise, additionally,
$\texttt{s}\in V(D)$ and since $(A,B)$ is an induced biclique,
$B^{\prime}=N^{+}_{\widehat{D^{\prime}}}(\texttt{s})$. Moreover,
$(\texttt{t},\texttt{s})\not\in E(\widehat{D^{\prime}})$.

Suppose next that $|J_{2}\cap I_{3}|\geq|I_{3}|/3$. Let
$A^{\prime}=\\{a_{i}:i\in J_{2}\cap I_{3}\\}$ and $B^{\prime}=\\{b_{i}:i\in
J_{2}\cap I_{3}\\}$. Observe that $|A^{\prime}|=|B^{\prime}|\geq
t^{\prime}/3$. Identify the vertices of $(A\setminus
A^{\prime})\cup(B\setminus B^{\prime})$, if any, with s. Let the resulting
digraph be $\widehat{D^{\prime}}$. If $(A\setminus A^{\prime})\cup(B\setminus
B^{\prime})=\emptyset$, then $\texttt{s}\not\in V(\widehat{D^{\prime}})$ and
$A=N^{-}_{\widehat{D^{\prime}}}(\texttt{t})$. Otherwise, additionally
$\texttt{s}\in V(\widehat{D^{\prime}})$ and since $(A,B)$ is an induced
biclique, $B=N^{+}_{\widehat{D^{\prime}}}(\texttt{s})$. Moreover,
$(\texttt{t},\texttt{s})\not\in E(\widehat{D^{\prime}})$.

Suppose finally that $|J_{3}\cap I_{3}|\geq|I_{3}|/3$. Let
$A^{\prime}=\\{a_{i}:i\in J_{3}\cap I_{3}\\}$ and $B^{\prime}=\\{b_{i}:i\in
J_{3}\cap I_{3}\\}$. Observe that $|A^{\prime}|=|B^{\prime}|\geq t^{\prime}/3$
and $(A\setminus A^{\prime})\cup(B\setminus B^{\prime})\neq\emptyset$ since
$D$ is connected (without loss of generality). Identify the vertices of
$(A\setminus A^{\prime})\cup(B\setminus B^{\prime})\cup\texttt{t}$ with s .
Let the resulting digraph be $\widehat{D^{\prime}}$. Since $(A,B)$ is an
induced biclique and $(A\setminus A^{\prime})\cup(B\setminus
B^{\prime})\neq\emptyset$,
$B^{\prime}=N^{+}_{\widehat{D^{\prime}}}(\texttt{s})$. ∎

##  5 Hardness proofs and lower bounds

This section is devoted to presenting the lower bounds on the complexity of
Planar $\mathcal{D}$-SN for various classes $\mathcal{D}$. First we prove the
combinatorial result Lemma 1.6 that implies that there are no nontrivial class
with subexponential FPT algorithms on planar graphs (Section 5.1). Then we
present reductions from Grid Tiling to Planar $\mathcal{D}$-SN where
$\mathcal{D}$ is the class of diamonds (Section 5.2), hard matching patterns
(Section 5.3.1), or hard biclique patterns (Section 5.3.2).

###  5.1 Finding a star

We present here a short proof that every nontrivial class $\mathcal{D}$ in our
setting contains either all cycles, all in-stars, or all out-stars.

###### Proof (of Lemma 1.6).

Suppose that there is an integer $\alpha$ such that $\mathcal{D}$ does not
contain a cycle, in-star, or out-star on $\alpha$ vertices. This means in
particular that a graph $\mathcal{D}$ cannot have a strongly connected
component with $\alpha$ vertices. Indeed, by selecting $\alpha$ vertices of
the component and identifying every other vertex of the graph with one of
these vertices, we would obtain a strongly connected graph on $\alpha$
vertices, which is transitively equivalent to a cycle on $\alpha$ vertices. It
also follows that a graph $D\in\mathcal{D}$ has less than $\alpha$ strongly
connected components of size larger than 1: otherwise, identifying one vertex
from each such component to a single vertex would create a strongly connected
component of size larger than $\alpha$.

This bound on the size of the strongly connected components implies that
identifying the vertex set of each strongly connected component of some
$D\in\mathcal{D}$ to a single vertex results in an acyclic graph whose size is
at most a factor of $\alpha$ smaller. Therefore, the fact that $\mathcal{D}$
contains arbitrarily large graphs implies that $\mathcal{D}$ contains
arbitrary large acyclic graphs. Furthermore, $\mathcal{D}$ contains
arbitrarily large graphs without isolated vertices: if we have a graph with
$c$ edges and identify every isolated vertex with some vertex $v$, then we get
a graph without isolated vertices and exactly $c$ edges. If we identify the