Induced Disjoint Paths Without an Induced Minor

We reduce from the NP-complete problem Clause-Linked Planar E3-Occ 3-SAT, with variables $x_1,\mathrm{\dots },x_n$ and clauses $c_1,\mathrm{\dots },c_m$ where every clause $c_j$ is on two or three variables, each variable appears in exactly three clauses, and the variable-clause incidence graph is planar even when the cycle $c_1{c}_2\mathrm{\dots }{c}_m{c}_1$ is added. This problem has been proven NP-complete by Fellows et al. [9], even in a restricted form with some additional constraint on the clauses, but we will not need this restriction. To get a unique representation of the variable gadget, we assume that every variable has exactly three occurrences: two positive and one negative, or two negative and one positive. Indeed variables appearing only positively (or only negatively) can be set to true (or to false). We refer the reader to [30] for the complexity of variants of Planar 3-SAT.

We present the variable gadgets, clause gadgets, and variable-clause incidences, which assembled together form the graph $G$ input to Induced 2-Disjoint Paths. The reader can also refer to Figure 2 where these three elements are depicted.

For each variable $x_i$, we now describe the variable gadget $𝒢(x_i)$. For each clause $c_j$ containing $x_i$, we add to $𝒢(x_i)$ two vertices $w_j^N(x_i),w_j^S(x_i)$ if $x_i$ appears positively in $c_j$, and we add two vertices $w_j^N(\neg x_i),w_j^S(\neg x_i)$ if, instead, $x_i$ appears negatively in $c_j$. We finally turn $𝒢(x_i)$ into an induced biclique by adding every edge between pairs of vertices $w_j^d(x_i),w_{j^{\prime }}^{d^{\prime }}(\neg x_i)$ for $d,d^{\prime }\in \{N,S\}$ and $j,j^{\prime }$ may be equal or distinct. Observe that every variable gadget is isomorphic to the bipartite complete graph $K_{2,4}$.

We describe the clause gadget $𝒢(c_j)$ for each clause $c_j$. Let ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2,{\mathrm{\ell }}_3$ be the three literals of $c_j$ (or ${\mathrm{\ell }}_1,{\mathrm{\ell }}_2$ if $c_j$ is a 2-clause). The gadget $𝒢(c_j)$ has 16 vertices (or 12 if $c_j$ is a 2-clause): four entry points $u_j^N,u_j^S,u_{j+1}^N,u_{j+1}^S$, and four vertices $v_j^{NW}({\mathrm{\ell }}_a),v_j^{NE}({\mathrm{\ell }}_a),v_j^{SW}({\mathrm{\ell }}_a),v_j^{SE}({\mathrm{\ell }}_a)$ for each $a\in \{1,2,3\}$ (for each $a\in \{1,2\}$). We add an edge between a pair of vertices $v_j^d({\mathrm{\ell }}_a)$, $v_j^{d^{\prime }}({\mathrm{\ell }}_{a^{\prime }})$, with $d,d^{\prime }\in \{NW,NE,SW,SE\}$, whenever $a\ne a^{\prime }$. Thus those 12 vertices (8 vertices) form a tripartite complete graph $K_{4,4,4}$ (bipartite complete graph $K_{4,4}$). For every $d\in \{N,S\}$ and $a\in \{1,2,3\}$ ($a\in \{1,2\}$), we also add the six (four) edges $u_j^d{v}_j^{dW}({\mathrm{\ell }}_a)$, and the six (four) edges $v_j^{dE}({\mathrm{\ell }}_a)u_{j+1}^d$. This finishes the description of $𝒢(c_j)$. Note that $𝒢(c_j)$ and $𝒢(c_{j+1})$ share two vertices: $u_{j+1}^N$ and $u_{j+1}^S$.

Finally for every clause $c_j$ and literal $\mathrm{\ell }$ in $c_j$, and each $d\in \{N,S\}$, we add the edges $v_j^{dW}(\mathrm{\ell })w_j^d(\mathrm{\ell })$ and $w_j^{dE}(\mathrm{\ell })v_j^d(\mathrm{\ell })$.

