On the Hardness of Recognizing Graphs of Small Mim-Width and Its Variants

We start by proving that $\mathrm{sim}-\mathrm{width}(G)\le 2$.

This follows directly from the fact that the maximum induced matching in the full graph $G$ has size at most 2. Suppose, for contradiction, that there exists an induced matching of size at least $3$. Since the set $P$ is an independent set in $G$, at least one endpoint of every edge in the matching must belong to $U$. By construction, each vertex in $U$ is adjacent to all other vertices of $U$ except two, which themselves are adjacent. Hence, among any three such vertices of $U$, there must exist at least one edge between them, contradicting the assumption that they form an induced matching.

We now prove that if $(Q,P)\notin \text{UQC}$, then $\mathrm{sim}-\mathrm{width}(G)\ge 2$.

Let $(Q,P)\notin \text{UQC}$, and let $T$ be a branch decomposition of $G$. There must exist a quartet $q=[p_i{p}_j\mid p_k{p}_{\mathrm{\ell }}]\in Q$ not satisfied by $T$, otherwise $(Q,P)$ would be in UQC. Assume without loss of generality that ${p_i{p}_k\mid }_T{p}_j{p}_{\mathrm{\ell }}$, and let $e$ be an edge of $T$ inducing the cut $(A_e,B_e)$ such that $p_i,p_k\in A_e$ and $p_j,p_{\mathrm{\ell }}\in B_e$. At least one of the edges along the path $p_i-u_i^q-u_j^q-p_j$ must cross this cut, and similarly, one of the edges along the path $p_k-u_k^q-u_{\mathrm{\ell }}^q-p_{\mathrm{\ell }}$ must also cross the cut. Because there is no edge with one endpoint in the first path and the other in the second path, these two edges form an induced matching in $G$, and therefore ${\mathrm{sim}-\mathrm{width}}_G(T)\ge 2$ for every branch decomposition $T$. Consequently, $\mathrm{sim}-\mathrm{width}(G)\ge 2$. $◀$

Let $T$ be such a caterpillar, and let $\le$ be a total order on $P$ that $T$ realizes. For each $p_i\in P$, define

that is, $C_i$ consists of all vertices in $P\cup U$ whose index is $i$. We extend $\le$ to a total order ${\le }^{\prime }$ on $P\cup U$ as follows.

For all $p_i,p_j\in P$ with , and for all $x\in C_i$, $y\in C_j$, we set . Within each $C_i$, the relative position of $p_i$ and any $u_i^q$ depends on the quartet $q$:

If $q=[p_i{p}_j\mid p_k{p}_{\mathrm{\ell }}]$, then, since $T$ satisfies $q$, we have either $p_i,p_j\le p_k,p_{\mathrm{\ell }}$ or $p_k,p_{\mathrm{\ell }}\le p_i,p_j$ (because the four vertices are distinct). In the former case ($p_i,p_j\le p_k,p_{\mathrm{\ell }}$) we set , in the latter case ($p_k,p_{\mathrm{\ell }}\le p_i,p_j$) we set . Note that this implies that we have either

We choose an arbitrary order within $C_i$ among the $u$-vertices to the left of $p_i$ and among those to the right of $p_i$. We then consider the ternary caterpillar $T^{\prime }$ realizing ${\le }^{\prime }$. We now prove that ${\mathrm{Omim}-\mathrm{width}}_G(T^{\prime })=1$, that is, ${\mathrm{Omim}}_G(A_e,B_e)=1$ for every edge $e$ of $T^{\prime }$.

Because $T^{\prime }$ is a caterpillar, it suffices to consider the cuts induced by the edges of its spine. Let $e$ be an edge of the spine, and let $(A_e,B_e)$ be the cut induced by $e$. Since $T^{\prime }$ realizes the order ${\le }^{\prime }$, one side of the cut corresponds to an initial segment of ${\le }^{\prime }$. Thus, we have either for all $a\in A_e$ and $b\in B_e$, , or for all $a\in A_e$ and $b\in B_e$, .

