Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard

Let $G$ be a graph and $A\subseteq V(G)$. We let $\overline{A}=V(G)\setminus A$. We denote by $G[A,\overline{A}]$ the bipartite subgraph of $G$ with vertex bipartition $(A,\overline{A})$ whose edges are $\{ab\mid ab\in E(G),a\in A,b\in \overline{A}\}$. A set of edges $M=\{a_i{b}_i\mid i\in [r]\}\subseteq E(G)$ is a matching if all vertices in $V(M)={\bigcup }_{i\in [r]}\{a_i,b_i\}$ are pairwise distinct. A matching $M$ is induced if $E(G[V(M)])=M$. The mim-value of a set $A\subseteq V(G)$, denoted by ${\mathrm{𝗆𝗂𝗆}}_G(A)$, is the largest size of any induced matching in $G[A,\overline{A}]$. Let $\lambda =(v_1,\mathrm{\dots },v_n)$ be a linear order of $V(G)$. The maximum induced matching width (mim-width) of $\lambda$ is ${\max }_{i\in [n]}{\mathrm{𝗆𝗂𝗆}}_G(\{v_1,\mathrm{\dots },v_i\})$.

The following observation will be helpful in a later proof.

For each $i\in [n]$, we create a variable gadget as follows. It consists of a sequence of $m$ cycles on six vertices such that traversing each cycle clockwise corresponds to setting $x_i$ to true, and traversing them counterclockwise corresponds to setting $x_i$ to false. The construction ensures that for each variable, all cycles are traversed in the same way.

Let $i\in [n]$. We show how to construct the variable gadget ${𝚅}_i$. For each $j\in [m]$, it contains a cycle $D_i^j$ whose vertices (listed in order) are called $0\text{-}in(i,j)$, $0\text{-}out(i,j)$, $z_{out}(i,j)$, $1\text{-}out(i,j)$, $1\text{-}in(i,j)$, $z_{in}(i,j)$. For each $j\in [m-1]$, we add an edge between $1\text{-}out(i,j)$ and $1\text{-}in(i,j+1)$, and between $0\text{-}out(i,j)$ and $0\text{-}in(i,j+1)$. See Figure 2 for an illustration. Moreover, there is a vertex $s_i$, adjacent to $0\text{-}in(i,1)$ and $1\text{-}in(i,1)$, and a vertex $t_i$, adjacent to $0\text{-}out(i,m)$ and $1\text{-}out(i,m)$.

For each clause $C_j$, we add a gadget ${𝙲}_j$ with the following property. Say variable $x_i$ appears in $C_j$. If a given truth assignment to $x_i$ satisfies $C_j$, then we can enter and collect the vertices of ${𝙲}_j$ from $D_i^j$ (in the variable gadget ${𝚅}_i$) under the traversal of $D_i^j$ corresponding to that truth assignment to $x_i$. To avoid “cheating”, we need ${𝙲}_j$ to have the following property: once a path enters a vertex of ${𝙲}_j$, then we have to immediately collect all vertices from ${𝙲}_j$, and leave again via a prescribed exit, depending on where we entered ${𝙲}_j$. The following clause gadget due to Cygan, Kratsch, and Nederlof [14] achieves just that. We visualize these graphs in Figure 3.

We now construct the graph $G$ from the formula $\varphi$, see Figure 4 for an illustration.

First, we add two vertices $s$ and $t$ to $G$, which will have degree one and are therefore the endpoints of any Hamiltonian path in $G$, if one exists. For each $i\in [n]$, we add a variable gadget ${𝚅}_i$. We furthermore add the edges $s{s}_1$, $t_{n}t$, and for all $i\in [n-1]$, we proceed as follows. We add a vertex $p_{i+1}$ to $G$, and add the edges $t_i{p}_{i+1}$ and $p_{i+1}{s}_{i+1}$.