The graph $G$, input of Induced 2-Disjoint Paths, is obtained by having a gadget for each variable and each clause, and adding the edges as described in the previous sentence. We set the first terminal pair to $u_1^N,u_{m+1}^N$ and the second terminal pair to $u_1^S,u_{m+1}^S$. This finishes the construction; see Figure 2.

The next two lemmas show the correctness of the reduction.

We fix a truth assignment ${\mathrm{\ell }}_1,\mathrm{\dots },{\mathrm{\ell }}_n$ of the variables satisfying $c_1\wedge \mathrm{\dots }\wedge c_m$, with ${\mathrm{\ell }}_i\in \{x_i,\neg x_i\}$ for every $i\in [n]$. For each clause $c_j$, we choose any literal $\mathrm{\ell }(c_j)$ of $c_j$ such that $\mathrm{\ell }(c_j)={\mathrm{\ell }}_i$ for some $i\in [n]$. For each $d\in \{N,S\}$, we build the path $P^d$:

Note that $P^N$ is a $u_1^N$–$u_{m+1}^N$ path in $G$, $P^S$ is a $u_1^S$–$u_{m+1}^S$ path, and $P^N,P^S$ are vertex-disjoint. We claim there is no chord between $P^N$ and $P^S$. This is essentially because

• $\mathrm{■}$

  within every $𝒢(c_j)$, $V(P^N)$ and $V(P^S)$ induce a $4K_2$ comprising four edges of $P^N\uplus P^S$,

• $\mathrm{■}$

  apart from edges incident to entry points, there is no edge between two clause gadgets,

• $\mathrm{■}$

  $P^N$ and $P^S$ enter each variable gadget on the same side of the induced biclique,

which concludes the proof of the claim. $\mathrm{⊲}$

Let $P^N,P^S$ be two mutually induced paths in $G$ such that $P^d$ is a $u_1^d$–$u_{m+1}^d$ path for each $d\in \{N,S\}$. We think of $P^d$ as going from $u_1^d$, its start, to $u_{m+1}^d$, its end. We first show the following invariant. For every $j\in [m]$, there exists a literal $\mathrm{\ell }$ of $c_j$ such that for each $d\in \{N,S\}$, the path $P^d$ goes from $u_j^d$ to $u_{j+1}^d$ via the 4-edge subpath $u_j^d,v_j^{dW}(\mathrm{\ell }),w_j^d(\mathrm{\ell }),v_j^{dE}(\mathrm{\ell }),u_{j+1}^d$.

Fix some $j\in [m]$, and assume that the invariant holds for every $j^{\prime }\in [j-1]$ (with $[0]=\mathrm{\varnothing }$). The vertex following $u_j^N$ along $P^N$ cannot be in $𝒢(c_{j-1})$ as either $j=1$ (and this gadget does not exist) or it would create a chord between $P^N$ and $P^S$, by the induction hypothesis. Thus it has to be $v_j^{NW}(\mathrm{\ell })$ for some literal $\mathrm{\ell }$ of $c_j$. To avoid a chord between $P^N$ and $P^S$, the vertex following $u_j^S$ along $P^S$ has to be $v_j^{SW}(\mathrm{\ell })$. Then the next vertex along $P^N$ (resp. $P^S$) has to be $w_j^N(\mathrm{\ell })$ (resp. $w_j^S(\mathrm{\ell })$). As the variable gadget of literal $\mathrm{\ell }$ is an induced biclique, the next vertices have to be back to the clause gadget $𝒢(c_j)$: $v_j^{NE}(\mathrm{\ell })$ along $P^N$, and $v_j^{SE}(\mathrm{\ell })$ along $P^S$. Finally the next vertices have to be $u_{j+1}^N$ along $P^N$, and $u_{j+1}^S$ along $P^S$. This completes the proof that the invariant holds for every $j\in [m]$.

