Parameterized Maximum Node-Disjoint Paths

In the present paper we thoroughly investigate the complexity of MaxNDP under different parameterizations, and determine exactly when it is rendered tractable, by additionally employing the use of approximation in the process (see Figure 1 for a synopsis of our results). We start by showing that the problem is FPT parameterized by the number of vertices of an optimal solution by developing a simple algorithm that makes use of the color-coding technique introduced by Alon, Yuster, and Zwick [2]. We then prove that, albeit simple, this algorithm is in fact sufficient to pinpoint exactly when the problem is fixed-parameter tractable: utilizing a variety of structural observations, we develop FPT algorithms for various parameterizations (most involving $\mathrm{\ell }$ as a parameter) at the core of all of which lies the previously mentioned algorithm. Along the way we also develop an FPT algorithm for the parameterization by the feedback edge number. These positive results, in conjunction with the hardness results of [14, 28], clearly showcase the transition of the problem from FPT to W[1]-hard for its various parameterizations (with the exception of cluster vertex deletion number, where it is unknown whether the problem is W[1]-hard).

Given the apparent hardness of the problem, we move on to consider it under the perspective of parameterized approximation (see [15] for a survey of the area). Here, we observe that utilizing the previously developed FPT algorithms when $\mathrm{\ell }$ is also a parameter, can in fact lead to efficient FPT approximation schemes (FPT-ASes) in case of solely structural parameterizations of the problem, when parameterized by the cluster vertex deletion number, the vertex integrity, or the tree-depth of the input graph; in the latter two cases the problem is known to be W[1]-hard [14].

The FPT approximation schemes developed indicate that the W[1]-hardness can, in some cases, be overcome via the use of approximation. Given the relationship of our studied parameters as well as the FPT-AS for tree-depth, a natural question is whether an analogous approximation scheme exists for the parameterization by pathwidth as well. Notice that the W[1]-hardness by $\mathrm{\ell }$ plus the pathwidth pw and the feedback vertex number fvs of the input graph already excludes the existence of an approximation scheme of running time $f(\text{pw},\text{fvs},\epsilon )n^{𝒪(1)}$, yet one of time $f(\text{pw},\text{fvs},\epsilon )n^{g(\epsilon )}$ remains possible. Our next result is to exclude the existence of such a scheme under the Parameterized Inapproximability Hypothesis [26], which was recently proved to hold under the ETH [17], and thus precisely determine the parameter border where the problem transitions from “hard but approximable” to “inapproximable”. By slightly modifying our reduction, we subsequently show that the problem is XNLP-complete when parameterized solely by the pathwidth of the input graph, where XNLP is a complexity class that has been recently brought forth by Bodlaender, Groenland, Nederlof, and Swennenhuis [3], and such a result implies W[$t$]-hardness for all integers $t\ge 1$.

Lastly, we proceed to a more fine-grained examination of the hardness of MaxNDP when parameterized by the tree-depth of the input graph. Standard dynamic programming techniques can be used to obtain an $n^{𝒪(\text{tw})}$ algorithm, while previous work by Ene, Mnich, Pilipczuk, and Risteski [14] implies that the problem cannot be solved in time $n^{o(\sqrt{\text{td}})}$ under the ETH for graphs of tree-depth td, thereby leaving hope for an $n^{o(\text{td})}$ algorithm. We revisit said proof, and by employing a recursive structure introduced by Lampis and Vasilakis [23] we bridge this gap and prove that MaxNDP cannot be solved in time $n^{o(\text{td})}$ under the ETH, rendering the $n^{𝒪(\text{tw})}$ algorithm optimal even for this much smaller class of graphs.