To prove that ${\mathrm{Omim}}_G(A_e,B_e)=1$, we need to prove that the upper induced matching numbers of $A_e$ and $B_e$ are both equal to one. This means that there is no matching of size $2$ in $G[A_e,B_e]$ that is an induced matching in the graph $G-E_G[A_e]$ or in the graph $G-E_G[B_e]$. Let $a_1{b}_1,a_2{b}_2\in E(G)$ be two edges with disjoint endpoints such that $a_1,a_2\in A_e$ and $b_1,b_2\in B_e$. To prove that it is not an induced matching in $G-E_G[A_e]$ or $G-E_G[B_e]$, it suffices to show that one of the two following conditions holds:

1. 1.

   One of the diagonals $a_1{b}_2$ or $a_2{b}_1$ is an edge, or

2. 2.

   Both $a_1{a}_2$ and $b_1{b}_2$ are edges.

Suppose for the sake of contradiction that neither condition holds. Each vertex $p_i\in P$ is connected only to vertices of the form $u_i^q$. Consider two edges $p_i{u}_i^q$ and $p_j{u}_j^{q^{\prime }}$ with $i\ne j$. By the construction of the order ${\le }^{\prime }$, we have either or . Given that the cut can only separate $p_i$ from at most one of its neighbours in $G$, it is therefore impossible for the cut $(A_e,B_e)$ to contain both edges $p_i{u}_i^q$ and $p_j{u}_j^{q^{\prime }}$. Consequently, at most one vertex among $\{a_1,a_2,b_1,b_2\}$ can belong to $P$.

Suppose that exactly one vertex among $\{a_1,a_2,b_1,b_2\}$ belongs to $P$. Without loss of generality, assume that $a_1=p_i$. Then $b_1$ must be of the form $u_i^q$. We are supposing that condition 1 is false and that $a_2{b}_1$ is not an edge. Since $b_1\in U$, the only vertices in $U$ that are not adjacent to $u_i^q$ are those corresponding to the other side of the same quartet. That is, if $q=[p_i{p}_j\mid p_k{p}_{\mathrm{\ell }}]$, then these vertices are $u_k^q$ and $u_{\mathrm{\ell }}^q$. By the definition of the order ${\le }^{\prime }$, we have either , or . Since the edge $e$ lies on the path between $a_1=p_i$ and $b_1=u_i^q$ in $T^{\prime }$, the vertices $u_k^q$ and $u_{\mathrm{\ell }}^q$ cannot belong to $A_e$. This yields a contradiction.

Now suppose that all vertices $\{a_1,a_2,b_1,b_2\}$ belong to $U$. Let $q$ be the quartet associated with $a_1$ and $q^{\prime }$ the quartet associated with $b_1$. As before, We are supposing that condition 1 is false, and that neither $a_1{b}_2$ nor $a_2{b}_1$ is an edge. The only vertices in $U$ not adjacent to $a_1$ correspond to the other side of the same quartet, so $q$ must also be the quartet of $b_2$. Similarly, $q^{\prime }$ must be the quartet of $a_2$.

If $q=q^{\prime }$, then we have $\{a_1,a_2,b_1,b_2\}=\{u_i^q,u_j^q,u_k^q,u_{\mathrm{\ell }}^q\}$ for some $q=[p_i{p}_j\mid p_k{p}_{\mathrm{\ell }}]\in Q$. The only edges among these vertices are $u_i^q{u}_j^q$ and $u_k^q{u}_{\mathrm{\ell }}^q$, which are both separated by $e$. Consequently, the quartet $[u_i^q{u}_j^q\mid u_k^q{u}_{\mathrm{\ell }}^q]$ is not satisfied by $T^{\prime }$, which, by the definition of ${\le }^{\prime }$, implies that $q$ is not satisfied by $T$, and we have a contradiction.
On the other hand, if $q\ne q^{\prime }$, then both $a_1{a}_2$ and $b_1{b}_2$ are edges, which contradicts the supposition that condition 2 holds. $◀$

Proposition 6 follows from Lemma 7 and Lemma 8. We are now ready to prove Theorem 1.