Let $𝒜$ be the truth assignment setting $x_i$ to true if $P^N$ (resp. $P^S$) does not contain any vertex $w_j^N(\neg x_i)$ (resp. $w_j^S(\neg x_i)$), and to false otherwise. As $P^N,P^S$ are mutually induced, in the latter case $P^N$ (resp. $P^S$) does not contain any vertex $w_j^N(x_i)$ (resp. $w_j^S(x_i)$). Thus, for every clause $c_j$, the vertex $v_j^{NW}(\mathrm{\ell })\in P^N$ is such that literal $\mathrm{\ell }$ is satisfied by $𝒜$. Hence $𝒜$ is a satisfying assignment. $\mathrm{⊲}$

Observe that the invariant in the first paragraph of the proof of Claim 10 still holds under the weaker assumption that the endpoints of $P^N,P^S$ are in $\{u_{m+1}^N,u_{m+1}^S\}$ (but are unspecified). Therefore finding two mutually induced paths between $\{u_1^N,u_1^S\}$ and $\{u_{m+1}^N,u_{m+1}^S\}$ in $G$ (the induced flow problem) is equivalent to the induced linkage problem.

We now show that $G$ is as advertised by the theorem statement. We start by giving a string representation for $G$.

First, we draw a planar embedding $𝒫$ of the variable-clause incidence graph augmented with the cycle $c_1{c}_2\mathrm{\dots }{c}_m{c}_1$. We refer to one face delimited by this cycle as the upper face (drawn in the figures “above” the path $c_1{c}_2\mathrm{\dots }{c}_m$), and the other face as the lower face. Second, for every clause $c_j$, draw $𝒢(c_j)$, and the six (or four, if $c_j$ is a 2-clause) vertices in variable gadgets that are adjacent to $𝒢(c_j)$, as the intersection graph of strings such that

• $\mathrm{■}$

  the strings of $u_j^N,u_j^S,u_{j+1}^N,u_{j+1}^S$ protrude in the infinite face,¹¹1In all these items, the faces are those of the planar diagram of the string representation of $𝒢(c_j)$, except the upper and lower faces, which are defined above.

• $\mathrm{■}$

  as well as $w_j^N(\mathrm{\ell })$ (resp. $w_j^S(\mathrm{\ell })$) if $\mathrm{\ell }$ is a literal of $c_j$ whose variable is drawn in the upper face (resp. lower face) in $𝒫$,

• $\mathrm{■}$

  these strings appear along the infinite face in the order prescribed by $𝒫$, and

• $\mathrm{■}$

  for each literal $\mathrm{\ell }$ of $c_j$, there is a face that contains a substring of $w_j^N(\mathrm{\ell })$ and a substring of $w_j^S(\mathrm{\ell })$, one of which bounding the infinite face (as requested by the second item).

Such a string representation is given in Figure 3.

The figure illustrates the case when no three variables of the clause lie on the same face. However it is easy to mirror the green strings to draw the other case. For 2-clauses, one can simply remove four strings of the same color (red, blue, or green) from Figure 3.

At this point, the string representation of $G$ has all the desired edges (intersections) except for those of the $K_{2,4}$ in variable gadgets. It has no extra edge, due to the planarity of $𝒫$. Figure 4 finally shows how to edit the strings $w_{\bullet }^N(\bullet )$ and $w_{\bullet }^S(\bullet )$ to add these edges, without incurring any other edges.

After editing every string of the variable gadgets, we obtain a string representation for $G$. $\mathrm{⊲}$

We finally show the following property of $G$.

In the planar drawing $𝒫$ (see proof of Claim 11), replace every clause vertex by a path of length 16, and every variable vertex by a cycle of length 12, in such a way that the obtained graph $H$ is subcubic, still planar, and the variable-clause incidences are preserved. It is then easy to see that $G$ is a subgraph of $H^{16}$. $\mathrm{⊲}$

This finishes the proof of the main theorem. $◀$

We then derive the following.

See 2

By Theorem 6, planar graphs have bounded twin-width. By Theorem 7, constant powers of planar graphs have bounded twin-width. Constant powers of bounded-degree graphs have themselves bounded maximum degree, and in particular, no $K_{t,t}$ subgraph for some constant $t$. Thus by Theorem 8, the graphs produced by the previous reduction have bounded twin-width. Besides, they are bounded-degree string graphs.