Even though MaxNDP has been well-studied under the scope of approximation algorithms, the 20 years old algorithm of ratio $𝒪(\sqrt{n})$ due to Kolliopoulos and Stein [21] remains the state of the art in general graphs. This has been improved in the case of grid [6] and planar graphs [7], resulting in approximation ratios $\widetilde{𝒪}(n^{1/4})$ and $\widetilde{𝒪}(n^{9/19})$ respectively, where standard $\widetilde{𝒪}$ notation is used to hide polylogarithmic terms. For graphs of pathwidth pw, Ene, Mnich, Pilipczuk, and Risteski [14] have presented an algorithm of approximation ratio $𝒪({\text{pw}}^3)$. Regarding inapproximalibity results, after a series of works, Chuzhoy, Kim, and Nimavat [9, 10] have shown that the problem cannot be approximated in polynomial time (i) within a factor of $2^{𝒪({\log }^{1-\epsilon }n)}$ for any constant $\epsilon$, assuming $\text{NP}⊈\text{DTIME}(n^{\mathrm{polylog}n})$, and (ii) within a factor of $n^{𝒪(1/{(\log \log n)}^2)}$, assuming that there exists some constant $\delta >0$ such that $\text{NP}⊈\text{DTIME}(2^{n^{\delta }})$.

The problem has been also studied under a parameterized complexity perspective. As already noted, it is trivially FPT by $k$ by a simple reduction to $2^k$ instances of Node-Disjoint Paths, which is well-known to be FPT by the number of demands. On the other hand, Marx and Wollan [28] have shown that it becomes W[1]-hard when parameterized by $\mathrm{\ell }+\text{tw}$, with a closer look into their proof revealing that their result extends to the parameterization by $\mathrm{\ell }+\text{pw}+\text{fvs}$. Regarding structural parameterizations, Ene, Mnich, Pilipczuk, and Risteski [14] have proved that the problem is W[1]-hard when parameterized by the tree-depth of the input graph; in fact, their proof extends to graphs of bounded vertex integrity plus feedback vertex number. Fleszar, Mnich, and Spoerhase [16] have proposed an algorithm of running time ${(k+\text{fvs})}^{𝒪(\text{fvs})}{n}^{𝒪(1)}$ as an alternative to the $2^k{\text{fvs}}^{𝒪(\text{fvs})}{n}^{𝒪(1)}$ algorithm obtained by reducing the instance to Node-Disjoint Paths and then using Scheffler’s algorithm [32].

In Section 2 we discuss the general preliminaries. Subsequently, in Section 3 we present various tractability results, followed by the inapproximability result for pathwidth in Section 4. Moving on, in Sections 5 and 6 we present the XNLP-completeness and the refined W[1]-hardness of the problem, when parameterized by the pathwidth and the tree-depth of the input graph respectively. Lastly, in Section 7 we present the conclusion as well as some directions for future research. Proofs of statements marked with $(\star )$ are omitted and can be found in the full version.

Let $ℐ=(G,k)$ be an instance of Multicolored Densest $k$-Subgraph, and recall that we assume that $G$ is given to us partitioned into $k$ independent sets $V_1,\mathrm{\dots },V_k$, where $V_i=\{v_1^i,\mathrm{\dots },v_n^i\}$. Moreover, let $E^{i_1,i_2}\subseteq E(G)$ denote the edges of $G$ with one endpoint in $V_{i_1}$ and the other in $V_{i_2}$. For every color class $i\in [k]$, let $s_i=|\{j\in [k]:E^{i,j}\ne \mathrm{\varnothing }\}|$, and assume without loss of generality that $1\le s_i\le 3$. Set $\sigma ={\sum }_{i\in [k]}{s}_i/2$, and notice that $\frac{k}{2}\le \sigma \le \frac{3k}{2}$. Let $\mathrm{OPT}(ℐ)\le \sigma$ denote the optimal value of instance $ℐ$, i.e., the maximum number of edges among the induced subgraphs of $G$ that contain one vertex per color class $V_i$.