Let $\sigma$ be one of the parameters $\mathrm{sim}-\mathrm{width},\mathrm{omim}-\mathrm{width},\mathrm{Omim}-\mathrm{width}$, $\mathrm{linear}-\mathrm{sim}-\mathrm{width},\mathrm{linear}-\mathrm{omim}-\mathrm{width}$, or $\mathrm{linear}-\mathrm{Omim}-\mathrm{width}$. We want to show that deciding whether $\sigma (G)=1$ is NP-complete. Membership in NP is easy since a branch decomposition is an easily verifiable certificate.

For NP-hardness, for technical accuracy we need to use Theorem 4 and reduce Betweenness to deciding $\sigma (G)=1$. Take an instance $I$ of Betweenness and let $(Q,P)$ be the UQC instance obtained from Theorem 4, and then obtain $G$ as constructed above from that UQC instance. If $I$ is a YES-instance of Betweenness, then $(Q,P)\in$ UQC and by Theorem 4 there is a ternary caterpillar that satisfies $Q$. Then, Proposition 6 implies that $\mathrm{linear}-\mathrm{Omim}-\mathrm{width}(G)=1$. This implies that $\sigma (G)=1$, since $\mathrm{linear}-\mathrm{Omim}-\mathrm{width}(G)$ is an upper bound on all the possible $\sigma$ parameters listed above (by Lemma 3).

Conversely, if $I$ is a NO-instance of Betweenness, then no tree satisfies the UQC instance $(Q,P)$. By Proposition 6, $\mathrm{sim}-\mathrm{width}(G)=2$, which implies $\sigma (G)\ge 2$ since $\mathrm{sim}-\mathrm{width}(G)$ is a lower bound on all the possible $\sigma$ parameters listed above (by Lemma 3). Therefore, $I$ is a YES-instance of Betweenness if and only if $\sigma (G)=1$.

Moreover $|V(G)|=|P|+4|Q|$, therefore an algorithm recognising graphs with $\sigma$ parameter equal to one in time $2^{o(|V(G)|)}$ could be used to solve UQC in time $2^{o(|P|+|Q|)}$, contradicting Theorem 5 assuming ETH. $◀$

Suppose, for the sake of contradiction, that there exists an edge $e$ of $\pi$ such that one of the $\gamma$-vertices lies in $A_e$ and another lies in $B_e$. We will show that we can always find an induced matching of size $3$ in $G[A_e,B_e]$. We proceed by a case analysis.

First, consider the case where both ${\gamma }_i^q$ and ${\gamma }_k^q$ lie in $A_e$. Choose $x\in \{j,\mathrm{\ell }\}$ such that ${\gamma }_x^q$ is a $\gamma$-vertex in $B_e$. Along the path $p_i-u_i^q-u_j^q-p_j$ of $G$, at least one edge crosses the cut $(A_e,B_e)$; likewise, at least one edge of the path $p_k-u_k^q-u_{\mathrm{\ell }}^q-p_{\mathrm{\ell }}$ also crosses the cut. These two crossing edges, together with the edge ${\gamma }_i^q{\gamma }_x^q$, form an induced matching in $G[A_e,B_e]$. Indeed, the only other edges that could appear among these six vertices in $G$ are $p_i{\gamma }_i^q$, which lies entirely within $A_e$, and $p_x{\gamma }_x^q$, which lies entirely within $B_e$.

Therefore, we may assume that at least one of ${\gamma }_i^q$ or ${\gamma }_k^q$ is in $B_e$. Without loss of generality, we may assume that ${\gamma }_i^q\in B_e$. By applying the symmetric argument on the pair ${\gamma }_j^q,{\gamma }_{\mathrm{\ell }}^q$, we may assume that one of the vertices ${\gamma }_j^q$ or ${\gamma }_{\mathrm{\ell }}^q$ lies in $A_e$.

Suppose now that $u_j^q\in A_e$. Then one of the edges on the path $p_k-u_k^q-u_{\mathrm{\ell }}^q-p_{\mathrm{\ell }}$, together with the edges $p_i{\gamma }_i^q$ and $u_j^q{p}_j$, forms an induced matching in $G[A_e,B_e]$. Hence we may assume $u_j^q\in B_e$.

