strongly connected components of such a graph to single vertices, then less
than $\alpha$ isolated vertices can be created (as there are less than
$\alpha$ components of size larger than 1). It follows that $\mathcal{D}$
contains arbitrarily large acyclic graphs with less than $\alpha$ isolated
vertices.

Observe that $D\in\mathcal{D}$ cannot have a path longer than $\alpha+1$:
otherwise, identifying the first and last vertices of the path would create a
member of $D\in\mathcal{D}$ that has a strongly connected component larger
than $\alpha$. This means that every acyclic $D\in\mathcal{D}$ can be
partitioned into $\alpha+2$ levels, that is, $D$ has a topological ordering
with blocks $B_{1}$, $\dots$, $B_{\ell}$ with $\ell\leq\alpha+2$ such that
each block $B_{i}$ is an independent set. If an acyclic graph $D_{c}$ has at
least $(\alpha+2)c$ vertices, then one such block $B_{i}$ has size at least
$c$. Let $D^{*}_{c}$ be obtained by identifying the blocks $B_{1}$, $\dots$,
$B_{i-1}$ to a single vertex $x$, and the blocks $B_{i+1}$, $\dots$,
$B_{\ell}$ to a single vertex $y$. If there are $\alpha$ vertices in $B_{i}$
adjacent to both $x$ and $y$, then identifying $x$ and $y$ creates a strongly
connected component, a contradiction. If there is a set $I\subseteq B_{i}$ of
$\alpha$ vertices that is adjacent only to $x$, then identifying
$(B_{i}\setminus I)\cup\\{x,y\\}$ to a single vertex results in an out-star on
$\alpha+1$ vertices. Similarly, if there is a set $I\subseteq B_{i}$ of
$\alpha$ vertices that is adjacent only to $y$, then identifying
$(B_{i}\setminus I)\cup\\{x,y\\}$ to a single vertex results in an in-star on
$\alpha+1$ vertices. Finally, $I$ cannot have $\alpha$ vertices that are
adjacent to neither $x$ or $y$, because they would be isolated vertices.
Therefore, if $c\geq 4\alpha$, then we arrive to a contradiction in one of the
three cases. ∎

###  5.2 Diamonds

The aim of this section is to prove the following.

######  Theorem 5.1.

For any $\ell\in[4]$, Planar $\mathcal{A}_{\ell}$-Steiner Network is
$\mathsf{W}[1]$-hard parameterized by the number $k$ of terminals and does not
admit an $f(k)\cdot n^{o(\sqrt{k})}$ algorithm for any computable function
$f$, unless $\mathsf{ETH}$ fails.

We only formally prove the statement for pure out-diamonds as it will become
clear from the proof that to handle

  1. 1.

flawed out-diamonds, it suffices to add a vertex $s$ and edges $(s,r_{1})$ and
$(s,r_{2})$ in the construction below;

  2. 2.

pure in-diamonds, it suffices to reverse the direction of every edge in the
construction below; and

  3. 3.

flawed in-diamonds, it suffices to add a vertex $t$ and edges $(r_{1},t)$ and
$(r_{2},t)$, and additionally reverse the direction of every edge in the
construction below.

In the following, we assume that the class of all pure out-diamonds is
$\mathcal{A}_{1}$. To prove the statement, we first introduce the $k\times
k$-Grid Tiling problem, formally defined below.

$k\times k$-Grid Tiling Input: Integers $k,n$ and $k^{2}$ nonempty set
$S_{i,j}\subseteq[n]\times[n]$ where $i,j\in[k]$. Question: For each
$i,j\in[k]$, does there exist an entry $(x_{i,j},y_{i,j})\in S_{i,j}$ such
that • for every $i\in[k]$, $x_{i,1}=x_{i,2}=\ldots=x_{i,k}$ and • for every
$j\in[k]$, $y_{1,j}=y_{2,j}=\ldots=y_{k,j}$?

Throughout the paper, we assume that whenever given a set
$S\subseteq[n]\times[n]$, $1<x,y<n$ holds for every $(x,y)\in S$: it suffices
to increase $n$ by two and replace $(x,y)$ by $(x+1,y+1)$ otherwise.

It was shown [9, Theorem 14.28] that, under $\mathsf{ETH}$, $k\times k$-Grid
Tiling does not admit an algorithm running in time $f(k)\cdot n^{o(k)}$ for
any computable function $f$. To prove Theorem 5.1 for pure out-diamonds, we
give a reduction which transforms an instance of $k\times k$-Grid Tiling into
an instance of (edge-weighted)333We argue at the end of the section that with
polynomially bounded integer weights, the edge-weighted version of the problem
reduces to its unweighted version. Planar $\mathcal{A}_{1}$-Steiner Network
with $O(k^{2})$ terminals. To this end, we design three types of gadgets: the
_connector gadget_ , the _down main gadget_ and the _up main gadget_. The
reduction represents each set of the $k\times k$-Grid Tiling instance with a
copy of the up or down main gadget, and uses the connector gadgets to further
connect these gadgets (see Figure 16). The remainder of this section is
organized as follows. We first introduce the connector gadget and prove in
Lemma 5.2 that it satisfies several desired properties. We then introduce the
down main gadget and prove in Lemma 5.7 that it also satisfies several desired
properties. The up main gadget is introduced thereafter together with its
symmetrical Lemma 5.24. We end the section with the precise description of the
reduction and a proof of its correctness.

Connector gadget. Given an integer $n>0$, the connector gadget $CG_{n}$ is an
edge-weighted planar digraph consisting of $n\times n$ grid, where the vertex
lying at the intersection of column $i$ and row $j$ is denoted by $x_{i,j}$,
and $2n+2$ additional vertices $p_{1},\ldots,p_{n},q_{1},\ldots,q_{n},p,q$.
The adjacencies and edge weights are defined as follows (we fix $N=3n$).

  * •

_Left source edges:_ for every $j\in[n]$, there is an edge $(p_{j},x_{1,j})$.
Together these edges are called left source edges. The weight of each such
edge is set to $N^{2}$.

  * •

_Right source edges:_ for every $j\in[n]$, there is an edge $(q_{j},x_{n,j})$.
Together these edges are called right source edges. The weight of each such
edge is set to $N^{2}$.

  * •

_Top sink edges:_ for every $i\in[n]$, there is an edge $(x_{i,n},p)$.
Together these edges are called top sink edges. The weight of each such edge
is set to $N^{2}$.

  * •

_Bottom sink edges:_ for every $i\in[n]$, there is an edge $(x_{i,1},q)$.
Together these edges are called bottom sink edges. The weight of each such
edge is set to $N^{2}$.

  * •

The $n\times n$ grid is divided in two according to the diagonal $j=n+1-i$:
the vertices on the top-right part (that is, the vertices $x_{i,j}$ such that
$j+i\geq n+1$) are connected with $\leftarrow$ and $\uparrow$ edges, and the
vertices of the bottom-left part (that is, the vertices $x_{i,j}$ such that
$j+i\leq n+1$) are connected with $\rightarrow$ and $\downarrow$ edges. More
specifically, we define the following edges.

    * –

_Up edges_ : for every $i\in[n]$ and every $j\in[n-1]$ such that $j+i\geq
n+1$, there is an edge $(x_{i,j},x_{i,j+1})$. Together these edges are called
up edges.

    * –

_Down edges:_ for every $i\in[n]$ and every $j\in[n]\setminus\\{1\\}$ such
that $j+i\leq n+1$, there is an edge $(x_{i,j},x_{i,j-1})$. Together these
edges are called down edges.

We set the weight of every up/down edge to $N$.

    * –

_Left edges:_ for every $i\in[n]\setminus\\{1\\}$ and every $j\in[n]$ such
that $j+i>n+1$, there is an edge $(x_{i,j},x_{i-1,j})$. Together these edges
are called left edges.

    * –

_Right edges:_ for every $i\in[n-1]$ and every $j\in[n]$ such that $j+i<n+1$,
there is an edge $(x_{i,j},x_{i+1,j})$. Together these edges are called right
edges.

We set the weight of every left/right edge to $1$.

This concludes the construction of the connector gadget $CG_{n}$ (see Figure
13 for an illustration of the connector gadget for $n=4$). In the following,
we call the vertices $p_{1},\ldots,p_{n}$ the _left vertices_ , the vertices
$q_{1},\ldots,q_{n}$ the _right vertices_ and the vertices $p,q$ the _terminal
vertices_. We further set

$C_{n}^{*}=4N^{2}+(n-1)N+n-1.$

A set $E\subseteq E(CG_{n})$ satisfies the _connectedness_ property if the
following hold in $E$:

  * •

$p$ can be reached from some right vertex and from some left vertex;

  * •

$q$ can be reached from some right vertex and from some left vertex.

A set $E\subseteq E(CG_{n})$ satisfying the connectedness property
_represents_ an integer $j\in[n]$ if the only left source edge in $E$ is the
one incident to $p_{j}$ and the only right source edge in $E$ is the one
incident to $q_{j}$ (see Figure 13 for a set of edges representing 2).

$p_{1}$$p_{2}$$p_{3}$$p_{4}$$q_{1}$$q_{2}$$q_{3}$$q_{4}$$q$$p$ Figure 13: The
connector gadget for $n=4$. A set of edges representing 2 is highlighted.

######  Lemma 5.2.

For any integer $n>0$, the connector gadget $CG_{n}$ satisfies the following
properties.

  * (1)

For every $j\in[n]$, there exists a set $E_{j}\subseteq E(CG_{n})$ of weight
$C_{n}^{*}$ representing $j$.

  * (2)

If there exists a set $E\subseteq E(CG_{n})$ of weight at most $C_{n}^{*}$
satisfying the connectedness property, then $E$ has weight exactly $C_{n}^{*}$
and represents some integer $j\in[n]$.

###### Proof.

To prove (1), it suffices to take $E_{j}$ to be the union of the following
sets of edges:

  * •

$\\{(p_{j},x_{1,j}),(q_{j},x_{n,j}),(x_{n+1-j,n},p),(x_{n+1-j,1},q)\\}$;

  * •

$\\{(x_{i,j},x_{i+1,j})~{}|~{}1\leq i\leq n-j\\}$;

  * •

$\\{(x_{i,j},x_{i-1,j})~{}|~{}n+2-j\leq i\leq n\\}$;

  * •

$\\{(x_{n+1-j,\ell},x_{n+1-j,\ell+1})~{}|~{}j\leq\ell\leq n-1\\}$; and

  * •

$\\{(x_{n+1-j,\ell},x_{n+1-j,\ell-1})~{}|~{}2\leq\ell\leq j\\}$.

It is not difficult to see that $E_{j}$ represents $j$ and has weight
$C_{n}^{*}$.

Next, suppose that $E\subseteq E(CG_{n})$ is a set of weight at most
$C_{n}^{*}$ satisfying the connectedness property. Let us show that $E$ has
weight exactly $C_{n}^{*}$ and represents some integer $j\in[n]$. To this end,
we prove the following claims.

######  Claim 5.3.

$E$ contains exactly one left source edge, one right source edge, one top sink
edge and one bottom sink edge.

###### Proof.

Since $E$ satisfies the connectedness property, it contains at least one left
source edge, one right source edge, one top sink edge and one bottom sink
edge. Now if $E$ contains at least two left source edges (the other cases are
symmetric), then the weight of $E$ is at least $5N^{2}$; however, by
definition,

$C_{n}^{*}=4N^{2}+(n-1)N+n-1<4N^{2}+nN+nN<5N^{2}$

as $N=3n>2n$, a contradiction. ∎

In the following, we let $p_{j_{1}}$ be the left vertex incident to the left
source edge in $E$ and $q_{j_{2}}$ be the right vertex incident to the right
source edge in $E$.

######  Claim 5.4.

For every $j\in[n-1]$, $E$ contains exactly one (up or down) edge with one
endvertex on row $j$ and one endvertex one row $j+1$. In particular, $E$
contains exactly $n-1$ up/down edges.

###### Proof.

First note that if there exists $j\in[n-1]$ such that $E$ contains no (up or
down) edge with one endvertex on row $j$ and the other endvertex on row $j+1$,
then either $j_{1}\leq j$ in which case $p_{j_{1}}$ cannot reach $p$ in $E$,
or $j_{1}>j$ in which case $p_{j_{1}}$ cannot reach $q$ in $E$, a
contradiction in both cases to the connectedness of $E$. Thus, for every
$j\in[n-1]$, $E$ contains at least one (up or down) edge with one endvertex on
row $j$ and the other endvertex on row $j+1$; in particular, $E$ contains at
least $n-1$ up/down edges. Now if $E$ contains at least $n$ up/down edges then
by 5.3, the weight of $E$ is at least $4N^{2}+nN$; however, by definition,

$C_{n}^{*}=4N^{2}+(n-1)N+n-1<4N^{2}+(n-1)N+n<4N^{2}+nN$

as $N=3n>n$, a contradiction. ∎

######  Claim 5.5.

$E$ contains exactly $n-1$ left/right edges.

###### Proof.

Observe first that for every $i\in[n-1]$, $E$ contains at least one (left or
right) edge with one endvertex on column $i$ and the other endvertex on column
$i+1$: indeed, if this were not the case for some $i\in[n-1]$, then every path
in $CG_{n}[E]$ from $p_{j_{1}}$ to $p$ would be edge-disjoint from every path
in $CG_{n}[E]$ from $q_{j_{2}}$ to $p$ and thus, $E$ would contain at least
two top sink edges, a contradiction to 5.3. Hence, for every $i\in[n-1]$, $E$
contains at least one (left or right) edge with one endvertex on column $i$
and the other endvertex on column $i+1$; in particular, $E$ contains at least
$n-1$ left/right edges. Now if $E$ contains at least $n$ left/right edges then
by Claims 5.3 and 5.4, the weight of $E$ is at least
$4N^{2}+(n-1)N+n>C_{n}^{*}$, a contradiction. ∎

Now by Claims 5.3, 5.4 and 5.5, $E$ has weight exactly $C_{n}^{*}$; we next
show that $j_{1}=j_{2}$ which would imply that $E$ represents $j_{1}$. Suppose
to the contrary that $j_{2}<j_{1}$ (the case where $j_{2}>j_{1}$ is
symmetric). By 5.4, $E$ contains exactly one edge $e$ with one endvertex on
row $j_{2}$ and one endvertex on row $j_{2}+1$; but then, either $e$ is an up
edge in which case $p_{j_{1}}$ cannot reach $q$ in $E$, or $e$ is a down edge
and $q_{j_{2}}$ cannot reach $p$ in $E$, a contradiction in both cases to the
connectedness of $E$ which concludes the proof. ∎