We will construct in polynomial time an instance $𝒥=(H,ℳ)$ of MaxNDP, where $\text{pw}(H)=𝒪(k)$, $\text{fvs}(H)=𝒪(k)$, and $|V(H)|=n^{𝒪(1)}$, while $ℳ\subseteq \left(\genfrac{}{}{0pt}{}{V(H)}{2}\right)$ is a set of demands. Moreover, it will hold that $\mathrm{OPT}(𝒥)\le \mathrm{\ell }$, where $\mathrm{OPT}(𝒥)$ denotes the optimal value of instance $𝒥$, and $\mathrm{\ell }=2k+\sigma$. We will present a reduction such that (i) if $\mathrm{OPT}(ℐ)=\sigma$, then $\mathrm{OPT}(𝒥)=\mathrm{\ell }$, and (ii) if , then , for constants $c$ and $c^{\prime }$ where and $c^{\prime }=\frac{9+c}{10}$.

For an independent set $V_i$, we construct the choice gadget ${\widehat{C}}_i$ in the following way. First, for $p\in [n]$, we construct paths on vertex sets ${\widehat{P}}_p^i=\{w_q^{i,p}:q\in [3]\}$, as well as paths ${\widehat{R}}_p^i$ on $3$ unnamed vertices each. Then, we introduce vertices $v_p^i$ and $u_p^i$, for $p\in [n+1]$. Next, we add edges $\{u_{n+1}^i,v_1^i\}$ and $\{v_{n+1}^i,u_1^i\}$. Lastly, for $p\in [n]$, we add edges $\{v_p^i,w_1^{i,p}\}$ and $\{w_3^{i,p},v_{p+1}^i\}$, as well as an edge from $u_p^i$ to one endpoint of ${\widehat{R}}_p^i$, and an edge from $u_{p+1}^i$ to the other endpoint of ${\widehat{R}}_p^i$. See Figure 2 for an illustration. Subsequently, add to $ℳ$ all pairs $(v_p^i,u_{p+1}^i)$ and $(v_p^i,u_{p-1}^i)$ for $p\in [2,n]$, as well as the pairs $(v_1^i,u_2^i)$ and $(v_{n+1}^i,u_n^i)$. Let ${ℳ}_c\subseteq ℳ$ denote all such pairs added to $ℳ$ in this step of the construction. Intuitively, we will consider a one-to-one mapping between the vertex $v_p^i$ of $V_i$ being chosen and the vertices of ${\widehat{P}}_p^i$ not being used to route any of the demands in ${ℳ}_c$.

Let $E^{i,j}\ne \mathrm{\varnothing }$. Introduce an adjacency vertex $e_{i,j}$, and add edges $\{e_{i,j},w_x^{i,p}\}$ and $\{e_{i,j},w_y^{j,p}\}$ where $p\in [n]$, and $x,y\in [3]$ such that no other adjacency vertex is adjacent to them (since $s_i\le 3$ for all $i\in [k]$, there always exist such $x$ and $y$). If $e=\{v_p^i,v_q^j\}\in E^{i,j}$, then add the pair $(w_x^{i,p},w_y^{j,q})$ in $ℳ$. Notice that all adjacency vertices have disjoint neighborhoods, and let $F\subseteq V(H)$ be the set of all adjacency vertices, where $|F|=\sigma$.

This concludes the construction of the instance $𝒥$. Notice that $H-F$ is a collection of $k$ choice gadgets, each of which is a cycle. Consequently, the graph obtained from $H-F$ by deleting a vertex per choice gadget is a collection of paths, thus both $\text{pw}(H)$ and $\text{fvs}(H)$ are at most $𝒪(k)$.