Next, suppose that $u_i^q\in A_e$. Then one of the edges on the path $p_k-u_k^q-u_{\mathrm{\ell }}^q-p_{\mathrm{\ell }}$, together with the edges $p_i{\gamma }_i^q$ and $u_i^q{u}_j^q$, forms an induced matching in $G[A_e,B_e]$. Hence we may assume $u_i^q\in B_e$.

If we had ${\gamma }_j^q\in A_e$, then one of the edges on the path $p_k-u_k^q-u_{\mathrm{\ell }}^q-p_{\mathrm{\ell }}$, together with the edges $p_i{u}_i^q$ and ${\gamma }_j^q{p}_j$, forms an induced matching in $G[A_e,B_e]$. Therefore ${\gamma }_j^q\in B_e$.

It follows that ${\gamma }_{\mathrm{\ell }}^q\in A_e$, and by symmetry again, we have ${\gamma }_k^q,u_k^q,u_{\mathrm{\ell }}^q\in A_e$ as well. In this situation, the three edges $u_{\mathrm{\ell }}^q{p}_{\mathrm{\ell }}$, $p_i{u}_i^q$, and ${\gamma }_k^q{\gamma }_j^q$ form an induced matching in $G[A_e,B_e]$.

This establishes that either ${\gamma }_i^q,{\gamma }_j^q,{\gamma }_k^q,{\gamma }_{\mathrm{\ell }}^q$ are all contained in $A$, or they are all contained in $B$. $\mathrm{⊲}$

We will assume without loss of generality that all the gammas are in $B$. We are now ready to finish the proof of Lemma 10.

We now assume for contradiction that $T$ is a caterpillar satisfying $\mathrm{linear}-\mathrm{mim}-\mathrm{width}(T)\le 2$, implying in particular that $\mathrm{mim}-\mathrm{width}(T)\le 2$. Note that Claim 12 is applicable to $T$ since it holds for any branch decomposition. Now, one of $p_j$ or $p_{\mathrm{\ell }}$ is adjacent to an endpoint of $\pi$ in $T$ (recall that $\pi$ is the set of edges separating $A$ and $B$). Without loss of generality, suppose it is $p_j$, and let $z$ be the neighbor of $p_j$ on the spine of the caterpillar. Let $e$ be the edge incident to $z$ that is not in $\pi$, other than $z{p}_j$ (so, $e$ is the next edge on the spine beyond $\pi$, going towards $p_{\mathrm{\ell }}$). This induces a cut $(A_e,B_e)$ with $p_{\mathrm{\ell }}$ and all the $\gamma$-vertices in $B_e$, and $p_i,p_j,p_k\in A_e$. Consequently, the edges $p_i{\gamma }_i^q$, $p_j{\gamma }_j^q$, and $p_k{\gamma }_k^q$ form an induced matching in $G[A_e,B_e]$. This implies that $\mathrm{linear}-\mathrm{mim}-\mathrm{width}(T)\ge 3$, which contradicts our initial assumption that $\mathrm{linear}-\mathrm{mim}-\mathrm{width}(T)\le 2$. $◀$

The proof of Lemma 11 is slightly more complicated, because $T$ might not be a caterpillar. Therefore, we need a case analysis depending on which vertices of $B$ lie in the branch containing $p_j$ and which lie in the branch containing $p_{\mathrm{\ell }}$. The additional vertex $\omega$ is required to force an induced matching of size $3$ in all configurations.

We assume for contradiction that $T$ is a branch decomposition of $H$ satisfying $\mathrm{mim}-\mathrm{width}(T)\le 2$. Let $v$ be the endpoint of $\pi$ that lies on the path between $p_j$ and $p_{\mathrm{\ell }}$ in $T$ (thus, one incident “side” of $v$ contains $p_j$, one contains $p_{\mathrm{\ell }}$, and the remaining side contains both $p_i$ and $p_k$, see figure). Let $e_{mid}$ be the edge from $v$ toward $p_i$ and $p_k$, $e_{top}$ the edge toward $p_j$, and $e_{bot}$ the edge toward $p_{\mathrm{\ell }}$. We denote by $(A_{mid},B_{mid})$, $(A_{bot},B_{bot})$, and $(A_{top},B_{top})$ the cuts induced by $e_{mid}$, $e_{bot}$, $e_{top}$, respectively. We have $B_{mid}=B$, and we partition $B$ as $B=B_{bot}\cup B_{top},$ where $B_{bot}$ (resp. $B_{top}$) consists of the vertices of $B$ in the branch toward $p_{\mathrm{\ell }}$ (resp. toward $p_j$).