Down Main Gadget. Given an integer $n>0$, the down main gadget $dMG_{S}$
represents a set $S\subseteq[n]\times[n]$444Recall that, by assumption,
$1<x,y<n$ holds for every $(x,y)\in S$. and is constructed as follows. It is
an edge-weighted planar digraph consisting of a $2n\times n^{2}$ grid, where
the vertex lying at the intersection of column $i$ and row $j$ is denoted by
$x_{i,j}$, and $6n$ additional vertices
$\ell_{1},\ldots,\ell_{n},\ell^{\prime}_{1},\ldots,\ell^{\prime}_{n},r_{1},\ldots,r_{n},r^{\prime}_{1},\ldots,r^{\prime}_{n},t_{1},\ldots,t_{n}$,
$b_{1},\ldots,b_{n}$. The adjacencies and edge weights are defined as follows
(we fix $M=13n^{2}$).

  * •

_Source edges:_ for every $i\in[n]$, there is an edge $(t_{i},x_{i,n^{2}})$.
Together these edges are called source edges. The weight of each such edge is
set to $M^{5}$.

  * •

_Bottom sink edges:_ for every $i\in[n]$, there is an edge
$(x_{n+i,1},b_{i})$. Together these edges are called bottom sink edges. The
weight of each such edge is set to $M^{5}$.

  * •

_Left sink edges:_ for every $j\in[n]$, there is an edge
$(\ell^{\prime}_{j},\ell_{j})$ whose weight is set to $Mj$. Together these
edges are called left sink edges.

  * •

_Right sink edges:_ for every $j\in[n]$, there is an edge
$(r^{\prime}_{j},r_{j})$ whose weight is set to $M^{2}-Mj$. Together these
edges are called right sink edges.

  * •

_Left internal sink edges:_ for every $j\in[n]$ and every $(j-1)n+1\leq p\leq
jn$, there is an edge $(x_{1,p},\ell^{\prime}_{j})$ whose weight is set to
$p-(j-1)n$. For every fixed $j\in[n]$, these edges together are called the
$j^{th}$ left internal sink edges.

  * •

_Right internal sink edges:_ for every $j\in[n]$ and every $(j-1)n+1\leq p\leq
jn$, there is an edge $(x_{2n,p},r^{\prime}_{j})$ whose weight is set to
$n+1-(p-(j-1)n)$. For every fixed $j\in[n]$, these edges together are called
the $j^{th}$ right internal sink edges.

  * •

_Right bridge edges:_ for every $j\in[n]$ and every $(j-1)n+1\leq p\leq jn$,
there is an edge $(x_{n,p},x_{n+1,p})$. For every fixed $j\in[n]$, these edges
together are called the $j^{th}$ right bridge edges. The weight of each
$j^{th}$ right bridge edge is set to $M^{4}$.

  * •

_Downward bridge edges:_ for every $j\in\\{pn+1~{}|~{}p\in[n-1]\\}$ and every
$i\in[2n]$, there is an edge $(x_{i,j},x_{i,j-1})$. For every fixed
$j\in\\{pn+1~{}|~{}p\in[n-1]\\}$, these edges together are called the $j^{th}$
downward bridge edges. The weight of each $j^{th}$ downward bridge edge is set
to $M^{3}$.

  * •

_Down edges:_ for every $i\in[2n]$, every $j\in[n]$ and every $(j-1)n+2\leq
p\leq jn$, there is an edge $(x_{i,p},x_{i,p-1})$. Together these edges are
called down edges. The weight of each such edge is set to $4$.

  * •

_Right edges:_ for every $j\in[n]$, every $(j-1)n+1\leq p\leq jn$ and every
$jn+1-p\leq q\leq 2n-1$ such that $q\neq n$, there is an edge
$(x_{q,p},x_{q+1,p})$. Together these edges are called right edges. The weight
of each such edge is set to $4$.

  * •

_Left edges:_ for every $j\in[n]$, every $(j-1)n+1\leq p\leq jn-1$ and every
$2\leq q\leq jn+1-p$, there is an edge $(x_{q,p},x_{q-1,p})$. Together these
edges are called left edges. The weight of each such edge is set to $4$.

  * •

_Shortcut edges:_ for every $s=(i,j)\in S$, we introduce two shortcut edges
$e^{\ell}_{s},e^{r}_{s}$ as follows. Set $p=jn+1$, then

    * –

subdivide the edge $(x_{i,p+1-i},x_{i,p-i})$ by adding a vertex $y_{i,j}$ and
the edge $(x_{i,p+1-i},y_{i,j})$ (of weight $3$) with the edge
$(y_{i,j},x_{i,p-i})$ (of weight $1$);

    * –

subdivide the edge $(x_{n+i,p-i},x_{n+i,p-1-i})$ by adding a vertex $z_{i,j}$
and the edge $(x_{n+i,p-i},\allowbreak z_{i,j})$ (of weight $3$) with the edge
$(z_{i,j},x_{n+i,p-1-i})$ (of weight $1$).

The introduced edges are called _down subdivided edges_. Then

    * –

$e^{\ell}_{s}=(y_{i,j},x_{i-1,p-i})$ and its weight is set to $2$;

    * –

$e^{r}_{s}=(z_{i,j},x_{n+i+1,p-i})$ and its weight is set to $2$.

The edges $e^{\ell}_{s}$ are called _left_ shortcut edges and the edges
$e^{r}_{s}$ are called _right_ shortcut edges.

This concludes the construction of the down main gadget $dMG_{S}$ (see Figure
14 for an illustration of the down main gadget with $n=4$ representing
$S=\\{(2,2),(2,3),(3,2)\\}$). In the following, we call the vertices
$\ell_{1},\ldots,\ell_{n}$ the _left vertices_ , the vertices
$r_{1},\ldots,r_{n}$ the _right vertices_ , the vertices $t_{1},\ldots,t_{n}$
the _top vertices_ and the vertices $b_{1},\ldots,b_{n}$ the _bottom
vertices_. Furthermore, we set

$M_{n}^{*}=2M^{5}+M^{4}+(n-1)M^{3}+M^{2}+(4n+1)(n+1)-12.$

We further let $V_{\ell}=\\{x_{i,j}~{}|~{}1\leq i\leq n\text{ and }1\leq j\leq
n^{2}\\}\cup\\{y_{i,j}~{}|~{}(i,j)\in S\\}$, $V_{r}=\\{x_{i,j}~{}|~{}n+1\leq
i\leq 2n\text{ and }1\leq j\leq n^{2}\\}\cup\\{z_{i,j}~{}|~{}(i,j)\in S\\}$
and for every $j\in[n]$, $V_{j}=\\{x_{i,p}~{}|~{}1\leq i\leq 2n\text{ and
}(j-1)n+1\leq p\leq jn\\}$. Note that, by construction, the following holds.

######  Observation 5.6.

For every $j\in[n]$ and every $x_{i,p}\in V_{j}\cap V_{\ell}$, the following
holds.

  * •

If $n+1-i>p-(j-1)n$ then $x_{i,p}$ cannot reach a vertex
$x_{i^{\prime},p^{\prime}}\in V_{j}$ such that $n+1-i^{\prime}\leq
p^{\prime}-(j-1)n$.

  * •

If $n+1-i<p-(j-1)n$ then $x_{i,p}$ cannot reach a vertex
$x_{i^{\prime},p^{\prime}}\in V_{j}$ such that $i^{\prime}<i$ and
$p^{\prime}-(j-1)n>n+1-i$.

$b_{1}$$b_{2}$$b_{3}$$b_{4}$$t_{1}$$t_{2}$$t_{3}$$t_{4}$$\ell^{\prime}_{1}$$\ell_{1}$$\ell^{\prime}_{2}$$\ell_{2}$$\ell^{\prime}_{3}$$\ell_{3}$$\ell^{\prime}_{4}$$\ell_{4}$$r^{\prime}_{1}$$r_{1}$$r^{\prime}_{2}$$r_{2}$$r^{\prime}_{3}$$r_{3}$$r^{\prime}_{4}$$r_{4}$
Figure 14: The down main gadget $dMG_{S}$ with $n=4$ representing
$S=\\{(2,2),(2,3),(3,2)\\}$ (the red edges are the shortcut edges). A set of
edges representing $(2,2)$ is highlighted.

A set $E\subseteq E(dMG_{S})$ satisfies the _connectedness_ property if the
following hold in $E$:

  * •

a top vertex can reach a bottom vertex;

  * •

a top vertex can reach a right vertex;

  * •

a top vertex can reach a left vertex.

A set $E\subseteq E(dMG_{S})$ satisfying the connectedness property
_represents_ a pair $(i,j)\in[n]\times[n]$ if the only source edge in $E$ is
the one incident to $t_{i}$, the only bottom sink edge in $E$ is the one
incident to $b_{i}$, the only left sink edge in $E$ is the one incident to
$\ell_{j}$ and the only right sink edge in $E$ is the one incident to $r_{j}$
(see Figure 14 for a set of edges representing $(2,2)$).

######  Lemma 5.7.

For any $n>0$ and any $S\subseteq[n]\times[n]$, the down main gadget $dMG_{S}$
satisfies the following properties.

  * (1)

For every $(i,j)\in S$, there exists a set $E_{i,j}\subseteq E(dMG_{S})$ of
weight $M_{n}^{*}$ representing $(i,j)$.

  * (2)

If there exists a set $E\subseteq E(dMG_{S})$ of weight at most $M_{n}^{*}$
satisfying the connectedness property, then $E$ has weight exactly $M_{n}^{*}$
and represents a pair $(i,j)\in S$.

###### Proof.

To prove (1), it suffices to take $E_{i,j}$ to be the union of the following
set of edges:

  * •

$\\{(t_{i},x_{i,n^{2}}),(x_{n+i,1},b_{i}),(x_{0,jn+1-i},\ell^{\prime}_{j}),(\ell^{\prime}_{j},\ell_{j}),(x_{2n+1,jn+1-i},r^{\prime}_{j}),(r^{\prime}_{j},r_{j})\\}$;

  * •

$\\{(x_{i,p},x_{i,p-1})~{}|~{}jn+2-i\leq p\leq
n^{2}\\}\cup\\{(x_{n+i,p},x_{n+i,p-1})~{}|~{}2\leq p\leq jn+1-i\\}$;

  * •

$\\{(x_{p,jn+1-i},x_{p-1,jn+1-i})~{}|~{}1\leq p\leq
i-1\\}\cup\\{e^{\ell}_{(i,j)}\\}$;

  * •

$\\{(x_{p,jn+1-i},x_{p+1,jn+1-i})~{}|~{}i\leq p\leq 2n\text{ and }p\neq
n+i\\}\cup\\{e^{r}_{(i,j)}\\}$.

It is not difficult to see that $E_{i,j}$ represents $(i,j)$ and has weight
$M_{n}^{*}$.

Next, suppose that $E\subseteq E(dMG_{S})$ is a set of weight at most
$M_{n}^{*}$ satisfying the connectedness property. Let us show that $E$ has
weight exactly $M_{n}^{*}$ and represents some $(i,j)\in S$. To this end, we
first prove the following claims.

######  Claim 5.8.

$E$ contains exactly one source edge and one bottom sink edge.

###### Proof.

Since $E$ satisfies the connectedness property, it contains at least one
source edge and one bottom sink edge. Now if $E$ contains at least two source
edges, then the weight of $E$ is at least $3M^{5}$; however, by definition,

$\begin{split}M_{n}^{*}&=2M^{5}+M^{4}+(n-1)M^{3}+M^{2}+(4n+1)(n+1)-12\\\
&<2M^{5}+n^{2}M^{4}+n^{2}M^{4}+n^{2}M^{4}+9n^{2}M^{4}<3M^{5}\end{split}$

as $M=13n^{2}>12n^{2}$, a contradiction. We conclude similarly if $E$ contains
at least two bottom sink edges. ∎

In the following, we let $t_{i_{1}}$ be the top vertex incident to the source
edge in $E$ and $b_{i_{2}}$ be the bottom vertex incident to the bottom sink
edge in $E$.

######  Claim 5.9.

$E$ contains exactly one right bridge edge.

###### Proof.

Since $t_{i_{1}}$ can reach $b_{i_{2}}$ in $E$, $E$ contains at least one
right bridge edge. Now if $E$ contains at least two right bridge edges then by
5.8, the weight of $E$ is at least $2M^{5}+2M^{4}$; however, by definition,

$\begin{split}M_{n}^{*}&=2M^{5}+M^{4}+(n-1)M^{3}+M^{2}+(4n+1)(n+1)-12\\\
&<2M^{5}+M^{4}+n^{2}M^{4}+n^{2}M^{4}+9n^{2}M^{4}\\\
&<2M^{5}+2M^{4}\end{split}$

as $M=13n^{2}>11n^{2}$, a contradiction. ∎

######  Claim 5.10.

For every $j\in[n-1]$, $E$ contains exactly one $j^{th}$ downward bridge edge.
In particular, $E$ contains exactly $n-1$ downward bridge edges.

###### Proof.

Since $t_{i_{1}}$ can reach $b_{i_{2}}$ in $E$, $E$ contains at least one
$j^{th}$ downward bridge edge for every $j\in[n-1]$. Now if $E$ contains at
least $n$ downward bridge edges then by Claims 5.8 and 5.9, the weight of $E$
is at least $2M^{5}+M^{4}+nM^{3}$; however, by definition,

$\begin{split}M_{n}^{*}&=2M^{5}+M^{4}+(n-1)M^{3}+M^{2}+(4n+1)(n+1)-12\\\
&<2M^{5}+M^{4}+(n-1)M^{3}+n^{2}M^{2}+9n^{2}M^{2}\\\
&<2M^{5}+M^{4}+nM^{3}\end{split}$

as $M=13n^{2}>10n^{2}$, a contradiction. ∎

Since $E$ satisfies the connectedness property, it contains at least one left
sink edge $(\ell^{\prime}_{j_{1}},\ell_{j_{1}})$ and at least one right sink
edge $(r^{\prime}_{j_{2}},r_{j_{2}})$; we next show that $E$ contains in fact
no other left or right sink edge.

######  Claim 5.11.

It holds that $j_{1}=j_{2}$. Furthermore, $E$ contains a $j_{1}^{th}$ right
bridge edge.

###### Proof.