We first prove that if $\mathrm{OPT}(ℐ)=\sigma$, then $\mathrm{OPT}(𝒥)=\mathrm{\ell }$. Consider a function $h:[k]\to [n]$ such that $G[𝒱]$ has $\sigma$ edges, where $𝒱=\{v_{h(i)}^i\in V_i:i\in [k]\}\subseteq V(G)$. We construct a family of $\mathrm{\ell }$ vertex-disjoint paths as follows. First, for every $i\in [k]$, we route two demands in ${\widehat{C}}_i$. In particular, we route the demands $(v_{h(i)}^i,u_{h(i)+1}^i)$ as well as $(v_{h(i)+1}^i,u_{h(i)}^i)$, using the vertices of the shortest path of ${\widehat{C}}_i$ in each case. Note that in this step we have created $2k$ vertex-disjoint paths connecting terminal pairs belonging to ${ℳ}_c$, and in every gadget ${\widehat{C}}_i$ the only unused vertices are those of ${\widehat{P}}_{h(i)}^i$ and ${\widehat{R}}_{h(i)}^i$. Then, consider the adjacency vertex $e_{i,j}$, where $i,j\in [k]$. Route the demand $(w_x^{i,h(i)},w_y^{j,h(j)})$ via $e_{i,j}$, since both endpoints of the demand are its neighbors and have not been used in any path so far, for some $x,y\in [3]$. Such a demand indeed exists in $ℳ$, since $\{v_{h(i)}^i,v_{h(j)}^j\}\in E^{i,j}$; if that were not the case then $G[𝒱]$ has less than $\sigma$ edges. This procedure results in $\sigma$ additional demands being routed. Notice that since the neighborhoods of all adjacency vertices are disjoint, the $\mathrm{\ell }$ resulting paths are indeed vertex-disjoint.

It remains to prove that if , then (or its contrapositive, as we will do in actuality). We start with Claim 7.

Let $N=3n+(n+1)$ and notice that ${\widehat{C}}_i$ is a $C_{2N}$, thus there are exactly $2$ simple paths connecting any pair of its vertices. Moreover, the number of vertices in any simple path between $v_p^i$ and $u_p^i$, including said endpoints, is $N+1$. Consequently, to route any demand with both endpoints in ${\widehat{C}}_i$, either $N+1-4$ or $N+1+4$ vertices are used. In case more than $2$ demands are routed, at least $3(N+1-4)=3N-9$ vertices are used, which is a contradiction since ${\widehat{C}}_i$ consists of $2N$ vertices.

Assume that exactly $2$ demands are routed. Moreover, assume that a demand is routed using $N+1+4$ vertices. Then, both routed demands use at least $(N+1+4)+(N+1-4)>2N$ vertices, which is a contradiction. Therefore, both demands that are routed in ${\widehat{C}}_i$ use the shortest path connecting their endpoints.

Let $(v_p^i,u_q^i)$ and $(v_{p^{\prime }}^i,u_{q^{\prime }}^i)$ denote the demands routed, where and $p\in [n]$. It holds that $q=p+1$, since otherwise $q=p-1$, and $v_{p^{\prime }}^i$ belongs to the shortest path connecting $(v_p^i,u_q^i)$, a contradiction. Symmetrically, it follows that $q^{\prime }=p^{\prime }-1$. Lastly, it holds that $q>q^{\prime }$, since otherwise $u_{q^{\prime }}^i$ belongs to the shortest path connecting $(v_p^i,u_q^i)$. Consequently, it follows that $q>q^{\prime }\iff p+2>p^{\prime }$, which implies that , i.e., $p^{\prime }=p+1$. In that case, the only unused vertices are those of ${\widehat{P}}_p^i$ and ${\widehat{R}}_p^i$.

Notice that $H-F$ is a collection of $k$ choice gadgets. Since in each such gadget at most $2$ demands can be routed, it follows that $\mathrm{OPT}(𝒥)\le 2k+|F|=2k+\sigma =\mathrm{\ell }$. $\mathrm{⊲}$