The remainder of the proof accumulates a series of facts under our contradiction assumptions, ultimately showing that every possible placement of the $u$-vertices, the $\gamma$-vertices, and $\omega$ leads to a $3$-induced matching across one of the edges $e_{mid}$, $e_{bot}$, or $e_{top}$. Recall that we defined $A={\bigcap }_{e\in \pi }{A}_e$ and $B={\bigcap }_{e\in \pi }{B}_e$.

Claim 12 still holds, because $T$ can be turned into a branch decomposition of $G$ by deleting the $\omega$-leaf, which does not increase the mim-width of the decomposition. $◀$

We will now assume without loss of generality that all $\gamma$-vertices of the quartet $q$ lie in $B$

Suppose not, and assume without loss of generality that $u_i^q\notin B$ or $u_j^q\notin B$ (the cases $u_k^q\notin B$ or $u_{\mathrm{\ell }}^q\notin B$ are symmetric). Then one of the edges $u_i^q{u}_j^q$ or $u_j^q{p}_j$ crosses the cut $(A_{mid},B_{mid})$ (with $u_i^q\in A_{mid}$ in the first case). One of the edges of the path $p_k-u_k^q-u_{\mathrm{\ell }}^q-p_{\mathrm{\ell }}$ must also cross the cut. The vertex ${\gamma }_i^q$ is in $B=B_{mid}$ by Fact 1. These two edges, together with the edge $p_i{\gamma }_i^q$, form an induced matching of size 3. $◀$

Assume for contradiction that $\omega \notin B$. Using Fact 1 and Fact 2, all the $u$ and $\gamma$ vertices are in $B=B_{mid}$. In the cut $(A_{mid},B_{mid})$, the edges $\omega u_j^q$, $p_i{\gamma }_i^q$, and $p_k{\gamma }_k^q$ form an induced matching of size 3. $◀$

Note that by Fact 2, each $u$-vertex belongs to either $B_{top}$ or $B_{bot}$. If all the four $u$-vertices lie on the same side, say $B_{top}$, then across the cut $(A_{top},B_{top})$ the edges $p_i{u}_i^q$, $p_k{u}_k^q$, and $p_{\mathrm{\ell }}{u}_{\mathrm{\ell }}^q$ form an induced matching of size 3. Likewise, not all four $u$-vertices can lie in $B_{bot}$. $◀$

Using Fact 1, each $\gamma$-vertex is either in $B_{bot}$ or $B_{top}$. Assume ${\gamma }_k^q$ and ${\gamma }_{\mathrm{\ell }}^q$ are both in $B_{top}$. Then one of the edges of the path $p_i-u_i^q-u_j^q-p_j$ must cross the cut $(A_{top},B_{top})$. Together with the edges $p_k{\gamma }_k^q$ and $p_{\mathrm{\ell }}{\gamma }_{\mathrm{\ell }}^q$, this yields an induced matching of size 3, a contradiction. $◀$

Using Fact 3, the vertex $\omega$ is either in $B_{bot}$ or in $B_{top}$. In the rest of the proof, we will assume without loss of generality that $\omega \in B_{bot}$ (to see why this is without loss of generality, notice that if this is not the case, then we may swap the subscripts of $p_i$ and $p_k$, and the subscripts of $p_j$ and $p_{\mathrm{\ell }}$ without affecting the previous arguments since they all apply symmetrically to $B_{bot}$ and $B_{top}$).

Consider $u_x^q$ with $x\in \{i,j\}$. Using Fact 2, $u_x^q$ is either in $B_{bot}$ or in $B_{top}$. Assume by contradiction that it is in $B_{bot}$. We consider two subcases depending of the position of ${\gamma }_{\mathrm{\ell }}^q$. Using Fact 1, ${\gamma }_{\mathrm{\ell }}^q$ is either in $B_{bot}$ or in $B_{top}$.