Next, for each clause $C_j$ with literals ${\mathrm{\ell }}_1,\mathrm{\dots },{\mathrm{\ell }}_k$, we proceed as follows. We let the clause gadget ${𝙲}_j$ be a copy of ${\mathrm{\Gamma }}_k$ from Lemma 3; let $({\sigma }_1,{\tau }_1)$, $\mathrm{\dots }$, $({\sigma }_k,{\tau }_k)$ be its distinguished vertices. For each $h\in [k]$, let $x_{j_h}$ be the variable of literal ${\mathrm{\ell }}_h$. If $x_{j_h}$ appears positively in $C_j$, then we add the edges $\{{\sigma }_h,0\text{-}in(i,j)\}$ and $\{{\tau }_h,0\text{-}out(i,j)\}$, and if $x_{j_h}$ appears negated in $C_j$, then we add $\{{\sigma }_h,1\text{-}in(i,j)\}$ and $\{{\tau }_h,1\text{-}out(i,j)\}$. This finishes the main part of the construction.

At this point, $G$ may have arbitrarily high mim-width. To reduce the mim-width of the graph, we add lots of dummy edges. These edges are introduced in such a way that they decrease the mim-width without allowing to “cheat”. That is, no Hamiltonian path of $G$ will ever use any of these edges. We proceed as follows. For each $j\in [m-1]$, each $i\in [2..n]$, and each , we add the edges $\{b_1\text{-}out(i,j),b_2\text{-}in(h,j+1)\}$, for any $b_1,b_2\in \{0,1\}$. Moreover, for each $i,j\in [t]$ with , we add the edge $\{t_i,p_j\}$.

This finishes the construction. Clearly, this reduction can be performed in polynomial time. We show that it is correct.

Suppose that $\varphi$ has a satisfying assignment $\alpha :\mathrm{𝖵𝖺𝗋}(\varphi )\to \{0,1\}$. We construct a Hamiltonian path $P$ of $G$ as follows. See Figure 5 for an illustration of this construction. First, $P$ starts in $s$, $s_1$. If $\alpha (x_1)=1$, then the next vertex of $P$ is $1\text{-}in(1,1)$, and if $\alpha (x_1)=0$, then the next vertex of $P$ is $0\text{-}in(1,1)$. Suppose the former is the case, the latter case is symmetric. The next vertices on $P$ are $z_{in}(1,1)$, $0\text{-}in(1,1)$. Now, if $x_1$ appears positively in $C_1$, then by construction, we can enter the gadget ${𝙲}_1$ from $0\text{-}in(1,1)$, collect all its vertices, and leave it to arrive at $0\text{-}out(1,1)$. Note that in this case, $x_1$’s truth assignment satisfied $C_1$. $P$ then collects $z_{out}(1,1)$, $1\text{-}out(1,1)$, and takes the edge to $1\text{-}in(1,2)$. We proceed analogously in sequence on all $D_1^j$, until we reach $t_1$. Here we follow the edge to $p_2$, $s_2$, and proceed on ${𝚅}_2$ as we did on ${𝚅}_1$, now based on which value $\alpha$ assigns $x_2$. We repeat this process until we finally reach $t$.

Whenever the truth assignment $\alpha (x_i)$ satisfies a clause $C_j$, we are able to collect the vertices of ${𝙲}_j$. Therefore, the procedure described above indeed produces a Hamiltonian path of $G$. $◀$

Let $s,t\in V(G)$, and let $P$ be an $(s,t)$-path in $G$. For distinct $u,v\in V(P)$, we write $u{\prec }_{P}v$ if the path from $s$ to $v$ contains $u$. For two sets $X,Y\subseteq V(G)$, we write $X{\prec }_{P}Y$ if for all $x\in X$, $y\in Y$, $x{\prec }_{P}y$. For intuition on the following notions, recall Figure 2.