Towards a contradiction, suppose that $j_{1}\neq j_{2}$. Assume first that
$j_{1}<j_{2}$ and let $P$ be a path from $t_{i_{1}}$ to $r_{j_{2}}$ in
$dMG_{S}[E]$. Then $P$ must contain a $j^{th}$ right bridge edge $e$ for some
$j\geq j_{2}$, and since $E$ contains exactly one right bridge edge by 5.9, it
follows that every path in $dMG_{S}[E]$ from $t_{i_{1}}$ to $b_{i_{2}}$
contains $e$. But $t_{i_{1}}$ can reach $\ell_{j_{1}}$ in $E$ as well and so,
$E$ must contain at least $n-j$ downward bridge edges for $t_{i_{1}}$ to reach
the tail of $e$, plus $j-1$ downward bridge edges for the head of $e$ to then
reach $b_{i_{2}}$, plus $j-j_{1}$ downward bridge edges for $t_{i_{1}}$ to
also reach $\ell_{j_{1}}$, a contradiction to 5.10. Suppose next that
$j_{2}<j_{1}$. Then since $E$ contains the edge
$(\ell^{\prime}_{j_{1}},\ell_{j_{1}})$ and the edge
$(r^{\prime}_{j_{2}},r_{j_{2}})$, it follows from Claims 5.8, 5.9 and 5.10
that the weight of $E$ is at least
$2M^{5}+M^{4}+(n-1)M^{3}+Mj_{1}+M^{2}-Mj_{2}\geq
2M^{5}+M^{4}+(n-1)M^{3}+M^{2}+M$. However, by definition,

$\begin{split}M_{n}^{*}&=2M^{5}+M^{4}+(n-1)M^{3}+M^{2}+(4n+1)(n+1)-12\\\
&<2M^{5}+M^{4}+(n-1)M^{3}+M^{2}+9n^{2}\\\
&<2M^{5}+M^{4}+(n-1)M^{3}+M^{2}+M\end{split}$

as $M=13n^{2}>9n^{2}$, a contradiction. Thus, $j_{1}=j_{2}$ and by arguing as
above, we can show that $E$ must then contain a $j_{1}^{th}$ right bridge
edge. ∎

In the following, we say that a path $P$ in $dMG_{S}$ _crosses a row_ $j$ if
$V(P)\cap\\{x_{i,j}~{}|~{}i\in[2n]\\}\neq\emptyset$ and that $P$ _crosses a
column_ $i$ if $V(P)\cap\\{x_{i,j}~{}|~{}j\in[n^{2}]\\}\neq\emptyset$.
Furthermore, we define

  * •

a _$2d$ -move_ to be the union of two down subdivided edges $e,e^{\prime}$
such that the head of $e$ coincides with the tail of $e^{\prime}$;

  * •

a _$d\ell$ -move_ to be the union of a down subdivided edge $e$ and a left
shortcut edge $e^{\prime}$ such that the head of $e$ coincides with the tail
of $e^{\prime}$;

  * •

a _$dr$ -move_ to be the union of a down subdivided edge $e$ and a right
shortcut edge $e^{\prime}$ such that the head of $e$ coincides with the tail
of $e^{\prime}$.

For convenience, we also call

  * •

a right edge an _$r$ -move_,

  * •

a left edge an _$\ell$ -move_,

  * •

a down edge a _$d$ -move_ and

  * •

a downward bridge edge a _$Db$ -move_.

Note that no $dr$-move is possible in $dMG_{S}[V_{\ell}]$ and that no $x$-move
with $x\in\\{d\ell,\ell\\}$ is possible in $dMG_{S}[V_{r}]$. Furthermore, for
any $x\in\\{2d,r,\ell,d\\}$, the weight of an $x$-move is 4 and for any
$x\in\\{dr,d\ell\\}$, the weight of an $x$-move is 5. Given a path $P$ of
$dMG_{S}$ and $x\in\\{2d,d\ell,dr,r,\ell,d,Db\\}$, we let $m(P,x)$ be the
number of $x$-moves in $P$.

Let $(x_{1,j_{0}},\ell^{\prime}_{j_{1}})$ be a $j_{1}^{th}$ left internal sink
edge contained in $E$ (recall that $\ell_{j_{1}}\in V(E)$). Further let
$x_{i_{0},j_{1}n}$ be the head of the $j_{1}^{th}$ downward bridge in $E$ if
$j_{1}\leq n-1$ (recall that by 5.10, $E$ contains exactly one such edge) and
the head of the source edge in $E$ otherwise (note that in this case
$i_{0}=i_{1}$). Since $x_{i_{0},j_{1}n}$ can reach $x_{1,j_{0}}$, the
following holds.

######  Observation 5.12.

$j_{0}-(j_{1}-1)n\leq n+1-i_{0}$.

Now by connectedness of $E$, there exists a path $P^{t}$ in $dMG_{S}[E]$ from
the head of the source edge in $E$ to $x_{i_{0},j_{1}n}$; we next lower bound
the weight of $P^{t}$.

######  Claim 5.13.

The weight of $P^{t}$ is at least
$(n-j_{1})M^{3}+4(n-1)(n-j_{1})+|i_{1}-i_{0}|$.

###### Proof.

Observe first that since by Claims 5.9 and 5.11, $E$ contains one $j_{1}^{th}$
right bridge edge and no other right bridge edge, necessarily $i_{0}\leq n$.
Now $P^{t}$ must cross every row $j_{1}n\leq j\leq n^{2}$ and thus,

$m(P^{t},Db)+m(P^{t},d)+m(P^{t},2d)+m(P^{t},d\ell)=n^{2}-j_{1}n.$

By 5.10, $P^{t}$ contains exactly $n-j_{1}$ downward bridge edges, that is,
$m(P^{t},Db)=n-j_{1}$. We next distinguish cases depending on whether
$i_{1}\leq i_{0}$ or $i_{1}>i_{0}$. Suppose first that $i_{1}\leq i_{0}$. Then
since $P^{t}$ must cross every column $i_{1}\leq i\leq i_{0}$, $m(P^{t},r)\geq
i_{0}-i_{1}$. It follows that the weight of $P^{t}$ is at least

$\begin{split}&~{}M^{3}m(P^{t},Db)+4m(P^{t},d)+4m(P^{t},2d)+5m(P^{t},d\ell)+4m(P^{t},r)\\\
&=(n-j_{1})M^{3}+4m(P^{t},d)+4m(P^{t},2d)+5m(P^{t},d\ell)+4m(P^{t},r)\\\
&\geq(n-j_{1})M^{3}+4(m(P^{t},d)+m(P^{t},2d)+m(P^{t},d\ell))+4(i_{0}-i_{1})\\\
&\geq(n-j_{1})M^{3}+4(n^{2}-j_{1}n-(n-j_{1}))+4(i_{0}-i_{1})\\\
&\geq(n-j_{1})M^{3}+4(n-1)(n-j_{1})+(i_{0}-i_{1})\end{split}$

Second, suppose that $i_{1}>i_{0}$. Then since $P^{t}$ must cross every column
$i_{0}\leq i\leq i_{1}$,

$m(P^{t},\ell)+m(P^{t},d\ell)=m(P^{t},r)+i_{1}-i_{0}$

and so, the weight of $P^{t}$ is at least

$\begin{split}&~{}M^{3}m(P^{t},Db)+4m(P^{t},d)+4m(P^{t},2d)+5m(P^{t},d\ell)+4m(P^{t},\ell)+4m(P^{t},r)\\\
&=(n-j_{1})M^{3}+4m(P^{t},d)+4m(P^{t},2d)+5m(P^{t},d\ell)+4m(P^{t},\ell)+4m(P^{t},r)\\\
&\geq(n-j_{1})M^{3}+4(n^{2}-j_{1}n-(n-j_{1}))+m(P^{t},d\ell)+4m(P^{t},\ell)+4(m(P^{t},\ell)\\\
&+m(P^{t},d\ell)-(i_{1}-i_{0}))\\\
&\geq(n-j_{1})M^{3}+4(n-1)(n-j_{1})+5m(P^{t},d\ell)+8m(P^{t},\ell)-4(i_{1}-i_{0})\\\
&\geq(n-j_{1})M^{3}+4(n-1)(n-j_{1})+5(m(P^{t},d\ell)+m(P^{t},\ell))-4(i_{1}-i_{0})\\\
&\geq(n-j_{1})M^{3}+4(n-1)(n-j_{1})+(i_{1}-i_{0})\\\ \end{split}$

as $m(P^{t},d\ell)+m(P^{t},\ell)\geq i_{1}-i_{0}$ which proves our claim. ∎

Let $(x_{2n,j^{\prime}_{0}},r^{\prime}_{j_{1}})$ be a $j_{1}^{th}$ right
internal sink edge contained in $E$ (recall that $r_{j_{2}}\in V(E)$ and
$j_{2}=j_{1}$ by 5.11). Further let $x_{i^{\prime}_{0},(j_{1}-1)n+1}$ be the
tail of the $(j_{1}-1)^{th}$ downward bridge in $E$ if $j_{1}>1$ (recall that
by 5.10, $E$ contains exactly one such edge) and the tail of the bottom sink
edge contained in $E$ otherwise (note that in this case
$i^{\prime}_{0}=n+i_{2}$). Then by connectedness of $E$, there exists a path
$P^{b}$ in $dMG_{S}[E]$ from $x_{i^{\prime}_{0},(j_{1}-1)n+1}$ to the tail of
the bottom sink edge in $E$; we next lower bound the weight of $P^{b}$.

######  Claim 5.14.

The weight of $P^{b}$ is at least
$(j_{1}-1)M^{3}+4(n-1)(j_{1}-1)+4(n+i_{2}-i^{\prime}_{0})$.

###### Proof.

Observe first that since by Claims 5.9 and 5.11, $E$ contains a $j_{1}^{th}$
right bridge edge and no other right bridge edge, necessarily
$i^{\prime}_{0}\geq n+1$. Furthermore, since $dMG_{S}[V_{r}]$ contains no edge
$r$-move, the following holds.

######  Observation 5.15.

$i^{\prime}_{0}\leq n+i_{2}$.

Now $P^{b}$ must cross every column $i^{\prime}_{0}\leq i\leq n+i_{2}$ and
every row $1\leq j\leq(j_{1}-1)n+1$; thus

$m(P^{b},Db)+m(P^{b},d)+m(P^{b},2d)=(j_{1}-1)n\text{ and
}m(P^{b},r)+m(P^{b},dr)=n+i_{2}-i^{\prime}_{0}.$

Since by 5.10, $P^{b}$ contains exactly $j_{1}-1$ downward bridge edges, it
follows that the weight of $P^{b}$ is at least

$\begin{split}&~{}M^{3}m(P^{b},Db)+4m(P^{b},d)+4m(P^{b},2d)+4m(P^{b},r)+5m(P^{b},dr)\\\
&=(j_{1}-1)M^{3}+4(m(P^{b},d)+m(P^{b},2d))+4m(P^{b},r)+5m(P^{b},dr)\\\
&\geq(j_{1}-1)M^{3}+4((j_{1}-1)n-(j_{1}-1))+4(m(P^{b},r)+m(P^{b},dr))\\\
&\geq(j_{1}-1)M^{3}+4(j_{1}-1)(n-1)+4(n+i_{2}-i^{\prime}_{0})\end{split}$

which proves our claim. ∎

Let $x_{n+1,t}$ be the head of the $j_{1}^{th}$ right bridge edge in $E$
(recall that by Claims 5.9 and 5.11, $E$ contains exactly one $j_{1}^{th}$
right bridge edge and no other right bridge edge). Then by connectedness of
$E$, there exist in $dMG_{S}[E]$ a path $P$ and a path $P^{\prime}$ from
$x_{i_{0},j_{1}n}$ to $x_{1,j_{0}}$ and from $x_{i_{0},j_{1}n}$ to $x_{n,t}$
respectively; we next lower bound the weight of $P\cup P^{\prime}$. To this
end, denote by $x_{i^{\prime},t^{\prime}}$ the last vertex in $V(P)$ belonging
to $V(P^{\prime})\cap V_{j_{1}}$.

######  Observation 5.16.

$\max\\{t,j_{0}\\}\leq t^{\prime}$ and $n+1-i^{\prime}\leq
t^{\prime}-(j_{1}-1)n$.

Indeed, since $x_{i^{\prime},t^{\prime}}$ can reach both $x_{1,j_{0}}$ and
$x_{n,t}$, $t^{\prime}\geq j_{0}$ and $t^{\prime}\geq t$. Now if
$n+1-i^{\prime}>t^{\prime}-(j_{1}-1)n$ then by 5.6,
$x_{i^{\prime},t^{\prime}}$ cannot reach $x_{n,t}$ as $t-(j_{1}-1)n\geq
1=n+1-n$, a contradiction.

######  Observation 5.17.

$i_{0}\leq i^{\prime}$.

Indeed, if $i_{0}>i^{\prime}$ then, in particular, $i_{0}>1$ and so,
$n+1-i_{0}<n=j_{1}n-(j_{1}-1)n$; but then, by 5.6, $x_{i_{0},j_{1}n}$ cannot
reach $x_{i^{\prime},t^{\prime}}$ as $n+1-i_{0}<n+1-i^{\prime}\leq
t^{\prime}-(j_{1}-1)n$ by 5.16, a contradiction.

######  Claim 5.18.

The weight of $P\cup P^{\prime}$ is at least

$4(n-1)+4(t^{\prime}-t)+4(j_{1}n-j_{0})+4(i^{\prime}-i_{0})-3(p_{1}+m(P,d\ell))$

where