We now move on to prove that if $\mathrm{OPT}(𝒥)\ge c^{\prime }\cdot \mathrm{\ell }$, then $\mathrm{OPT}(ℐ)\ge c\cdot \sigma$. Let $𝒫$ denote a collection of $\mathrm{OPT}(𝒥)$ vertex-disjoint paths of $H$ routing demands of $ℳ$, where $\mathrm{OPT}(𝒥)\ge c^{\prime }\cdot \mathrm{\ell }$. Additionally, let ${𝒞}_j^{𝒫}$ contain the choice gadgets ${\widehat{C}}_i$ such that there exist exactly $j$ paths in $𝒫$ that route demands in the graph induced by ${\widehat{C}}_i$, for $j\in [0,2]$. Notice that $({𝒞}_0^{𝒫},{𝒞}_1^{𝒫},{𝒞}_2^{𝒫})$ defines a partition of the choice gadgets due to Claim 7. Moreover, let ${𝒫}^F\subseteq 𝒫$ be comprised of the paths of $𝒫$ that contain vertices of $F$. We will say that a path $P\in {𝒫}^F$ intersects ${\widehat{C}}_i$ if $P$ contains a vertex of ${\widehat{C}}_i$. We define the loss of a solution $𝒫$ to be $L_{𝒫}=\mathrm{\ell }-|𝒫|$. Notice that due to Claim 7 it holds that $L_{𝒫}=2|{𝒞}_0^{𝒫}|+|{𝒞}_1^{𝒫}|+(|F|-|{𝒫}^F|)$.

It holds that $\mathrm{OPT}(𝒥)=|𝒫|=\mathrm{\ell }-L_{𝒫}\ge c^{\prime }\cdot \mathrm{\ell }=\mathrm{\ell }-(1-c^{\prime })\cdot \mathrm{\ell }$, thus it follows that $L_{𝒫}\le (1-c^{\prime })\cdot \mathrm{\ell }$. Construct a new solution ${𝒫}^{\prime }$ in the following way: for every ${\widehat{C}}_i\in {𝒞}_0^{𝒫}\cup {𝒞}_1^{𝒫}$, route two demands of ${ℳ}_c$ such that there exist two vertex-disjoint paths using only vertices of ${\widehat{C}}_i$. Afterwards, remove any paths of ${𝒫}^F$ that are not vertex-disjoint with those. There are at most 3 vertices of $F$ adjacent to vertices of ${\widehat{C}}_i$, and by choosing the routed demands of ${\widehat{C}}_i$ in such a way that at least one of those vertices of ${\widehat{C}}_i$ remains unused, it follows that at most $2$ paths of ${𝒫}^F$ intersect ${\widehat{C}}_i$. Thus it follows that $L_{{𝒫}^{\prime }}\le (|F|-|{𝒫}^F|)+2(|{𝒞}_0^{𝒫}|+|{𝒞}_1^{𝒫}|)\le 2L_{𝒫}$, therefore $|{𝒫}^{\prime }|=\mathrm{\ell }-L_{{𝒫}^{\prime }}\ge \mathrm{\ell }-2L_{𝒫}$. Furthermore, notice that since for all $i\in [k]$ it holds that ${\widehat{C}}_i\in {𝒞}_2^{{𝒫}^{\prime }}$, due to Claim 7 it follows that only the vertices of ${\widehat{P}}_{h(i)}^i$ and ${\widehat{R}}_{h(i)}^i$ remain unused by the paths of ${𝒫}^{\prime }$ that route demands in ${ℳ}_c$, for some function $h:[k]\to [n]$. Consequently, for any routed demand $(w_x^{i,p},w_y^{j,q})\in ℳ\setminus {ℳ}_c$, it holds that $p=h(i)$ and $q=h(j)$.

Let $𝒱=\{v_{h(i)}^i:i\in [k]\}$, and notice that $|𝒱\cap V_i|=1$ for all $i\in [k]$. Let $A=|E(G[𝒱])|$ denote the number of edges present in the subgraph induced by $𝒱$. We will prove that $A\ge c\cdot \sigma$, in which case it follows that $\mathrm{OPT}(ℐ)\ge c\cdot \sigma$. Notice that $A\ge \mathrm{\ell }-2L_{𝒫}-2k=\sigma -2L_{𝒫}$, since this is the number of routed demands in $ℳ\setminus {ℳ}_c$ by ${𝒫}^{\prime }$, while $(w_x^{i,h(i)},w_y^{j,h(j)})\in ℳ$ implies that $\{v_{h(i)}^i,v_{h(j)}^j\}\in E^{i,j}$.