Let $P$ be a Hamiltonian path in $G$. By Lemma 7, $P$ is $(n,m)$-respectable and in particular, for every $i\in [n]$, $P$ traverses $D_i^1,\mathrm{\dots },D_i^m$ in either true-order or false-order. We construct a truth assignment $\alpha :\mathrm{𝖵𝖺𝗋}(\varphi )\to \{0,1\}$ as follows. For each $i\in [n]$, if $P$ traverses $D_i^1,\mathrm{\dots },D_i^m$ in true-order, we set $\alpha (x_i)=1$, and if $P$ traverses $D_i^1,\mathrm{\dots },D_i^m$ in false-order, we set $\alpha (x_i)=0$. Let $j\in [m]$. Since $P$ is a Hamiltonian path, it collects the vertices in ${𝙲}_j$. By Lemma 3, there is some $i\in [n]$ such that $P$ contains a path starting with a vertex in $D_i^j$, traversing all vertices in ${𝙲}_j$, and ending with a vertex in $D_i^j$. By construction, the two vertices in $D_i^j$ are $0\text{-}in(i,j)$, $0\text{-}out(i,j)$, if $x_i$ appears positively in $C_j$, and $1\text{-}in(i,j)$, $1\text{-}out(i,j)$, if $x_i$ appears negated in $C_j$. Suppose without loss of generality that the former is the case. For $P$ to contain the described subpath, it must have entered $D_i^j$ at vertex $1\text{-}in(i,j)$, which implies that $P$ traverses $D_i^1,\mathrm{\dots },D_i^m$ in true-order. By our construction, $\alpha (x_i)=1$, meaning that the literal of $C_j$ containing $x_i$ satisfies $C_j$. $◀$

Let $\lambda$ be any linear order on $V(G)$ extending the following partial order:

Throughout the following, we let $D={\bigcup }_{(i,j)\in [n]\times [m]}{D}_i^j$, $P=\{p_i\mid i\in [n]\}$, $S=\{s\}\cup \{s_i\mid i\in [n]\}$, $T=\{t_i\mid i\in [n]\}\cup \{t\}$. Let $(A,\overline{A})$ be any cut induced by $\lambda$ (such that $A$ contains the first $t$ vertices of $\lambda$ for some $t\le |V(G)|$), and let $M$ be an induced matching in $G[A,\overline{A}]$. Each edge of $M$ is one of the following types, and below we justify the bounds on their number indicated in the respective parenthesis.

1. 1.

   Between $S\cup P$ and $S\cup T$ ($\le 1$).

2. 2.

   Between $S\cup T$ and $D$ ($\le 1$).

3. 3.

   Between $D$ and $V({𝙲}_j)$, for some $j\in [m]$ ($\le 6$).

4. 4.

   Inside $V({𝙲}_j)$ for some $j\in [m]$ ($\le 13$).

5. 5.

   Inside $D$ ($\le 4$).

For edges of type 1, note that $G[A\cap (S\cup P),\overline{A}\cup (S\cup T)]$ is a chain graph plus possibly one edge $p_i{s}_i$, for some $i\in [n]$. Recall by Observation 2, $M$ can contain at most one edge from any chain graph. Furthermore, if $p_i{s}_i\in M$, then $M$ has no other edge from this subgraph, since in this case, $p_i\in A$ is adjacent to all vertices in $T\cap \overline{A}$ that have a neighbor in $(S\cup P)\cap A$. So in either case, there is at most one edge of type 1 in $M$.

For edges of type 2, such edges can only occur if either some $s_i$ is the last vertex of $A$ or if some $t_i$ is the first vertex of $\overline{A}$; in any case, there is at most one such edge in $M$. The number of edges of types 3 and 4 are trivial upper bounds.

Lastly, consider edges of type 5. Let $(j,i)$ be the lexicographically largest pair such that $A$ contains vertices from $D_i^j$. First, there are at most two edges from $D_i^j$ itself in $M$. Next, consider the edges in $M$ that are between $D^j={\bigcup }_{i\in [n]}{D}_i^j$ and $D^{j+1}={\bigcup }_{i\in [n]}{D}_i^{j+1}$. Suppose there is some $h\in [n]$ such that there is an edge $d_j{d}_{j+1}$ in $M$, where $d_j\in D_h^j$ and $d_{j+1}\in D_h^{j+1}$. Note that there are at most two such edges per $h$. Moreover, in this case, $M$ has no other edges between $D^j$ and $D^{j+1}$, since for each such edge, at least one endpoint has a neighbor in $\{d_j,d_{j+1}\}$. So in this case, there are at most four edges of type 5 in total. If there is no such $h$, then by a similar argument, $M$ contains at most one edge between $D^j$ and $D^{j+1}$, in which case we have at most three edges of type 5. $◀$

This finishes the proof for Hamiltonian Path. By adding another degree-two vertex adjacent to only $s$ and $t$, we also obtain the same result for the Hamiltonian Cycle problem and the fact that adding a vertex to a graph increase its mim-width by at most $1$. See 1