The previous reduction also works for Induced Disjoint $S$–$T$ Paths as the invariant shown in Claim 10 can be established in the same way under the weaker assumption that $G$ admits two mutually induced paths between $u_1^N$ and $\{u_{m+1}^N,u_{m+1}^S\}$, and between $u_1^S$ and $\{u_{m+1}^N,u_{m+1}^S\}$, respectively. In particular, the invariant shows that (if there is at least one clause) there cannot be $u_1^N$–$u_{m+1}^S$ and $u_1^S$–$u_{m+1}^N$ paths that are mutually induced in $G$.

The reduction from Clause-Linked Planar E3-OCC 3-SAT of the proof of Theorem 1 is linear. Indeed it creates a constant number of vertices for each variable and for each clause. By the Sparsification Lemma of Impagliazzo, Paturi, and Zane [16] and classic linear reductions (see [9, 30]), $n$-variable Clause-Linked Planar E3-OCC 3-SAT requires time $2^{\mathrm{\Omega }(\sqrt{n})}$, under the ETH. We conclude that Induced Disjoint $S$–$T$ Paths with $|S|=|T|=2$ requires time $2^{\mathrm{\Omega }(\sqrt{n})}$ on $n$-variable string graphs of bounded twin-width and maximum degree. $◀$

We reduce from Induced 2-Disjoint Paths in string graphs. Given any input $(G^{\prime },s_1,t_1,s_2,t_2)$, we construct a graph $G$ as follows. Take the disjoint union of $G^{\prime }$ and $H$, remove the edges $st$ and $s^{\prime }{t}^{\prime }$ (of $H$), and identify $s_1$ with $s$, $t_1$ with $t$, $s_2$ with $s^{\prime }$, and $t_2$ with $t^{\prime }$. For the sake of clarity, for any $i\in [4]$, vertex set $A_i$ (in $H$) is renamed $B_i$ in $G$. Hence $V(G)=V(G^{\prime })\cup {\bigcup }_{i\in [4]}{B}_i$. One can observe that if $(G^{\prime },s_1,t_1,s_2,t_2)$ is a positive instance of Induced 2-Disjoint Paths, then $H$ is an induced subdivision of $G$. We show that the converse also holds, hence this linear reduction is correct.

Let $(\varphi :V(H)\to V(G),{(P_e)}_{e\in E(H)})$ be an induced subdivision model of $H$ in $G$. We say that a vertex of $H$ is mapped to its image by $\varphi$.

No subdivision of $K_{3,3}$ has a bridge. However, any induced subdivision in $G$ whose branching vertices intersect both $V(G^{\prime })$ and ${\bigcup }_{i\in [4]}{B}_i$ contains a bridge. This is because any of $s,t,s^{\prime },t^{\prime }$ is a cutvertex in $G$. Thus for every $i\in [4]$, $\varphi (A_i)\subset {\bigcup }_{i\in [4]}{B}_i$ or $\varphi (A_i)\subset V(G^{\prime })$. We now simply have to rule out the latter. Observe that there is no path in $G$ between two vertices in $V(G^{\prime })$ that exits $V(G^{\prime })$. Thus, if $\varphi (A_i)\subset V(G^{\prime })$, $G^{\prime }$ would contain an induced subdivision of the 1-subdivision of $K_{3,3}$, which does not hold as $G^{\prime }$ is a string graph. $\mathrm{⊲}$

Claim 13 implies that $\varphi ({\bigcup }_{i\in [4]}{A}_i)={\bigcup }_{i\in [4]}{B}_i$. Again, the absence of cutvertices in each $H[A_i]$ and $G[B_i]$ implies that for every $i\in [4]$ there is some $j\in [4]$ such that $\varphi (A_i)=B_j$. As $|A_1|=|A_2|\ne |A_3|=|A_4|$ and $\varphi$ is injective, $\{\varphi (A_1),\varphi (A_2)\}=\{B_1,B_2\}$ and $\{\varphi (A_3),\varphi (A_4)\}=\{B_3,B_4\}$. Now for the induced subdivision model of $H$ to be completed, there has to be in $G^{\prime }$ two mutually induced paths between $s_1$ and $t_1$, and between $s_2$ and $t_2$. Thus $(G^{\prime },s_1,t_1,s_2,t_2)$ is indeed a positive instance. $◀$