If ${\gamma }_{\mathrm{\ell }}^q$ is in $B_{top}$, across the cut $(A_{bot},B_{bot})$, the following 3 edges form an induced matching:

• $\mathrm{■}$

  $p_x{u}_x^q$.

• $\mathrm{■}$

  ${\gamma }_{\mathrm{\ell }}^q{p}_{\mathrm{\ell }}$.

• $\mathrm{■}$

  One of the edge of the path $p_k-u_k^q-\omega$.

Otherwise ${\gamma }_{\mathrm{\ell }}^q$ is in $B_{bot}$. Then across the cut $(A_{bot},B_{bot})$, the following 3 edges form an induced matching:

• $\mathrm{■}$

  $p_x{u}_x^q$.

• $\mathrm{■}$

  We take an edge joining a $\gamma$-vertex in $B_{top}$ to ${\gamma }_{\mathrm{\ell }}^q$ in $B_{bot}$ (see Fact 5).

• $\mathrm{■}$

  One of the edge of the path $p_k-u_k^q-\omega$.

$◀$

Using Fact 1, each $\gamma$-vertex is either in $B_{bot}$ or $B_{top}$. Assume for contradiction that ${\gamma }_j^q$ and ${\gamma }_k^q$ are both in $B_{bot}$. Across the cut $(A_{bot},B_{bot})$, the following 3 edges form an induced matching: $p_j{\gamma }_j^q$, $p_k{\gamma }_k^q$, and $u_i^q\omega$ (we know that $u_i^q\in B_{top}$ using Fact 6). $◀$

Using Fact 2, $u_k^q$ is either in $B_{bot}$ or in $B_{top}$. Assume by contradiction that it is in $B_{top}$. Across the cut $(A_{top},B_{top})$, the following 3 edges form an induced matching:

• $\mathrm{■}$

  $p_i{u}_i^q$. We have $u_i^q\in B_{top}$ by Fact 6.

• $\mathrm{■}$

  $u_{\mathrm{\ell }}^q{u}_k^q$. We are assuming that $u_k^q\in B_{top}$. Moreover, we know that $u_i^q,u_j^q\in B_{top}$ (Fact 6), and that the $u$-vertices are not all in $B_{top}$ (Fact 4); therefore $u_{\mathrm{\ell }}^q$ is in $B_{bot}$.

• $\mathrm{■}$

  An edge joining a $\gamma$-vertex in $B_{bot}$ to either ${\gamma }_j^q$ or ${\gamma }_k^q$ in $B_{top}$. Such an edge exists using Fact 7.

$◀$

Assume by contradiction that there is a $\gamma$-vertex other than ${\gamma }_k^q$ in $B_{bot}$. Across the cut $(A_{bot},B_{bot})$, the following 3 edges form an induce matching:

• $\mathrm{■}$

  $p_k{u}_k^q$. We know that $u_k^q$ is in $B_{bot}$ by Fact 8.

• $\mathrm{■}$

  $u_i^q\omega$. We know that $u_i^q$ is in $B_{top}$ by Fact 6.

• $\mathrm{■}$

  An edge joining either ${\gamma }_i^q$ or ${\gamma }_j^q$ in $B_{top}$ (Fact 5) to a $\gamma$-vertex in $B_{bot}$ that is not ${\gamma }_k^q$.

$◀$

We can finally conclude the proof. By combining Fact 1 and Fact 9, we know that ${\gamma }_i^q$ and ${\gamma }_{\mathrm{\ell }}^q$ are both in $B_{top}$. Across the cut $(A_{top},B_{top})$, the following 3 edges form an induced matching: $p_i{\gamma }_i^q$, $p_{\mathrm{\ell }}{\gamma }_{\mathrm{\ell }}^q$, and $\omega u_j^q$ (since $u_j^q$ is in $B_{top}$ by Fact 6). This completes the proof: in all cases we obtain an induced matching of size 3. $◀$

As we already observed, $\mathrm{mim}-\mathrm{width}(G)\ge 2$ because it contains induced cycles of length $6$, implying $\mathrm{linear}-\mathrm{mim}-\mathrm{width}(G)\ge 2$. We focus on the upper bound.