$p_{1}=\left\\{\begin{array}[]{ll}1&\mbox{if }(i^{\prime},j_{1})\in
S,~{}e^{\ell}_{i^{\prime},j_{1}}\in E(P)\mbox{ and
}x_{i^{\prime},t^{\prime}-1}\in V(P^{\prime})\\\
0&\mbox{otherwise.}\end{array}\right.$

###### Proof.

Denote by $e$ the down or down subdivided edge with tail
$x_{i^{\prime},t^{\prime}}$ (note that $e$ is a down subdivided edge if and
only if $(i^{\prime},j_{1})\in S$). Then by definition of
$x_{i^{\prime},t^{\prime}}$, the weight of $P\cup P^{\prime}$ is at least the
sum of the weights of $P^{\prime}$ and
$P[x_{i^{\prime},t^{\prime}},x_{1,j_{0}}]$ minus the weight of $e$ whenever
$(i^{\prime},j_{1})\in S$ and $e\in E(P^{\prime})\cap
E(P[x_{i^{\prime},t^{\prime}},x_{1,j_{0}}])$. Let us therefore lower bound the
weights of $P^{\prime}$ and $P[x_{i^{\prime},t^{\prime}},x_{1,j_{0}}]$.

First note that since for any left shortcut edge $f$ with head $x_{p,q}\in
V_{j}$, it holds that $n+1-p>q-(j-1)n$, $x_{p,q}$ cannot reach any vertex
$x_{p^{\prime},q^{\prime}}\in V_{j}$ such that $n+1-p^{\prime}\leq
q^{\prime}-(j-1)n$ by 5.6. Further note that since the tail of $f$ can only be
reached through $x_{p-1,q-1}$ where $n+1-(p-1)<(q-1)-(j-1)n$, no vertex
$x_{p^{\prime},q^{\prime}}\in V_{j}$ such that
$n+1-p^{\prime}>q^{\prime}-(j-1)n$ can reach the tail of $f$ by 5.6. It
follows that $P^{\prime}$ and $P[x_{i_{0},j_{1}n},x_{i^{\prime},t^{\prime}}]$
contain no left shortcut edge (recall that $n+1-i^{\prime}\leq
t^{\prime}-(j_{1}-1)n$ by 5.16) and that
$P[x_{i^{\prime},t^{\prime}},x_{1,j_{0}}]$ contains at most one left shortcut
edge, that is, the following holds.

######  Observation 5.19.

$m(P^{\prime},d\ell)=m(P[x_{i_{0},j_{1}n},x_{i^{\prime},t^{\prime}}],d\ell)=0$
and $m(P,d\ell)\in\\{0,1\\}$.

Now $P^{\prime}$ must cross every row $t\leq j\leq j_{1}n$ and
$P[x_{i^{\prime},t^{\prime}},x_{1,j_{0}}]$ must cross every row $j_{0}\leq
j\leq t^{\prime}$ (recall that $\max\\{t,j_{0}\\}\leq t^{\prime}$ by 5.16);
thus

$\begin{split}&m(P^{\prime},d)+m(P^{\prime},2d)=j_{1}n-t\text{ and }\\\
&m(P[x_{i^{\prime},t^{\prime}}.x_{1,j_{0}}],d)+m(P[x_{i^{\prime},t^{\prime}}.x_{1,j_{0}}],2d)+m(P[x_{i^{\prime},t^{\prime}}.x_{1,j_{0}}],d\ell)=t^{\prime}-j_{0}.\end{split}$

Similarly, $P^{\prime}$ must cross every column $i_{0}\leq i\leq n$ and
$P[x_{i^{\prime},t^{\prime}},x_{1,j_{0}}]$ must cross every column $1\leq
i\leq i^{\prime}$ (recall that $i_{0}\leq i^{\prime}$ by 5.17); thus

$\begin{split}&m(P^{\prime},\ell)+m(P^{\prime},r)\geq n-i_{0}\text{ and }\\\
&m(P[x_{i^{\prime},t^{\prime}}.x_{1,j_{0}}],\ell)+m(P[x_{i^{\prime},t^{\prime}}.x_{1,j_{0}}],d\ell)\geq
i^{\prime}-1.\end{split}$

Now note that $p_{1}=1$ if and only if $(i^{\prime},j_{1})\in S$ and $e$
belongs to both $P$ and $P[x_{i^{\prime},t^{\prime}},x_{1,j_{0}}]$: indeed, if
$p_{1}=1$ then clearly $(i^{\prime},j_{1})\in S$ and $e\in E(P)\cap
E(P[x_{i^{\prime},t^{\prime}},x_{1,j_{0}}])$. Conversely, if
$(i^{\prime},j_{1})\in S$ and $e$ belongs to both $P$ and
$P[x_{i^{\prime},t^{\prime}},x_{1,j_{0}}]$ then since by definition of
$x_{i^{\prime},t^{\prime}}$, $x_{i^{\prime},t^{\prime}-1}$ cannot belong to
both $P^{\prime}$ and $P[x_{i^{\prime},t^{\prime}},x_{1,j_{0}}]$, and
$P^{\prime}$ contains no left shortcut edge by 5.19, it must be that
$P^{\prime}$ contains $x_{i^{\prime},t^{\prime}-1}$ while
$P[x_{i^{\prime},t^{\prime}},x_{1,j_{0}}]$ contains the left shortcut edge
$e^{\ell}_{(i^{\prime},j_{1})}$, that is, $p_{1}=1$. It follows that the
weight of $P\cup P^{\prime}$ is at least

$\begin{split}&4(m(P^{\prime},d)+m(P^{\prime},2d))+4(m(P^{\prime},\ell)+m(P^{\prime},r))+4(m(P[x_{i^{\prime},t^{\prime}}.x_{1,j_{0}}],d)+m(P[x_{i^{\prime},t^{\prime}}.x_{1,j_{0}}],2d))\\\
+&~{}5(m(P[x_{i^{\prime},t^{\prime}}.x_{1,j_{0}}],d\ell)-p_{1})+2p_{1}+4m(P[x_{i^{\prime},t^{\prime}}.x_{1,j_{0}}],\ell)\\\
\geq&~{}4(j_{1}n-t)+4(n-i_{0})+4(t^{\prime}-j_{0})+m(P[x_{i^{\prime},t^{\prime}}.x_{1,j_{0}}],d\ell)-3p_{1}\\\
+&~{}4(i^{\prime}-1-m(P[x_{i^{\prime},t^{\prime}}.x_{1,j_{0}}],d\ell))\\\
\geq&~{}4(n-1)+4(t^{\prime}-t)+4(j_{1}n-j_{0})+4(i^{\prime}-i_{0})-3(p_{1}+m(P[x_{i^{\prime},t^{\prime}}.x_{1,j_{0}}],d\ell))\end{split}$

which proves our claim as
$m(P[x_{i^{\prime},t^{\prime}}.x_{1,j_{0}}],d\ell)=m(P,d\ell)$ by 5.19. ∎

Note that if $p_{1}=1$ then, since $x_{i^{\prime}-1,t^{\prime}-1}\in V(P)$ can
reach $x_{1,j_{0}}$ and $x_{i^{\prime},t^{\prime}-1}\in V(P^{\prime})$ can
reach $x_{n,t}$, the following holds.

######  Observation 5.20.

If $p_{1}=1$ then $j_{0}\leq t^{\prime}-1$ and $t\leq t^{\prime}-1$.

Now by connectedness of $E$, there exist in $dMG_{S}[E]$ a path $Q$ and a path
$Q^{\prime}$ from $x_{n+1,t}$ to $x_{i^{\prime}_{0},(j_{1}-1)n+1}$ and from
$x_{n+1,t}$ to $x_{2n,j^{\prime}_{0}}$, respectively; we next lower bound the
weight of $Q\cup Q^{\prime}$. To this end, denote by
$x_{i^{\prime\prime},t^{\prime\prime}}$ the last vertex in $V(Q^{\prime})$
belonging to $V(Q)\cap V_{j_{1}}$.

######  Claim 5.21.

The weight of $Q\cup Q^{\prime}$ is at least

$4(n-2)+4(i^{\prime}_{0}-i^{\prime\prime})+4(t^{\prime\prime}-j^{\prime}_{0})+4(t-(j_{1}-1)n)-2p_{2}$

where

$p_{2}=\left\\{\begin{array}[]{ll}1&\mbox{if }(i^{\prime\prime}-n,j_{1})\in
S\mbox{ and }e^{r}_{i^{\prime\prime}-n,j_{1}}\in E(Q^{\prime}),\\\
0&\mbox{otherwise.}\end{array}\right.$

###### Proof.

First note that since $x_{n+1,t}$ can reach
$x_{i^{\prime\prime},t^{\prime\prime}}$, and
$x_{i^{\prime\prime},t^{\prime\prime}}$ can reach both $x_{2n,j^{\prime}_{0}}$
and $x_{i^{\prime}_{0},(j_{1}-1)n+1}$, the following holds.

######  Observation 5.22.

$j^{\prime}_{0}\leq t^{\prime\prime}\leq t$ and $i^{\prime\prime}\leq
i^{\prime}_{0}$.

Now denote by $e$ the down or down subdivided edge with tail
$x_{i^{\prime\prime},t^{\prime\prime}}$ (note that $e$ is a down subdivided
edge if and only if $(i^{\prime\prime}-n,j_{1})\in S$). Then by definition of
$x_{i^{\prime\prime},t^{\prime\prime}}$, the weight of $Q\cup Q^{\prime}$ is
at least the sum of the weights of $Q$ and
$Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}]$
minus the weight of $e$ whenever $(i^{\prime\prime}-n,j_{1})\in S$ and $e\in
E(Q)\cap
E(Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}])$.
Let us therefore lower bound the weights of $Q$ and
$Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}]$.

Since $Q$ must cross every row $(j_{1}-1)n+1\leq j\leq t$ and
$Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}]$ must
cross every row $j^{\prime}_{0}\leq j\leq t^{\prime\prime}$ (recall that
$j^{\prime}_{0}\leq t^{\prime\prime}\leq t$ by 5.22), it follows that

$\begin{split}&m(Q,d)+m(Q,2d)=t-((j_{1}-1)n+1)\text{ and}\\\
&m(Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}],d)+m(Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}],2d)=t^{\prime\prime}-j^{\prime}_{0}.\end{split}$

Similarly, $Q$ must cross every column $n+1\leq i\leq i^{\prime}_{0}$ and
$Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}]$ must
cross every column $i^{\prime\prime}\leq i\leq 2n$ (recall that
$i^{\prime\prime}\leq i^{\prime}_{0}$ by 5.22); thus

$\begin{split}&m(Q,r)+m(Q,dr)=i^{\prime}_{0}-(n+1)\text{ and}\\\
&m(Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}],r)+m(Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}],dr)=2n-i^{\prime\prime}.\end{split}$

Now note that $p_{2}=1$ if and only if $(i^{\prime\prime}-n,j_{1})\in S$ and
$e$ belongs to both $Q$ and $Q^{\prime}$: indeed, if $p_{2}=1$ then by
definition $(i^{\prime\prime}-n,j_{1})\in S$, $e\in E(Q^{\prime})$ and
$x_{i^{\prime\prime}+1,t^{\prime\prime}}\in V(Q^{\prime})$ which implies, by
definition of $x_{i^{\prime\prime},t^{\prime\prime}}$, that
$x_{i^{\prime\prime}+1,t^{\prime\prime}}\notin V(Q)$ and so, $e\in E(Q)$.
Conversely, if $(i^{\prime\prime}-n,j_{1})\in S$ and $e$ belongs to both $Q$
and $Q^{\prime}$ then, by definition of
$x_{i^{\prime\prime},t^{\prime\prime}}$, it must be that
$x_{i^{\prime\prime},t^{\prime\prime}-1}$ belongs to one of $Q$ and
$Q^{\prime}$ while $x_{i^{\prime\prime}+1,t^{\prime\prime}}$ belongs to the
other. However, if $x_{i^{\prime\prime}+1,t^{\prime\prime}}$ belongs to $Q$
(and so, $x_{i^{\prime\prime},t^{\prime\prime}-1}\in V(Q^{\prime})$) then,
since $Q$ crosses row $(j_{1}-1)n+1$ and $Q^{\prime}$ crosses column $2n$,
necessarily
$Q[x_{i^{\prime\prime}+1,t^{\prime\prime}},x_{i^{\prime}_{0},(j_{1}-1)n+1}]\cap
Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}-1},x_{2n,j^{\prime}_{0}}]\cap
V_{j_{1}}\neq\emptyset$, a contradiction to the definition of
$x_{i^{\prime\prime},t^{\prime\prime}}$. Thus,
$x_{i^{\prime\prime}+1,t^{\prime\prime}}\in V(Q^{\prime})$ and so,
$e^{r}_{(i^{\prime\prime}-n,t^{\prime\prime})}\in E(Q^{\prime})$, that is,
$p_{2}=1$. It follows that the weight of $Q\cup Q^{\prime}$ is at least

$\begin{split}&4(m(Q,d)+m(Q,2d))+4m(Q,r)+5m(Q,dr)+4(m(Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}],d)\\\
+&~{}m(Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}],2d))+4m(Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}],r)+5(m(Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}],dr)-p_{2})+2p_{2}\\\
\geq&~{}4(t-((j_{1}-1)n+1))+4(m(Q,r)+m(Q,dr))+4(t^{\prime\prime}-j^{\prime}_{0})+4(2n-i^{\prime\prime})\\\
+&~{}m(Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}],dr)-3p_{2}\\\
\geq&~{}4(t-((j_{1}-1)n+1))+4(i^{\prime}_{0}-(n+1))+4(t^{\prime\prime}-j^{\prime}_{0})+4(2n-i^{\prime\prime})\\\
+&~{}m(Q^{\prime}[x_{i^{\prime\prime},t^{\prime\prime}},x_{2n,j^{\prime}_{0}}],dr)-3p_{2}\\\
\geq&~{}4(n-2)+4(i^{\prime}_{0}-i^{\prime\prime})+4(t^{\prime\prime}-j^{\prime}_{0})+4(t-(j_{1}-1)n)-2p_{2}\end{split}$

which proves our claim. ∎

In the following, we write $j_{0}=(j_{1}-1)n+p_{0}$ and
$j^{\prime}_{0}=(j_{1}-1)n+p^{\prime}_{0}$ and further let

$W=|i_{1}-i_{0}|+4(n+i_{2}-i^{\prime\prime})+4(i^{\prime}-i_{0})+4(t^{\prime}-j_{0})+4(t^{\prime\prime}-j^{\prime}_{0})-(8+3(p_{1}+m(P,d\ell))+2p_{2}).$

Observe that by Claims 5.13, 5.14, 5.18 and 5.21, the weight of the union of
$P^{t},P^{b},P,P^{\prime},Q$ and $Q^{\prime}$ is at least

$(n-1)M^{3}+4n(n+1)+W$

and so, by Claims 5.8, 5.9, 5.10 and 5.11, the weight of $E$ is at least

$2M^{5}+M^{4}+(n-1)M^{3}+M^{2}+(4n+1)(n+1)+p_{0}-p^{\prime}_{0}+W.$ (2)

######  Claim 5.23.

The following hold.

  * (1)

$i_{1}=i_{2}$ and $(i_{1},j_{1})\in S$.

  * (2)

$W=-12$ and $p_{0}=p^{\prime}_{0}$.

###### Proof.

Since the weight of $E$ is at most $M_{n}^{*}$, it follows from Equation 2
that

$\begin{split}M_{n}^{*}&=2M^{5}+M^{4}+(n-1)M^{3}+M^{2}+(4n+1)(n+1)-12\\\ &\geq
2M^{5}+M^{4}+(n-1)M^{3}+M^{2}+(4n+1)(n+1)+p_{0}-p^{\prime}_{0}+W.\end{split}$

Thus, by definition of $W$,

$\begin{split}&p_{0}-p^{\prime}_{0}+|i_{1}-i_{0}|+4(n+i_{2}-i^{\prime\prime})+4(i^{\prime}-i_{0})+4(t^{\prime}-j_{0})+4(t^{\prime\prime}-j^{\prime}_{0})\\\
&\leq-4+3(p_{1}+m(P,d\ell))+2p_{2}\\\ &\leq 4\end{split}$ (3)