The previous reduction also works for $H$-Induced Minor Containment. However, the proof is slightly more involved. We tune $H$ a little bit such that it is still subcubic but has no two adjacent vertices of degree 3 (so that the forthcoming result answers a question of Korhonen and Lokshtanov). We call the resulting graph $H^{\prime }$; see Figure 5.

See 4

Again, we reduce from Induced 2-Disjoint Paths in string graphs and build from any input $(G^{\prime },s_1,t_1,s_2,t_2)$, a graph $G$ in the following way: Take the disjoint union of $G^{\prime }$ and $H^{\prime }$, remove the edges $st$ and $s^{\prime }{t}^{\prime }$ (of $H^{\prime }$), and identify $s_1$ with $s$, $t_1$ with $t$, $s_2$ with $s^{\prime }$, and $t_2$ with $t^{\prime }$. For any $i\in [4]$, vertex set $A_i$ (in $H^{\prime }$) is renamed $B_i$ in $G$. Thus $V(G)=V(G^{\prime })\cup {\bigcup }_{i\in [4]}{B}_i$. If $(G^{\prime },s_1,t_1,s_2,t_2)$ is a positive instance of Induced 2-Disjoint Paths, then $H^{\prime }$ is an induced subdivision, and hence an induced minor of $G$. Again, we show that the converse also holds.

Let $h:=|V(H^{\prime })|=74$, and $(ℳ:=\{X_1,\mathrm{\dots },X_h\},\varphi :V(H^{\prime })\to ℳ)$ be a minimal induced minor model of $H^{\prime }$ in $G$. First, assume that there is an $i\in [4]$ and $x\in A_i$ such that $\varphi (x)\cap V(G^{\prime })\ne \mathrm{\varnothing }$. As $G^{\prime }$ is a string graph (but $H^{\prime }[A_i]$ is not), there is also some $y\in A_i$ and $j\in [4]$ such that $\varphi (y)\cap B_j\ne \mathrm{\varnothing }$. Let $u$ be the vertex of $\{s_1,t_1,s_2,t_2\}$ with a neighbor in $B_j$. As $u$ is a cutvertex in $G$ that disconnects $B_j$ from the rest of $G$, there is a $z\in A_i$ such that $u\in \varphi (z)$.

As every branch set is connected, for every $z^{\prime }\in A_i\setminus \{z\}$, either $\varphi (z^{\prime })\subset B_j$ or $\varphi (z^{\prime })\subset V(G-B_j)$. Furthermore, as $H^{\prime }[A_i]$ has no cutvertex (in particular $z$ is not a cutvertex of $H^{\prime }[A_i]$), either for every $z^{\prime }\in A_i\setminus \{z\}$, $\varphi (z^{\prime })\subset B_j$, or for every $z^{\prime }\in A_i\setminus \{z\}$, $\varphi (z^{\prime })\subset V(G-B_j)$. The latter would contradict the minimality of $(ℳ,\varphi )$ as the (non-empty subset of) vertices of $B_j$ could then be removed from every branch set; and in particular $\varphi (y)$ would strictly decrease.

Therefore, for every $z^{\prime }\in A_i\setminus \{z\}$, $\varphi (z^{\prime })\subset B_j$. Moreover, it should hold that $z$ has a neighbor in $\{s,t,s^{\prime },t^{\prime }\}$, say $s$. Now, one can change the induced minor model by moving $\varphi (z)\cap V(G-B_j)$ to the adjacent branch set $\varphi (s)$. This indeed still works as an induced minor model of $H^{\prime }$ in $G$, and can greedily be made minimal (if need be).

After at most three more similar steps, we obtain a (minimal) induced minor model $({ℳ}^{\prime },{\varphi }^{\prime })$ such that for every $x\in {\bigcup }_{i\in [4]}{A}_i$, ${\varphi }^{\prime }(x)\subseteq {\bigcup }_{i\in [4]}{B}_i$. We may then conclude as in the proof of Theorem 3. The ETH lower bound is a direct consequence of Theorem 2 and of the fact that the present reduction is linear. $◀$