It suffices to prove that $\sigma -2L_{𝒫}\ge c\cdot \sigma$. Since $\sigma -2L_{𝒫}\ge \sigma -2(1-c^{\prime })\cdot \mathrm{\ell }$, we will prove $\sigma -2(1-c^{\prime })\cdot \mathrm{\ell }\ge c\cdot \sigma$ instead, which is equivalent to $c^{\prime }\ge 1+\frac{\sigma }{2\mathrm{\ell }}(c-1)$. Since and $\frac{\sigma }{2\mathrm{\ell }}=\frac{1}{2}\cdot \frac{\sigma }{2k+\sigma }\ge \frac{1}{2}\cdot \frac{k/2}{2k+k/2}=\frac{1}{10}$, the statement holds for $c^{\prime }=1+\frac{1}{10}(c-1)=\frac{9+c}{10}$. $◀$

Let $(G,k)$ be an instance of $k$-Multicolored Clique, such that every vertex of $G$ has a self loop, i.e., $\{v,v\}\in E(G)$, for all $v\in V(G)$. Recall that we assume that $G$ is given to us partitioned into $k$ independent sets $V_1,\mathrm{\dots },V_k$, where $V_i=\{v_1^i,\mathrm{\dots },v_n^i\}$. Assume without loss of generality that $k=2^z$, for some $z\in \mathbb{N}$ (one can do so by adding dummy independent sets connected to all the other vertices of the graph). Moreover, let $E^{i_1,i_2}\subseteq E(G)$ denote the edges of $G$ with one endpoint in $V_{i_1}$ and the other in $V_{i_2}$. We will construct in polynomial time an equivalent instance $(H,ℳ,\mathrm{\ell })$ of MaxNDP, where $H$ is a graph of tree-depth $\text{td}(H)=𝒪(k)$, feedback vertex number $\text{fvs}(H)=𝒪(k^2)$, and size $|V(H)|=n^{𝒪(1)}$, $ℳ\subseteq \left(\genfrac{}{}{0pt}{}{V(H)}{2}\right)$ is a set of demands, and $\mathrm{\ell }$ is an integer, such that $G$ has a $k$-clique if and only if at least $\mathrm{\ell }$ demands of $ℳ$ can be routed in $H$.

For an independent set $V_i$, we construct the choice gadget ${\widehat{C}}_i$ as depicted in Figure 3(a). We first construct paths on vertex sets ${\widehat{P}}_j^i=\{v_1^{i,j},v_2^{i,j},v_3^{i,j}\}$, where $j\in [n]$. Afterwards, for every $j\in [2,n]$, we introduce vertices ${\alpha }_j^i$ and ${\beta }_j^i$, connecting them with $v_1^{i,1},v_1^{i,j}$ and $v_3^{i,1},v_3^{i,j}$ respectively. Moreover, we add the pair $({\alpha }_j^i,{\beta }_j^i)$ to $ℳ$. Intuitively, we will consider a one-to-one mapping between the vertex $v_j^i$ of $V_i$ belonging to a supposed $k$-clique of $G$ and the vertices of ${\widehat{P}}_j^i$ not being used to route any of the demands added in this step.

Given two instances ${ℐ}_1$, ${ℐ}_2$ of a choice gadget ${\widehat{C}}_i$, when we say that we add a copy gadget $({ℐ}_1,{ℐ}_2,t)$, where $t\in \{1,2\}$, we introduce a copy vertex $g$, connect it with all vertices $v_{t+1}^{i,j}$ of ${ℐ}_1$ and all vertices $v_1^{i,j}$ of ${ℐ}_2$ for $j\in [n]$ and add all the pairs $(v_{t+1}^{i,j},v_1^{i,j})$ to $ℳ$.

Let $i_1,i_2,i_1^{\prime },i_2^{\prime }\in [k]$. For $i_1\le i_2$ and $i_1^{\prime }\le i_2^{\prime }$, we define the adjacency gadget³³3For some high-level intuition regarding the adjacency gadgets, we refer the reader to [23, Section 4]. $\widehat{A}(i_1,i_2,i_1^{\prime },i_2^{\prime })$ as follows:

• $\mathrm{■}$

  Consider first the case when $i_1=i_2=i$ and $i_1^{\prime }=i_2^{\prime }=i^{\prime }$. Let the adjacency gadget contain instances of the choice gadgets ${\widehat{C}}_i$ and ${\widehat{C}}_{i^{\prime }}$, as well as a validation vertex $m_{i,i^{\prime }}$. Add edges between $m_{i,i^{\prime }}$ and all vertices $v_2^{i,j}$ and $v_2^{i^{\prime },j}$ for $j\in [n]$. If $e=\{v_j^i,v_{j^{\prime }}^{i^{\prime }}\}\in E^{i,i^{\prime }}$, then add the pair $(v_2^{i,j},v_2^{i^{\prime },j^{\prime }})$ to $ℳ$.

• $\mathrm{■}$

  Now consider the case when and . Then, let $\widehat{A}(i_1,i_2,i_1^{\prime },i_2^{\prime })$ contain instances of choice gadgets ${\widehat{C}}_i$ and ${\widehat{C}}_{i^{\prime }}$, where $i\in [i_1,i_2]$ and $i^{\prime }\in [i_1^{\prime },i_2^{\prime }]$, which we will refer to as the original choice gadgets of $\widehat{A}(i_1,i_2,i_1^{\prime },i_2^{\prime })$, as well as the adjacency gadgets

  • –

    $\widehat{A}(i_1,\lfloor \frac{i_1+i_2}{2}\rfloor ,i_1^{\prime },\lfloor \frac{i_1^{\prime }+i_2^{\prime }}{2}\rfloor )$,

  • –

    $\widehat{A}(i_1,\lfloor \frac{i_1+i_2}{2}\rfloor ,\lceil \frac{i_1^{\prime }+i_2^{\prime }}{2}\rceil ,i_2^{\prime })$,

  • –

    $\widehat{A}(\lceil \frac{i_1+i_2}{2}\rceil ,i_2,i_1^{\prime },\lfloor \frac{i_1^{\prime }+i_2^{\prime }}{2}\rfloor )$,

  • –

    $\widehat{A}(\lceil \frac{i_1+i_2}{2}\rceil ,i_2,\lceil \frac{i_1^{\prime }+i_2^{\prime }}{2}\rceil ,i_2^{\prime })$.

  Lastly, let $ℐ$ denote the original choice gadget ${\widehat{C}}_p$, where $p\in [i_1,i_2]\cup [i_1^{\prime },i_2^{\prime }]$. Notice that there are exactly two instances of choice gadget ${\widehat{C}}_p$ appearing as original choice gadgets in the adjacency gadgets just introduced, say instances ${ℐ}_1$ and ${ℐ}_2$. Add copy gadgets $(ℐ,{ℐ}_1,1)$ and $(ℐ,{ℐ}_2,2)$.

Let graph $H$ be the adjacency gadget $\widehat{A}(1,k,1,k)$ and set $\mathrm{\ell }=\gamma \cdot (n-1)+\delta$, where $\gamma =2k(2k-1)$ and $\delta =5k^2-4k$. Notice that it holds that $|V(H)|={(n\cdot k)}^{𝒪(1)}$ as well as that all copy and validation vertices have disjoint neighborhoods. Additionally, let ${ℳ}_{\alpha \beta }$ denote the set of pairs of $ℳ$ of the form $({\alpha }_j^i,{\beta }_j^i)$. This concludes the construction of the instance $(H,ℳ,\mathrm{\ell })$.

Therefore, in polynomial time, we can construct a graph $H$, of tree-depth $\text{td}=𝒪(k)$ and $\text{fvs}=𝒪(k^2)$ due to Lemma 11, as well as a set of pairs $ℳ$, such that, due to Lemmas 12 and 13, deciding whether at least $\mathrm{\ell }$ pairs of $ℳ$ can be routed is equivalent to deciding whether $G$ has a $k$-clique. $◀$