as $p_{1},p_{2}\in\\{0,1\\}$ by definition and $m(D,d\ell)\in\\{0,1\\}$ by
5.19. Now suppose to the contrary that $p^{\prime}_{0}>p_{0}$ or,
equivalently, that $j^{\prime}_{0}>j_{0}$. Then since $t^{\prime}\geq t\geq
t^{\prime\prime}\geq j^{\prime}_{0}$ by Observations 5.16 and 5.22,
$p^{\prime}_{0}-p_{0}=j^{\prime}_{0}-j_{0}\leq t^{\prime}-j_{0}$ and so,

$\begin{split}&p_{0}-p^{\prime}_{0}+4(t^{\prime}-j_{0})+|i_{1}-i_{0}|+4(n+i_{2}-i^{\prime\prime})+4(i^{\prime}-i_{0})+4(t^{\prime\prime}-j^{\prime}_{0})\\\
&\geq
3(t^{\prime}-j_{0})+|i_{1}-i_{0}|+4(n+i_{2}-i^{\prime\prime})+4(i^{\prime}-i_{0})+4(t^{\prime\prime}-j^{\prime}_{0}).\end{split}$

But $n+i_{2}\geq i^{\prime\prime}$, $i^{\prime}\geq i_{0}$ and $t^{\prime}\geq
t^{\prime\prime}\geq j^{\prime}_{0}>j_{0}$ by Observations 5.15, 5.16, 5.17
and 5.22, hence

$3(t^{\prime}-j_{0})+|i_{1}-i_{0}|+4(n+i_{2}-i^{\prime\prime})+4(i^{\prime}-i_{0})+4(t^{\prime\prime}-j^{\prime}_{0})\geq
3.$

It then follows from Equation 3 and the above that $p_{1}=m(P,d\ell)=p_{2}=1$
and $t^{\prime}=j_{0}+1$; however, by 5.20, if $p_{1}=1$ then $t^{\prime}\geq
t+1$ and so, by 5.16, $j^{\prime}_{0}\leq t\leq t^{\prime}-1=j_{0}$, a
contradiction. Thus, $p_{0}\geq p^{\prime}_{0}$ and so,

$p_{0}-p^{\prime}_{0}+|i_{1}-i_{0}|+4(n+i_{2}-i^{\prime\prime})+4(i^{\prime}-i_{0})+4(t^{\prime}-j_{0})+4(t^{\prime\prime}-j^{\prime}_{0})\geq
0$ (4)

by Observations 5.15, 5.16, 5.17 and 5.22. Now suppose for a contradiction
that $p_{1}=0$. Then by Equation 3,

$p_{0}-p^{\prime}_{0}+|i_{1}-i_{0}|+4(n+i_{2}-i^{\prime\prime})+4(i^{\prime}-i_{0})+4(t^{\prime}-j_{0})+4(t^{\prime\prime}-j^{\prime}_{0})\leq
1$

and so, by Observations 5.15, 5.16, 5.17 and 5.22, we must have
$n+i_{2}=i^{\prime\prime}$, $t^{\prime}=j_{0}$,
$t^{\prime\prime}=j^{\prime}_{0}$ and $i_{0}=i^{\prime}$. But then, by
Observations 5.12 and 5.16, $p_{0}=n+1-i_{0}$ which implies that $P$ contains
no left shortcut edge as $t^{\prime}=j_{0}$; thus, by Equation 3,

$p_{0}-p^{\prime}_{0}+|i_{1}-i_{0}|+4(n+i_{2}-i^{\prime\prime})+4(i^{\prime}-i_{0})+4(t^{\prime}-j_{0})+4(t^{\prime\prime}-j^{\prime}_{0})\leq-2,$

as $m(P,d\ell)=0$, a contradiction to Equation 4. Hence, $p_{1}=1$ and so,
$m(D,d\ell)=1$ as well. Now by 5.20, $t^{\prime}\geq j_{0}+1$ and so, by
Equation 3,

$4\leq 4(t^{\prime}-j_{0})\leq
p_{0}-p^{\prime}_{0}+|i_{1}-i_{0}|+4(n+i_{2}-i^{\prime\prime})+4(i^{\prime}-i_{0})+4(t^{\prime}-j_{0})+4(t^{\prime\prime}-j^{\prime}_{0})\leq
2+2p_{2}.$

Therefore, $p_{2}=1$ and $t^{\prime}-1=j_{0}=j^{\prime}_{0}=t^{\prime\prime}$,
$i_{1}=i_{0}=i^{\prime}$ and $n+i_{2}=i^{\prime\prime}$ by Observations 5.15,
5.16, 5.17 and 5.22; in particular, $W=-12$. Now since $p_{1}=1$,
$(i^{\prime},j_{1})\in S$ by definition and so,
$t^{\prime}=j_{1}n+2-i^{\prime}$ by construction; and since $p_{2}=1$,
$(i^{\prime\prime}-n,j_{1})\in S$ by definition and so,
$t^{\prime\prime}=j_{1}n+1-(i^{\prime\prime}-n)$ by construction. As
$t^{\prime}-1=t^{\prime\prime}$, $i^{\prime}=i_{1}$ and
$i_{2}=i^{\prime\prime}-n$, we conclude that $i_{1}=i_{2}$ and
$(i_{1},j_{1})\in S$. ∎

It now follows from Claims 5.11 and 5.23(1) that $E$ represents the pair
$(i_{1},j_{1})\in S$; and by combining Equation 2 with 5.23(2), we conclude
that the weight of $E$ is at least $M_{n}^{*}$ and thus exactly $M_{n}^{*}$
which completes the proof. ∎

Up Main Gadget. Given an integer $n>0$, the up main gadget $uMG_{S}$
represents a set $S\subseteq[n]\times[n]$555Recall that, by assumption,
$1<x,y<n$ holds for every $(x,y)\in S$. and is constructed as follows. It is
an edge-weighted planar digraph consisting of a $2n\times n^{2}$ grid, where
the vertex lying at the intersection of column $i$ and row $j$ is denoted by
$x_{i,j}$, and $6n$ additional vertices
$\ell_{1},\ldots,\ell_{n},\ell^{\prime}_{1},\ldots,\ell^{\prime}_{n},r_{1},\ldots,r_{n},$
$r^{\prime}_{1},\ldots,r^{\prime}_{n},t_{1},\ldots,t_{n}$,
$b_{1},\ldots,b_{n}$. The adjacencies and edge weights are defined as follows.

  * •

_Source edges:_ for every $i\in[n]$, there is an edge $(b_{i},x_{n+i,1})$.
Together these edges are called source edges. The weight of each such edge is
set to $M^{5}$.

  * •

_Top sink edges:_ for every $i\in[n]$, there is an edge $(x_{i,n^{2}},t_{i})$.
Together these edges are called top sink edges. The weight of each such edge
is set to $M^{5}$.

  * •

_Left sink edges:_ for every $j\in[n]$, there is an edge
$(\ell^{\prime}_{j},\ell_{j})$ whose weight is set to $Mj$. Together these
edges are called left sink edges.

  * •

_Right sink edges:_ for every $j\in[n]$, there is an edge
$(r^{\prime}_{j},r_{j})$ whose weight is set to $M^{2}-Mj$. Together these
edges are called right sink edges.

  * •

_Left internal sink edges:_ for every $j\in[n]$ and every $(j-1)n+1\leq p\leq
jn$, there is an edge $(x_{1,p},\ell^{\prime\prime}_{j})$ whose weight is set
to $p-(j-1)n$. For every fixed $j\in[n]$, these edges together are called the
$j^{th}$ left internal sink edges.

  * •

_Right internal sink edges:_ for every $j\in[n]$ and every $(j-1)n+1\leq p\leq
jn$, there is an edge $(x_{2n,p},r^{\prime\prime}_{j})$ whose weight is set to
$n+1-(p-(j-1)n)$. For every fixed $j\in[n]$, these edges together are called
the $j^{th}$ right internal sink edges.

  * •

_Left bridge edges:_ for every $j\in[n]$, and every $(j-1)n+1\leq p\leq jn$,
there is an edge $(x_{n+1,p},x_{n,p})$. For every fixed $j\in[n]$, these edges
together are called the $j^{th}$ right bridge edges. The weight of each
$j^{th}$ left bridge edge is set to $M^{4}$.

  * •

_Upward bridge edges:_ for every $j\in\\{pn~{}|~{}p\in[n-1]\\}$ and every
$i\in[2n]$, there is an edge $(x_{i,j},x_{i,j+1})$. For every fixed
$j\in\\{pn~{}|~{}p\in[n-1]\\}$, these edges together are called the $j^{th}$
upward bridge edges. The weight of each $j^{th}$ downward bridge edge is set
to $M^{3}$.

  * •

_Up edges:_ for every $i\in[2n]$, every $j\in[n]$ and every $(j-1)n+1\leq
p\leq jn-1$, there is an edge $(x_{i,p},x_{i,p+1})$. Together these edges are
called up edges. The weight of each such edge is set to $4$.

  * •

_Left edges:_ for every $j\in[n]$, every $(j-1)n+1\leq p\leq jn-1$ and every
$2\leq q\leq jn+1-p$, there is an edge $(x_{q,p},x_{q-1,p})$; and for every
$j\in[n]$, every $(j-1)n+1\leq p\leq jn-1$ and every $2\leq i\leq n$, there is
an edge $(x_{i,p},x_{i-1,p}$. Together these edges are called left edges. The
weight of each such edge is set to $4$.

  * •

_Right edges:_ for every $j\in[n]$, every $(j-1)n+2\leq p\leq jn$ and every
$jn+1-p\leq q\leq n-1$, there is an edge $(x_{n+q,p},x_{n+q+1,p})$. Together
these edges are called right edges. The weight of each such edge is set to
$4$.

  * •

_Shortcut edges:_ for every $s=(i,j)\in S$, we introduce two shortcut edges
$e^{\ell}_{s},e^{r}_{s}$ as follows. Set $p=jn+1$ then

    * –

subdivide the edge $(x_{i,p-i},x_{i,p+1-i})$ by adding a vertex $y_{i,j}$ and
the edge $(x_{i,p-i},y_{i,j})$ (of weight $3$) with the edge
$(y_{i,j},x_{i,p+1-i})$ (of weight $1$);

    * –

subdivide the edge $(x_{n+i,p-1-i},x_{n+i,p-i})$ by adding a vertex $z_{i,j}$
and the edge

$(x_{n+i,p-1-i},z_{i,j})$ (of weight $3$) with the edge
$(z_{i,j},x_{n+i,p-i})$ (of weight $1$).

The introduced edges are called _down subdivided edges_. Then

    * –

$e^{\ell}_{s}=(y_{i,j},x_{i-1,p-i})$ and its weight set to $2$;

    * –

$e^{r}_{s}=(z_{i,j},x_{n+i+1,p-i})$ and its weight set to $2$.

The edges $e^{\ell}_{s}$ are called _left_ shortcut edges and the edges
$e^{r}_{s}$ are called _right_ shortcut edges.

This concludes the construction of the up main gadget $uMG_{S}$ (see Figure 15
for an illustration of the up main gadget $uMG_{S}$ with $n=4$ representing
$S=\\{(2,2),(2,3),(3,2)\\}$). We call the vertices $\ell_{1},\ldots,\ell_{n}$
the _left vertices_ , the vertices $r_{1},\ldots,r_{n}$ the _right vertices_ ,
the vertices $t_{1},\ldots,t_{n}$ the _top vertices_ and the vertices
$b_{1},\ldots,b_{n}$ the _bottom vertices_.

$b_{1}$$b_{2}$$b_{3}$$b_{4}$$t_{1}$$t_{2}$$t_{3}$$t_{4}$$\ell^{\prime}_{1}$$\ell_{1}$$\ell^{\prime}_{2}$$\ell_{2}$$\ell^{\prime}_{3}$$\ell_{3}$$\ell^{\prime}_{4}$$\ell_{4}$$r^{\prime}_{1}$$r_{1}$$r^{\prime}_{2}$$r_{2}$$r^{\prime}_{3}$$r_{3}$$r^{\prime}_{4}$$r_{4}$
Figure 15: The up main gadget $uMG_{S}$ with $n=4$ representing
$S=\\{(2,2),(2,3),(3,2)\\}$ (the red edges are the shortcut edges). A set of
edges representing $(2,2)$ is highlighted.

A set $E\subseteq E(uMG_{S})$ satisfies the _connectedness_ property if the
following hold in $E$:

  * •

a bottom vertex can reach a top vertex;

  * •

a bottom vertex can reach a left vertex;

  * •

a bottom vertex can reach a right vertex.

A set $E\subseteq E(uMG_{S})$ satisfying the connectedness property
_represents_ a pair $(i,j)\in[n]\times[n]$ if the only source edge in $E$ is
the one incident to $b_{i}$, the only top sink edge in $E$ is the one incident
to $t_{i}$, the only left sink edge in $E$ is the one incident to $\ell_{j}$
and the only right sink edge in $E$ is the one incident to $r_{j}$ (see Figure
15 for a set of edges representing $(2,2)$). Symmetrical to Lemma 5.7, we have
the following.

######  Lemma 5.24.

For any $n>0$ and any $S\subseteq[n]\times[n]$, the up main gadget $uMG_{S}$
satisfies the following properties.

  * (1)

For every $(i,j)\in S$, there exists a set $E_{i,j}\subseteq E(uMG_{S})$ of
weight $M_{n}^{*}$ representing $(i,j)$.

  * (2)

If there exists a set $E\subseteq E(uMG_{S})$ of weight at most $M_{n}^{*}$
satisfying the connectedness property then $E$ has weight exactly $M_{n}^{*}$
and represents a pair $(i,j)\in S$.

Reduction. Given an instance $(k,n,\\{S_{i,j}~{}|~{}i,j\in[k]\\})$ of Grid
Tiling, we construct an equivalent instance $(G,T,D)$ of (edge-weighted)
Planar $\mathcal{A}_{1}$-Steiner Network where $G$ is defined as follows (see
Figure 16).

  * •

We introduce a total of $k^{2}$ (down/up) main gadgets and $k(k+1)$ connector
gadgets.

  * •

For every set $S_{i,j}$ of the Grid Tiling instance such that $i$ is odd, we
introduce an up main gadget $uMG_{i,j}$ representing $S_{i,j}$. The up main
gadget $uMG_{i,j}$ is surrounded by two connector gadgets: $CG_{i,j}$ lying to
its left and $CG_{i+1,j}$ lying to its right. We identify each right vertex of
$CG_{i,j}$ with the left vertex of $uMG_{i,j}$ of the same index, and each
left vertex of $CG_{i+1,j}$ with the right vertex of $uMG_{i,j}$ of the same
index. Furthermore, for every $j\in[k-1]$, $uMG_{i,j}$ lies above
$uMG_{i,j+1}$ and we identify each bottom vertex of $uMG_{i,j}$ with the top
vertex of $uMG_{i,j+1}$ of the same index.

  * •

For every set $S_{i,j}$ of the Grid Tiling instance such that $i$ is even, we
introduce a down main gadget $dMG_{i,j}$ representing $S_{i,j}$. The down main
gadget $dMG_{i,j}$ is surrounded by two connector gadgets: $CG_{i,j}$ lying to
its left and $CG_{i+1,j}$ lying to its right. We identify each right vertex of
$CG_{i,j}$ with the left vertex of $dMG_{i,j}$ of the same index, and each
left vertex of $CG_{i+1,j}$ with the right vertex of $dMG_{i,j}$ of the same
index. Furthermore, for every $j\in[k-1]$, $dMG_{i,j}$ lies above
$dMG_{i,j+1}$ and we identify each bottom vertex of $dMG_{i,j}$ with the top
vertex of $dMG_{i,j+1}$ of the same index.

  * •

We introduce $k$ terminals $t_{1},\ldots,t_{k}$ and add the following edges of
weight 0: for every odd $i\in[k]$, we add an edge from each top vertex of
$uMG_{i,1}$ to $t_{i}$ and for every even $i\in[k]$, we add an edge from each
bottom vertex of $dMG_{i,k}$ to $t_{i}$.

  * •

We introduce two vertices $r_{1}$ and $r_{2}$ and add the following edges of
weight 0: there is an edge from $r_{1}$ to every terminal $t_{i}$ such that
$i\in[k]$ is odd; for every even $i\in[k]$, there is an edge from $r_{1}$ to
every top vertex of $dMG_{i,1}$; for every $j\in[k]$, there is an edge from
$r_{1}$ to every left vertex of $CG_{1,j}$; and if $k$ is odd then for every
$j\in[k]$, there is an edge from $r_{1}$ to every right vertex of
$CG_{k+1,j}$. Similarly, there is an edge from $r_{2}$ to every terminal
$t_{i}$ such that $i$ is even; for every odd $i\in[k]$, there is an edge from
$r_{1}$ to every bottom vertex of $dMG_{i,k}$; and if $k$ is even then for
every $j\in[k]$, there is an edge from $r_{1}$ to every right vertex of
$CG_{k+1,j}$.

This concludes the construction of $G$. The set $T$ of terminals consists of
the union of the two terminal vertices in each connector gadget and
$\\{r_{1},r_{2}\\}\cup\\{t_{i}~{}|~{}i\in[k]\\}$ (note that
$|T|=2k(k+1)+k+2$). The demand graph $D$ is the pure out-diamond on vertex set
$T$ where $r_{1}$ and $r_{2}$ are the two vertices of in-degree 0. In the
following, we let

$W_{n}^{*}=k^{2}M_{n}^{*}+k(k+1)C_{n}^{*}.$

$CG_{1,1}$$CG_{1,2}$$CG_{1,3}$$CG_{2,1}$$CG_{2,2}$$CG_{2,3}$$CG_{3,1}$$CG_{3,2}$$CG_{3,3}$$CG_{4,1}$$CG_{4,2}$$CG_{4,3}$$uMG_{1,1}$$\cdots$$\cdots$$uMG_{1,2}$$\cdots$$\cdots$$uMG_{1,3}$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$dMG_{2,1}$$\cdots$$\cdots$$dMG_{2,2}$$\cdots$$\cdots$$dMG_{2,3}$$\cdots$$\cdots$$uMG_{3,1}$$\cdots$$\cdots$$uMG_{3,2}$$\cdots$$\cdots$$uMG_{3,3}$$\cdots$$\cdots$$t_{1}$$\cdots$$t_{2}$$\cdots$$t_{3}$$\cdots$$r_{1}$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$r_{2}$$\cdots$$\cdots$
Figure 16: An illustration of the reduction from Grid Tiling to Planar
$\mathcal{A}_{1}$-Steiner Network with $k=3$ (the black vertices are the
terminals).

######  Lemma 5.25.

The Grid Tiling instance $(k,n,\\{S_{i,j}~{}|~{}i,j\in[k]\\})$ has a solution
if and only if the (edge-weighted) Planar $\mathcal{A}_{1}$-Steiner Network
instance $(G,T,D)$ has a solution of weight at most $W_{n}^{*}$.

###### Proof.

Assume first that the instance $(k,n,\\{S_{i,j}~{}|~{}i,j\in[k]\\})$ of Grid
Tiling has a solution, that is, for every $i,j\in[k]$, there is an entry
$(x_{i,j},y_{i,j})\in S_{i,j}$ such that

  * •

for every $i\in[k]$, $x_{i,1}=x_{i,2}=\ldots=x_{i,k}=\alpha_{i}$ and

  * •

for every $j\in[k]$, $y_{1,j}=y_{2,j}=\ldots=y_{k,j}=\beta_{j}$.

We construct a solution $E$ for the Planar $\mathcal{A}_{1}$-Steiner Network
instance $(G,T,D)$ of weight at most $W_{n}^{*}$ as follows. Include in $E$

  * •

for every odd $i\in[k]$, the edge $(r_{1},t_{i})$ of weight 0 and for every
even $i\in[k]$, the edge $(r_{2},t_{i})$ of weight 0;

  * •

for every even $i\in[k]$, the edge from $r_{1}$ to the top vertex of index
$\alpha_{i}$ in $dMG_{i,1}$ of weight 0 and for every odd $i\in[k]$, the edge
from $r_{2}$ to the bottom vertex of index $\alpha_{i}$ in $dMG_{i,k}$ of
weight 0;

  * •

for every $j\in[k]$, the edge from $r_{1}$ to the left vertex of index
$\beta_{j}$ in $CG_{1,j}$ of weight 0;

  * •

if $k$ is odd then for every $j\in[k]$, the edge from $r_{1}$ to the right
vertex of index $\beta_{j}$ in $CG_{k+1,j}$ of weight 0 and if $k$ is even
then for every $j\in[k]$, the edge from $r_{2}$ to the right vertex of
$\beta_{j}$ in $CG_{k+1,j}$ of weight 0;

  * •

for every $j\in[k]$ and every $i\in[k]$, the set $E^{C}_{i,j}\subseteq
E(CG_{i,j})$ of weight $C_{n}^{*}$ representing $\beta_{j}$ whose existence is
guaranteed by Lemma 5.2(1);

  * •

for every $j\in[k]$ and every odd $i\in[k]$, the set $E^{M}_{i,j}\subseteq
E(uMG_{i,j})$ of weight $M_{n}^{*}$ representing $(\alpha_{i},\beta_{j})$
whose existence is guaranteed by Lemma 5.24(1); and

  * •

for every $j\in[k]$ and every even $i\in[k]$, the set $E^{M}_{i,j}\subseteq
E(dMG_{i,j})$ of weight $M_{n}^{*}$ representing $(\alpha_{i},\beta_{j})$
whose existence is guaranteed by Lemma 5.7(1).

It is not difficult to see that the weight of $E$ is
$k^{2}M_{n}^{*}+k(k+1)C_{n}^{*}=W_{n}^{*}$ and that by the connectedness of
the sets $E^{C}_{p,j}$ and $E^{M}_{i,j}$ for every $i,j\in[k]$ and
$p\in[k+1]$, $r_{1}$ and $r_{2}$ can reach every terminal in
$T\setminus\\{r_{1},r_{2}\\}$ in $E$.

Conversely, assume that the Planar $\mathcal{A}_{1}$-Steiner Network instance
$(G,T,D)$ has a solution $E$ of weight at most $W_{n}^{*}$. We contend that
for every $i\in[k+1]$ and every $j\in[k]$, $E\cap E(CG_{i,j})$ satisfies the
connectedness property. Indeed, if this is not the case for some $i\in[k+1]$
and $j\in[k]$, say no left vertex of $V(CG_{i,j})$ can reach the terminal
$p\in V(CG_{i,j})$ in $E$ (the other cases are symmetric) then either $i$ is
even in which case $r_{2}$ cannot reach $p$ in $E$, or $i$ is odd in which
case $r_{1}$ cannot reach $p$ in $E$, a contradiction in both cases.
Similarly, the restriction of $E$ to any (down/up) main gadget satisfies the
connectedness property: indeed, if for some $j\in[k]$ and for some even
$i\in[k]$ (we argue similarly if $i$ is odd), $E\cap E(dMG_{i,j})$ does not
satisfy the connectedness property, then either no top vertex of $dMG_{i,j}$
can reach a bottom vertex of $dMG_{i,j}$ in $E$ in which case $r_{2}$ cannot
reach $t_{i}$ in $E$; or no top vertex of $dMG_{i,j}$ can reach a left (or
right) vertex of $dMG_{i,j}$ in $E$ in which case $r_{2}$ (or $r_{1}$) cannot
reach the terminal vertices of $CG_{i,j}$ in $E$, a contradiction in both
cases.

Next, we argue that the weight of the restriction of $E$ to any connector
gadget is $C_{n}^{*}$ and that the weight of the restriction of $E$ to any
(down/up) main gadget is $M_{n}^{*}$. To this end, let $c$ and $C$ be the
number of connector gadgets whose weight in $E$ is at most $C_{n}^{*}$ and
greater than $C_{n}^{*}$, respectively. Then $c+C=k(k+1)$ and by Lemma 5.2(2),
any connector gadget whose weight in $E$ is at most $C_{n}^{*}$ has in fact a
weight of exactly $C_{n}^{*}$ in $E$. Similarly, let $m$ and $M$ be the number
of (down/up) main gadgets whose weight in $E$ is at most $M_{n}^{*}$ and
greater than $M_{n}^{*}$ respectively. Then $m+M=k^{2}$ and by Lemmas 5.7 and
5.24, any (down/up) main gadget whose weight in $E$ is at most $M_{n}^{*}$ has
in fact a weight of exactly $M_{n}^{*}$ in $E$. Now by definition of
$W_{n}^{*}$,

$\begin{split}W_{n}^{*}&=k^{2}M_{n}^{*}+k(k+1)C_{n}^{*}\\\ &\geq
mM_{n}^{*}+M(M_{n}^{*}+1)+cC_{n}^{*}+C(C_{n}^{*}+1)\\\
&=k^{2}M_{n}^{*}+M+k(k+1)C_{n}^{*}+C\end{split}$

which implies that $M=C=0$. Thus, every connector gadget has weight
$C_{n}^{*}$ in $E$ and every (down/up) main gadget has weight $M_{n}^{*}$ in
$E$. From Lemmas 5.2(2), 5.7(2) and 5.24(2), it then follows that

  * •

for every $j\in[k]$ and every $i\in[k+1]$, the restriction of $E$ to the
connector gadget $CG_{i,j}$ represents an integer
$\beta^{\prime}_{i,j}\in[n]$;

  * •

for every $j\in[k]$ and every even $i\in[k]$, the restriction of $E$ to the
down main gadget $dMG_{i,j}$ represents a pair
$(\alpha_{i,j},\beta_{i,j})\in[n]\times[n]$; and

  * •

for every $j\in[k]$ and every odd $i\in[k]$, the restriction of $E$ to the up
main gadget $uMG_{i,j}$ represents a pair
$(\alpha_{i,j},\beta_{i,j})\in[n]\times[n]$.

Let us show that for every $i,j\in[k]$ the entries
$(\alpha_{i,j},\beta_{i,j})\in S_{i,j}$ form a solution to the Grid Tiling
instance $(k,n,\\{S_{i,j}~{}|~{}i,j\in[k]\\})$ which if true, would conclude
the proof. To this end, we first prove that for every $i,j\in[k]$,
$\beta^{\prime}_{i,j}=\beta_{i,j}$. Consider an even $i\in[k]$. Then by Lemma
5.7(2), the only left sink edge in $E$ incident to a left vertex of
$dMG_{i,j}$ is the one incident to the left vertex of index $\beta_{i,j}$; and
by Lemma 5.2(2), the only right source edge in $E$ incident to a right vertex
of $CG_{i,j}$ is the one incident to the right vertex of index
$\beta^{\prime}_{i,j}$. Thus, if $\beta^{\prime}_{i,j}\neq\beta_{i,j}$ then
$r_{1}$ cannot reach the terminal vertices of $CG_{i,j}$ in $E$, a
contradiction. We conclude similarly if $i$ is odd.

Second, we show that for every $i,j\in[k]$,
$\beta^{\prime}_{i+1,j}=\beta_{i,j}$. Consider an even $i\in[k]$. Then by
Lemma 5.7(2), the only right sink edge in $E$ incident to a right vertex of
$dMG_{i,j}$ is the one incident to the right vertex of index $\beta_{i,j}$;
and by Lemma 5.2(2), the only left source edge in $E$ incident to a left
vertex of $CG_{i+1,j}$ is the one incident to the left vertex of index
$\beta^{\prime}_{i,j}$. Thus, if $\beta^{\prime}_{i,j}\neq\beta_{i,j}$ then
$r_{2}$ cannot reach the terminal vertices of $CG_{i+1,j}$ in $E$, a
contradiction. We conclude similarly if $i$ is odd.

It follows from the above that for every $i\in[k-1]$ and every $j\in[k]$,
$\beta_{i+1,j}=\beta^{\prime}_{i+1,j}=\beta_{i,j}$; we next show that for
every $i\in[k]$ and every $j\in[k-1]$, $\alpha_{i,j}=\alpha_{i,j+1}$. Consider
an even $i\in[k]$. Then by Lemma 5.7(2), the only bottom sink edge in $E$
incident to a bottom vertex of $dMG_{i,j}$ is the one incident to the bottom
vertex of index $\alpha_{i,j}$; and by Lemma 5.7(2), the only source edge in
$E$ incident to a top vertex of $dMG_{i,j+1}$ is the one incident to the top
vertex of index $\alpha_{i,j+1}$. Thus, if $\alpha_{i,j}\neq\alpha_{i,j+1}$
then $r_{1}$ cannot reach the terminal $t_{i}$ in $E$, a contradiction. We
conclude similarly if $i$ is odd. Therefore, the entries
$(\alpha_{i,j},\beta_{i,j})\in S_{i,j}$ form a solution to the Grid Tiling
instance $(k,n,\\{S_{i,j}~{}|~{}i,j\in[k]\\})$ as claimed. ∎

Let us finally explain how to get rid of the edge-weights (we use the same
trick as in [8]). We replace every edge $(x,y)$ of weight $w$ in the instance
$(G,T,D)$ of (edge-weighted) Planar $\mathcal{C}_{1}$-Steiner Network
constructed above, with a directed path from $x$ to $y$ of length $w\cdot n+1$
where $n=|V(G)|$. We let $G^{\prime}$ be the resulting graph. Then similarly
to [8, Theorem A.1], we can show that the instance $(G,T,D)$ of edge-weighted
Planar $\mathcal{C}_{1}$-Steiner Network has a solution of weight at most $W$
if and only if the instance $(G^{\prime},T,D)$ of Planar
$\mathcal{C}_{1}$-Steiner Network has a solution of size at most $Wn+n$.

###  5.3 Hard patterns

The aim of this section is to prove that for every $\ell\in[8104]$, Planar
$\mathcal{C}_{\ell}$-Steiner Network is $\mathsf{W}[1]$-hard parameterized by
the number $k$ of terminals and does not admit a $f(k)\cdot n^{o(k)}$
algorithm for any computable function $f$, unless $\mathsf{ETH}$ fails. For
each $\ell\in[8104]$, we give a reduction which transforms an instance of
$k\times k$-Grid Tiling (see Section 5.2 for a definition of this problem)
into an instance of (edge-weighted)666We then use the same trick as in Section
5.2 to get rid of the edge-weights. Planar $\mathcal{C}_{\ell}$-Steiner
Network with $O(k)$ terminals. The constructed instances in each case are very
similar and are based on a construction developed in the proof of [8, Theorem
1.4], which we describe below as the _main gadget_. We then show how to built
upon this construction to handle the hard matching patterns (see Section
5.3.1) and the hard biclique patterns (see Section 5.3.2).

Main Gadget. As mentioned above, we use the same construction as in the proof
of [8, Theorem 1.4]. More precisely, given an integer $n>0$ and a subset
$S\subseteq[n]\times[n]$777Recall that, by assumption, $1<x,y<n$ holds for
every $(x,y)\in S$., we first construct an edge-weighted planar digraph $G(S)$
as follows. The graph $G(S)$ consists of an $n\times n$ grid where the
horizontal edges are oriented towards the right and the vertical edges are
oriented towards the bottom, that is, denoting by $x_{i,j}$ the vertex lying
at the intersection of column $i$ and row $j$, there is an edge

  * •

$(x_{i+1,j},x_{i,j})$ (of weight 2) for every $i\in[n-1]$ and $j\in[n]$, and

  * •

$(x_{i,j},x_{i,j+1})$ (of weight 2) for every $i\in[n]$ and $j\in[n-1]$.

Then for every $(i,j)\in S$, we subdivide the edge $(x_{i-1,j},x_{i,j})$, by
adding a vertex $y_{i,j}$ and the edges $(x_{i-1,j},y_{i,j})$ and
$(y_{i,j},x_{i,j})$ (both of weight 1), and further add the edge
$(x_{i,j-1},y_{i,j})$ (of weight 1). This concludes the construction of
$G(S)$. In the following, we call the vertices
$x_{1,1},x_{1,2},\ldots,x_{1,n}$ the _left vertices_ , the vertices
$x_{n,1},x_{n,2}\ldots,x_{n,n}$ the _right vertices_ , the vertices
$x_{1,n},x_{2,n},\ldots,x_{n,n}$ the _top vertices_ and the vertices
$x_{1,1},x_{2,1},\ldots,x_{n,1}$ the _bottom vertices_.

Now given a collection $\mathcal{S}=\\{S_{i,j}~{}|~{}i,j\in[k]\\}$ of $k^{2}$
subsets of $[n]\times[n]$, the _main gadget $MG(\mathcal{S})$_ for
$\mathcal{S}$ is constructed as follows.

  * •

For every set $S_{i,j}\in\mathcal{S}$, we introduce a copy of the graph
$G(S_{i,j})$ as constructed above. For every $i\in[n]$ and $j\in[n-1]$, the
graph $G(S_{i,j+1})$ lies below the $G(S_{i,j})$; we add an edge (of weight 2)
from each top vertex of $G(S_{i,j+1})$ to the bottom vertex of $G(S_{i,j})$ of
the same index. Similarly, for every $i\in[n-1]$ and $j\in[n]$, the graph
$G(S_{i,j})$ lies to the left of the graph $G(S_{i+1,j})$; we add an edge (of
weight 2) from each right vertex of $G(S_{i,j})$ to the left vertex of
$G(S_{i+1,j})$ of the same index.

  * •

We introduce $4k$ additional vertices
$a_{1},\ldots,a_{k},b_{1},\ldots,b_{k},c_{1},\ldots,c_{k},d_{1},\ldots,d_{k}$
and the following edges (we fix $\Delta=5n^{2}$).

    * –

For every $j\in[k]$ and every $i\in[n]$, there is an edge from $a_{j}$ to the
left vertex of $G(S_{1,j})$ of index $i$ of weight $\Delta(n+1-i)$.

    * –

For every $j\in[k]$ and every $i\in[n]$, there is an edge from the right
vertex of $G(S_{n,j})$ of index $i$ to $b_{j}$ of weight $\Delta i$.

    * –

For every $j\in[k]$ and every $i\in[n]$, there is an edge from $c_{j}$ to the
top vertex of $G(S_{j,1})$ of index $i$ of weight $\Delta(n+1-i)$.

    * –

For every $j\in[k]$ and every $i\in[n]$, there is an edge from the bottom
vertex of $G(S_{j,n})$ of index $i$ to $d_{j}$ of weight $\Delta i$.

This concludes the construction of the main gadget $MG(\mathcal{S})$ for
$\mathcal{S}$ (see Figure 17 for an illustration of the main gadget
$MG(\mathcal{S})$ with $n=4$ for $\mathcal{S}=\\{S_{i,j}~{}|~{}i,j\in[3]\\}$
where $S_{1,1}=\\{(2,2),(2,3),(3,3)\\}$ and $S_{i,j}=\emptyset$ for every
$(i,j)\neq(1,1)$). We now set $I=\\{a_{i},b_{i},c_{i},d_{i}~{}|~{}i\in[k]\\}$
and let $M$ be the induced matching
$\\{(a_{i},b_{i}),(c_{i},d_{i})~{}|~{}i\in[k]\\}$. We further set

$B^{*}=2k(\Delta(n+1)+2(k+1)+2k(n-1)).$

######  Lemma 5.26 ([8]).

The $k\times k$-Grid Tiling instance $(k,n,\mathcal{S})$ has a solution if and
only if the (edge-weighted) Planar $M$-Steiner Network instance
$(MG(\mathcal{S}),I,M)$ has a solution of weight at most $B^{*}-k^{2}$.

$G(S_{1,3})$$a_{3}$$4\Delta$$3\Delta$$2\Delta$$\Delta$$d_{1}$$\Delta$$2\Delta$$3\Delta$$4\Delta$$G(S_{1,2})$$a_{2}$$4\Delta$$3\Delta$$2\Delta$$\Delta$$G(S_{1,1})$$a_{1}$$4\Delta$$3\Delta$$2\Delta$$\Delta$$c_{1}$$4\Delta$$3\Delta$$2\Delta$$\Delta$$G(S_{2,3})$$d_{2}$$\Delta$$2\Delta$$3\Delta$$4\Delta$$G(S_{2,2})$$G(S_{2,1})$$c_{2}$$4\Delta$$3\Delta$$2\Delta$$\Delta$$G(S_{3,3})$$b_{3}$$\Delta$$2\Delta$$3\Delta$$4\Delta$$d_{3}$$\Delta$$2\Delta$$3\Delta$$4\Delta$$G(S_{3,2})$$b_{2}$$\Delta$$2\Delta$$3\Delta$$4\Delta$$G(S_{3,1})$$b_{1}$$\Delta$$2\Delta$$3\Delta$$4\Delta$$c_{3}$$4\Delta$$3\Delta$$2\Delta$$\Delta$
Figure 17: The main gadget $MG(\mathcal{S})$ with $n=4$ for
$\mathcal{S}=\\{S_{i,j}~{}|~{}i,j\in[3]\\}$ where
$S_{1,1}=\\{(2,2),(2,3),(3,3)\\}$ and $S_{i,j}=\emptyset$ for every
$(i,j)\neq(1,1)$.

####  5.3.1 Hard matching patterns

The aim of this section is to prove hardness for the hard matching patterns.
We restate here the definition of these graphs for the reader’s convenience.

######  Definition 1.4 ($t$-hard matching pattern).

A _$t$ -hard matching pattern_ is an (acyclic) digraph $G$ constructed the
following way. We start with disjoint vertex sets
$A=\\{a_{1},\ldots,a_{t}\\}$, $B=\\{b_{1},\ldots,b_{t}\\}$,
$C=\\{c_{1},\ldots,c_{t}\\}$ and $D=\\{d_{1},\ldots,d_{t}\\}$ and introduce
the edges $(a_{i},b_{i})$ and $(c_{i},d_{i})$ for every $i\in[t]$.
Furthermore, we introduce into $G$ any combination of the following items:

  1. 1.

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

  2. 2.

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

  3. 3.

an $S$-source for exactly one $S\in\\{A,B,C,D,A\cup C,B\cup D,B\cup C,A\cup
D\\}$;

  4. 4.

an $S$-sink for exactly one $S\in\\{A,B,C,D,A\cup C,B\cup D,B\cup C,A\cup
d\\}$;

  5. 5.

a vertex $r_{AD}$ such that $N^{-}(r_{AD})=A$ and $N^{+}(r_{AD})=D$;

  6. 6.

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

In particular, there are $5\cdot 5\cdot 9\cdot 9\cdot 2\cdot 2$ types of
$t$-hard matching patterns: we let $\mathcal{C}_{5},\ldots,\mathcal{C}_{8104}$
be the 8100 classes that each contain all the $t$-hard matching patterns of a
specific type for every $t$.

Formally, we aim to prove the following.

######  Lemma 5.27.

For every $\ell\in[5,8104]$, Planar $\mathcal{C}_{\ell}$-Steiner Network is
$\mathsf{W}[1]$-hard parameterized by the number $k$ of terminals and does not
admit a $f(k)\cdot n^{o(k)}$ algorithm for any computable function $f$, unless
$\mathsf{ETH}$ fails.

To prove the lemma, we use the construction described above and further add
vertices and edges so as to take into account the specific combination of the
items in Definition 1.4 for each fixed $\ell\in[5,8104]$.

Reduction. Consider $\ell\in[7,2031]$. Given an instance
$(k,n,\mathcal{S}=\\{S_{i,j}~{}|~{}i,j\in[k]\\})$ of $k\times k$-Grid Tiling,
we construct an equivalent instance $(G(\mathcal{S}),T,D)$ of (edge-weighted)
Planar $\mathcal{C}_{\ell}$-Steiner Network as follows. Let $MG(\mathcal{S})$
be the main gadget for $\mathcal{S}$ as constructed above. Then $T$ contains
$\\{a_{i},b_{i},c_{i},d_{i}~{}|~{}i\in[k]\\}$ (and possibly, as described
below, some additional vertices depending on the class $\mathcal{C}\ell$)
where $\\{(a_{i},b_{i})~{}|~{}i\in[k]\\}$ and
$\\{(c_{i},d_{i})~{}|~{}i\in[k]\\}$ are the two perfect matchings contained in
$D$. The graph $G(\mathcal{S})$ is then obtained from $MG(\mathcal{S})$ by
introducing the directed paths

$a_{1}\rightarrow\ldots\rightarrow a_{k},d_{1}\rightarrow\ldots\rightarrow
d_{k},c_{1}\rightarrow\ldots\rightarrow c_{k}\text{ and
}b_{1}\rightarrow\ldots\rightarrow b_{k}$

where the weight of each newly added edge is set to 0. Furthermore, if the
patterns in the class $C_{\ell}$ contain

  * •

a source (that is, a vertex of item 3 in Definition 1.4) then we add a vertex
$s$ to $G(\mathcal{S})$ and $T$, and the edges $(s,a_{1})$ and $(s,c_{1})$,
both of weight 0;

  * •

a sink (that is, a vertex of item 4 in Definition 1.4) then we add a vertex
$t$ to $G(\mathcal{S})$ and $T$, and the edges $(b_{k},t)$ and $(d_{k},t)$,
both of weight 0;

  * •

the vertex of item 5 in Definition 1.4, then we add a vertex $r_{AD}$ to
$G(\mathcal{S})$ and $T$, and the edges $(a_{k},r_{AD})$ and $(r_{AD},d_{1})$,
both of weight 0;

  * •

the vertex of item 6 in Definition 1.4, then we add a vertex $r_{CB}$ to
$G(\mathcal{S})$ and $T$, and the edges $(c_{k},r_{CB})$ and $(r_{CB},b_{1})$,
both of weight 0.

This concludes the construction of $G(\mathcal{S})$. We let $D$ be the
corresponding $k$-hard matching pattern of $\mathcal{C}_{\ell}$ on vertex set
$T$. Lemma 5.27 then follows from Lemma 5.26 and the lemma below.

######  Lemma 5.28.

The (edge-weighted) Planar $\mathcal{C}_{\ell}$-Steiner Network instance
$(G(\mathcal{S}),T,D)$ has a solution of weight at most $B^{*}-k^{2}$ if and
only if the (edge-weighted) Planar $M$-Steiner Network instance
$(MG(\mathcal{S}),I,M)$ has a solution of weight at most $B^{*}-k^{2}$.

###### Proof.

If $E$ is a solution of $(MG(\mathcal{S}),I,M)$ of weight at most
$B^{*}-k^{2}$ then it is easy to see that $E\cup(E(G(\mathcal{S}))\setminus
E(MG(\mathcal{S})))$ is a solution of $(G(\mathcal{S}),T,D)$ of weight at most
$B^{*}-k^{2}$. Conversely, if $E$ is a solution of $(G(\mathcal{S}),T,D)$ of
weight at most $B^{*}-k^{2}$ then the restriction of $E$ to $MG(\mathcal{S})$
is readily seen to be a solution of $(MG(\mathcal{S}),I,M)$ of weight at most
$B^{*}-k^{2}$. ∎

####  5.3.2 Hard biclique patterns

The aim of this section is to prove hardness for the hard biclique patterns.
We restate here the definition of these graphs for the reader’s convenience.

######  Definition 1.3 ($t$-hard biclique pattern).

A _$t$ -hard biclique pattern_ is an (acyclic) digraph $D$ constructed the
following way. We start with two disjoint sets $A$ and $B$ with $|A|=|B|=t$
and introduce every edge from $A$ to $B$. Furthermore, we introduce into $D$
any combination of the following items (see Figure 1):

  1. 1.

an $A$-source;

  2. 2.

a $B$-sink.

In particular, there are $2\cdot 2$ types of $t$-hard biclique patterns: we
let $\mathcal{C}_{1},\ldots,\mathcal{C}_{4}$ be the 4 classes that each
contain all the $t$-hard biclique patterns of a specific type for every $t$.

Formally, we aim to prove the following.

######  Lemma 5.29.

For every $\ell\in[4]$, Planar $\mathcal{C}_{\ell}$-Steiner Network is
$\mathsf{W}[1]$-hard parameterized by the number $k$ of terminals and does not
admit a $f(k)\cdot n^{o(k)}$ algorithm for any computable function $f$, unless
$\mathsf{ETH}$ fails.

We only formally prove the statement for the class of all hard biclique
patterns containing no further vertices as it will become clear from the proof
that to handle the classes of all hard biclique patterns containing

  * •

the sink vertex, it suffices to add a vertex $t$ and an edge $(t_{i},t)$ for
each $i\in[2k+1]$ in the construction below; or

  * •

the source vertex, it suffices to add a vertex $s$ and an edge $(s,s_{i})$ for
each $i\in[2k+1]$ in the construction below.

In the following, we assume that the class of all hard biclique patterns with
no further vertices is $\mathcal{C}_{1}$.

Reduction. Given an instance $(k,n,\mathcal{S}=\\{S_{i,j}~{}|~{}i,j\in[k]\\})$
of $k\times k$-Grid Tiling, we construct an equivalent instance
$(G(\mathcal{S}),T,D)$ of (edge-weighted) Planar $\mathcal{C}_{1}$-Steiner
Network as follows. We start by constructing an auxiliary planar digraph $H$
consisting of $2(2k+1)$ distinguished vertices
$s_{1},\ldots,s_{2k+1},t_{1},\ldots,t_{2k+1}$, and $2(2k+1)$ edge-disjoint
directed paths $P_{i,j}$ with $i\in[2k+1]$ and $j\in\\{i,i+1\\}$ (where
indices are taken modulo $2k+1$ henceforth), defined as follows.

  * •

For every $i\in[2k+1]$, $P_{i,i}=s_{i}u_{i}^{1}\ldots u_{i}^{2k-1}t_{i}$ is a
directed path from $s_{i}$ to $t_{i}$ of length $2k$.

  * •

For every $i\in[2k+1]$, $P_{i,i+1}$ is the directed path
$s_{i}u^{1}_{i-1}u^{2}_{i-2}\ldots u^{j}_{i-j}\ldots u^{2k-1}_{i+2}t_{i+1}$
from $s_{i}$ to $t_{i+1}$ of length $2k$.

(For $k=3$, the graph $H$ can be obtained from the graph depicted in Figure 18
by ignoring the blue vertices and contracting every grey box into a single
vertex.) Note that by construction, the following holds.

######  Observation 5.30.

For every $i\in[2k+1]$, there is a unique path from $s_{i}$ to $t_{i}$
($t_{i+1}$, respectively) in $H$, namely $P_{i,i}$ ($P_{i,i+1}$,
respectively).

The graph $G(\mathcal{S})$ is then obtained from $H$ as follows (see Figure
18).

  * •

We subdivide the edge $(s_{k+1},u^{k+1}_{1})$ by adding the vertex $a_{1}$ and
the edges $(s_{k+1},a_{1})$ and $(a_{1},u^{k+1}_{1})$; and for every $2\leq
i\leq k$, we subdivide the edge $(u^{i}_{k+1-i},u^{i}_{k+2-i})$ by adding the
vertex $a_{k+2-i}$ and the edges $(u^{i}_{k+1-i},a_{k+2-i})$ and
$(a_{k+2-i},u^{i}_{k-i})$.

  * •

We subdivide the edge $(u^{2}_{2k-1},t_{2})$ by adding the vertex $b_{k}$ and
the edges $(u^{2}_{2k-1},b_{k})$ and $(b_{k},t_{2})$; and for every $3\leq
i\leq k+1$, we subdivide the edge $(u^{i}_{2k+1-i},u^{i}_{2k+2-i})$ by adding
the vertex $b_{k+2-i}$ and the edges $(u^{i}_{2k+1-i},b_{k+2-i})$ and
$(b_{k+2-i},u^{i}_{2k+2-i})$.

  * •

We subdivide the edge $(s_{k+2},u^{k+1}_{1})$ by adding the vertex $c_{1}$ and
the edges $(s_{k+2},c_{1})$ and $(c_{1},u^{k+1}_{1})$; and for every $k+3\leq
i\leq 2k+1$, we subdivide the edge $(u^{k+2}_{i-k-2},u^{k+1}_{i-k-2})$ by
adding the vertex $c_{i-k-1}$ and the edges $(u^{k+2}_{i-k-2},c_{i-k-1})$ and
$(c_{i-k-1},u^{k+1}_{i-k-2})$.

  * •

For every $k+2\leq i\leq 2k+1$, we subdivide the edge
$(u^{2}_{i-k-2},u^{1}_{i-k-2})$ by adding the vertex $d_{i-k-1}$ and the edges
$(u^{2}_{i-k-2},d_{i-k-1})$ and $(d_{i-k-1},u^{1}_{i-k-2})$.

  * •

For every $1\leq i,j\leq k$, we replace the vertex $u^{j+1}_{k-j+i}$ with a
copy of the graph $G(S_{i,k+1-j})$ and add the necessary edges so that the
subgraph of $G$ induced by $\\{a_{i},b_{i},c_{i},d_{i}~{}|~{}1\leq i\leq
k\\}\cup\bigcup_{1\leq i,j\leq k}V(G(S_{i,j}))$ is isomorphic to
$MG(\mathcal{S})$ (and has the same edge-weight function).

The weight of each edge outside the copy of the main gadget $MG(\mathcal{S})$
is set to 0. This concludes the construction of $G(\mathcal{S})$. We set
$T=\\{s_{i},t_{i}~{}|~{}i\in[2k+1]\\}$ and let the demand graph $D$ be the
corresponding
$(\\{s_{i}~{}|~{}i\in[2k+1]\\},\\{t_{i}~{}|~{}i\in[2k+1]\\})$-biclique. Lemma
5.29 for $\ell=1$ then follows from Lemma 5.26 and the lemma below.

$s_{1}$$s_{2}$$s_{3}$$s_{4}$$s_{5}$$s_{6}$$s_{7}$$t_{1}$$t_{2}$$t_{3}$$t_{4}$$t_{5}$$t_{6}$$t_{7}$$a_{3}$$a_{2}$$a_{1}$$b_{3}$$b_{2}$$b_{1}$$d_{1}$$d_{2}$$d_{3}$$c_{1}$$c_{2}$$c_{3}$
Figure 18: An illustration of the reduction from $k\times k$-Grid Tiling to
Planar $\mathcal{C}_{1}$-Steiner Network with $k=3$ (the red vertices are the
terminals and the dashed blue square together with the grey boxes represent
the main gadget).

######  Lemma 5.31.

The (edge-weighted) Planar $\mathcal{C}_{1}$-Steiner Network instance
$(G(\mathcal{S}),T,D)$ has a solution of weight at most $B^{*}-k^{2}$ if and
only if the (edge-weighted) Planar $M$-Steiner Network instance
$(MG(\mathcal{S}),I,M)$ has a solution of weight at most $B^{*}-k^{2}$.

###### Proof.

If $E$ is a solution of $(MG(\mathcal{S}),I,M)$ of weight at most
$B^{*}-k^{2}$ then it is not difficult to see that
$E\cup(E(G(\mathcal{S}))\setminus E(MG(\mathcal{S})))$ is a solution of
$(G(\mathcal{S}),T,D)$ of weight at most $B^{*}-k^{2}$. Conversely, let $E$ be
a solution of $(G(\mathcal{S}),T,D)$ of weight at most $B^{*}-k^{2}$. Since
for every $2\leq i\leq k+1$, there is a unique path in $H$ from $s_{i}$ to
$t_{i}$, namely $P_{i,i}$, and for every $k+2\leq i\leq 2k+1$, there is a
unique path in $H$ from $s_{i}$ to $t_{i+1}$, namely $P_{i,i+1}$, the
restriction $E^{\prime}$ of $E$ to $MG(\mathcal{S})$ is a solution of
$(MG(\mathcal{S}),I,M)$; and since every edge in $E(G(\mathcal{S}))\setminus
E(MG(\mathcal{S}))$ has weight 0, the weight of $E^{\prime}$ is that of $E$,
that is, $E^{\prime}$ has weight at most $B^{*}-k^{2}$. ∎

## References

  * [1] M. Bateni, C. Chekuri, A. Ene, M. T. Hajiaghayi, N. Korula, and D. Marx, Prize-collecting Steiner Problems on Planar Graphs, in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011, 2011, pp. 1028–1049.
  * [2] M. Bateni, M. T. Hajiaghayi, and D. Marx, Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth, J. ACM, 58 (2011), pp. 21:1–21:37.
  * [3] P. Berman, A. Bhattacharyya, K. Makarychev, S. Raskhodnikova, and G. Yaroslavtsev, Approximation algorithms for spanner problems and directed steiner forest, Inf. Comput., 222 (2013), pp. 93–107.
  * [4] A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, Fourier meets möbius: fast subset convolution, in Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, D. S. Johnson and U. Feige, eds., ACM, 2007, pp. 67–74.
  * [5] M. Charikar, C. Chekuri, T. Cheung, Z. Dai, A. Goel, S. Guha, and M. Li, Approximation Algorithms for Directed Steiner Problems, J. Algorithms, 33 (1999), pp. 73–91.
  * [6] R. Chitnis, H. Esfandiari, M. T. Hajiaghayi, R. Khandekar, G. Kortsarz, and S. Seddighin, A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands, Algorithmica, 77 (2017), pp. 1216–1239.
  * [7] R. Chitnis, A. E. Feldmann, and P. Manurangsi, Parameterized Approximation Algorithms for Bidirected Steiner Network Problems, in 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, 2018, pp. 20:1–20:16.
  * [8] R. H. Chitnis, A. E. Feldmann, M. T. Hajiaghayi, and D. Marx, Tight bounds for planar strongly connected steiner subgraph with fixed number of terminals (and extensions), SIAM J. Comput., 49 (2020), pp. 318–364.
  * [9] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized Algorithms, Springer Publishing Company, Incorporated, 1st ed., 2015.
  * [10] É. C. de Verdière, Multicuts in planar and bounded-genus graphs with bounded number of terminals, Algorithmica, 78 (2017), pp. 1206–1224.
  * [11] P. Dvorák, A. E. Feldmann, D. Knop, T. Masarík, T. Toufar, and P. Veselý, Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, in 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, 2018, pp. 26:1–26:15.
  * [12] E. Eiben, D. Knop, F. Panolan, and O. Suchý, Complexity of the Steiner Network Problem with Respect to the Number of Terminals, in 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), R. Niedermeier and C. Paul, eds., vol. 126 of Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, 2019, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 25:1–25:17.
  * [13] J. Feldman and M. Ruhl, The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals, SIAM J. Comput., 36 (2006), pp. 543–561.
  * [14] A. E. Feldmann and D. Marx, The complexity landscape of fixed-parameter directed steiner network problems, in 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, vol. 55 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, pp. 27:1–27:14.
  * [15] F. V. Fomin, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Subexponential parameterized algorithms for planar and apex-minor-free graphs via low treewidth pattern covering, in IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, I. Dinur, ed., IEEE Computer Society, 2016, pp. 515–524.
  * [16] J. Guo, R. Niedermeier, and O. Suchý, Parameterized complexity of arc-weighted directed steiner problems, SIAM J. Discrete Math., 25 (2011), pp. 583–599.
  * [17] S. L. Hakimi, Steiner’s problem in graphs and its implications, Networks, 1 (1971), pp. 113–133.
  * [18] R. M. Karp, Reducibility Among Combinatorial Problems, in Proceedings of a Symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, 1972, pp. 85–103.
  * [19] P. N. Klein and D. Marx, Solving planar k -terminal cut in $o(n^{c \sqrt{k}})$ time, in Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, A. Czumaj, K. Mehlhorn, A. M. Pitts, and R. Wattenhofer, eds., vol. 7391 of Lecture Notes in Computer Science, Springer, 2012, pp. 569–580.
  * [20] , A subexponential parameterized algorithm for subset TSP on planar graphs, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, C. Chekuri, ed., SIAM, 2014, pp. 1812–1830.
  * [21] A. Levin, Algorithm for the shortest connection of a group of graph vertices, Soviet Math. Dokl., 12 (1971), pp. 1477–1481.
  * [22] C. Li, S. T. McCormick, and D. Simchi-Levi, The point-to-point delivery and connection problems: complexity and algorithms, Discrete Applied Mathematics, 36 (1992), pp. 267–292.
  * [23] D. Lokshtanov, S. Saurabh, and M. Wahlström, Subexponential parameterized odd cycle transversal on planar graphs, in IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2012, December 15-17, 2012, Hyderabad, India, D. D’Souza, T. Kavitha, and J. Radhakrishnan, eds., vol. 18 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 424–434.
  * [24] D. Marx, On the Optimality of Planar and Geometric Approximation Schemes, in 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, 2007, pp. 338–348.
  * [25] , A tight lower bound for planar multiway cut with fixed number of terminals, in Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, A. Czumaj, K. Mehlhorn, A. M. Pitts, and R. Wattenhofer, eds., vol. 7391 of Lecture Notes in Computer Science, Springer, 2012, pp. 677–688.
  * [26] D. Marx and M. Pilipczuk, Optimal parameterized algorithms for planar facility location problems using voronoi diagrams, ACM Trans. Algorithms, 18 (2022), pp. 13:1–13:64.
  * [27] D. Marx, M. Pilipczuk, and M. Pilipczuk, On subexponential parameterized algorithms for steiner tree and directed subset TSP on planar graphs, in 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, M. Thorup, ed., IEEE Computer Society, 2018, pp. 474–484.
  * [28] M. Natu and S. Fang, The Point-to-point Connection Problem - Analysis and Algorithms, Discrete Applied Mathematics, 78 (1997), pp. 207–226.
  * [29] J. Nederlof, Detecting and counting small patterns in planar graphs in subexponential parameterized time, in Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, and J. Chuzhoy, eds., ACM, 2020, pp. 1293–1306.
  * [30] S. Ramanathan, Multicast tree generation in networks with asymmetric links, IEEE/ACM Trans. Netw., 4 (1996), pp. 558–568.
  * [31] N. Robertson, P. D. Seymour, and R. Thomas, Quickly excluding a planar graph, J. Comb. Theory, Ser. B, 62 (1994), pp. 323–348.
  * [32] H. F. Salama, D. S. Reeves, and Y. Viniotis, Evaluation of Multicast Routing Algorithms for Real-Time Communication on High-Speed Networks, IEEE Journal on Selected Areas in Communications, 15 (1997), pp. 332–345.
  * [33] P. Winter, Steiner problem in networks: A survey, Networks, 17 (1987), pp. 129–167.