Mim-Width Is paraNP-Complete

We denote by $V(G)$ and $E(G)$ the vertex and the edge set, respectively, of a graph $G$. If $G$ is a graph and $S\subseteq V(G)$, we denote by $G[S]$ the subgraph of $G$ induced by $S$, and use $G-S$ as a short-hand for $G[V(G)\setminus S]$. If $e\in E(G)$, we denote by $G-e$ the graph $G$ deprived of edge $e$, but the endpoints of $e$ remain. More generally, if $F\subseteq E(G)$, $G-F$ is the graph obtained from $G$ by removing all the edges of $F$ (but not their endpoints). For $X\subseteq V(G)$, we may denote by $E_G(X)$ the edge set of $G[X]$. We denote the open and closed neighborhoods of a vertex $v$ in $G$ by $N_G(v)$ and $N_G[v]$, respectively. For $S\subseteq V(G)$, we set $N_G(S):={\bigcup }_{v\in S}{N}_G(v)\setminus S$ and $N_G[S]:=N_G(S)\cup S$. In every notation with a graph subscript, we may omit it if the graph is clear from the context. A vertex set $S\subseteq V(G)$ covers an edge set $F\subseteq E(G)$ if every edge of $F$ has at least one endpoint in $S$.

A cut of a graph $G$ is a bipartition $(A,B)$ of $V(G)$. The cut-set defined by a cut $(A,B)$, denoted by $E(A,B)$, is $\{uv\in E(G)\mid u\in A,v\in B\}$. We denote by $G[A,B]$ the bipartite subgraph of $G$ with edge set $E(A,B)$. A matching is a set of edges that share no endpoints and an induced matching of $G$ is a matching $M$ such that every edge of $G$ intersects at most one edge in $M$. If $A,B\subseteq V(G)$ are two disjoint vertex subsets of $G$, a matching between $A$ and $B$ is a matching where every edge has one endpoint in $A$ and the other endpoint in $B$. An induced matching in $G[A,B]$ is called a semi-induced matching of $G$ between $A$ and $B$.

A branch decomposition or tree layout (or simply layout) of a graph $G$ is a pair $(T,f)$ where $T$ is a ternary tree (i.e., every internal node of $T$ has degree 3) and $f$ is a bijection from $V(G)$ to the leaves of $T$. Given two disjoint sets $X,Y\subseteq V(G)$, we denote by ${\text{mim}}_G(X,Y)$ (resp. ${\text{sim}}_G(X,Y)$) the maximum number of edges in a semi-induced matching (resp. induced matching) of $G$ between $X$ and $Y$, and may refer to it as mim-value (resp. sim-value). An edge $e$ of $T$ induces or defines a cut $(A_e,B_e)$ of $G$, where $A_e$ and $B_e$ are the preimages by $f$ of the leaves in the two components of $T-e$.

The mim-value (resp. sim-value) of $(A_e,B_e)$ is set as ${\text{mim}}_G(A_e,B_e)$ (resp. ${\text{sim}}_G(A_e,B_e)$). The mim-value (resp. sim-value) of the branch decomposition $(T,f)$ is the maximum of ${\text{mim}}_G(A_e,B_e)$ (resp. ${\text{sim}}_G(A_e,B_e)$) taken over every edge $e$ of $T$. Finally, the mim-width (resp. sim-width) of $G$ is the minimum mim-value (resp. sim-value) taken over every branch decomposition $(T,f)$ of $G$.

The upper-induced matching number of $X\subseteq V(G)$ is the maximum size of an induced matching of $G-E(V(G)\setminus X)$ between $X$ and $V(G)\setminus X$. The one-sided mim-width is defined as above with the omim-value of cut $(A_e,B_e)$, ${\text{omim}}_G(A_e,B_e)$, defined as the minimum between the upper-induced matching numbers of $A_e$ and of $B_e$.

The linear variants of these widths and values impose $T$ to be a rooted full binary tree (i.e, every internal node has exactly two children) such that the internal nodes form a path.

Given a total order $\prec$ on a graph $H$, we say that a vertex set $S$ is smaller (resp. larger) than another vertex set $U$, denoted by $S\prec U$ (resp. $U\prec S$), if for all $s\in S,u\in U$ we have $s\prec u$ (resp. $u\prec s)$. When a set $S$ is neither larger nor smaller than a vertex $u$, we say that $S$ surrounds $u$. We also say that $u$ is surrounded by $S$. Note that if $S$ surrounds two vertices $u$ and $v$, it surrounds any vertex $w$ with $u\prec w\prec v$.

We begin with a useful observation on the only possible $\tau$-balancing order of a $P_3$ (i.e., 3-vertex path) with large total weight.

We also rely on the following observation, where the induced subgraph of an edge-weighted graph $(H,\omega )$ is an induced subgraph of $H$ edge-weighted by the restriction of $\omega$ to its edge set.

Our main ingredient here is a family of edge-weighted caterpillars called bottleneck.

The vertex $v_1$ is called first terminal of $B$. A $(\tau ,\gamma )$-bottleneck is depicted in Figure 2.

A bottleneck ensures the following.

Henceforth every bottleneck is a $(\tau ,\gamma )$-bottleneck. Thus we simply write bottleneck.

The next lemma yields the crucial property ensured by bottleneck sequences.

We conclude the section by defining $\tau$-balancing orders for bottleneck sequences. A direct order ${\prec }_{\to }$ of a bottleneck $B$ with terminals $v_1,\mathrm{\dots },v_k$ goes as follows:

where $a_1{b}_2\mathrm{\dots }{a}_k{b}_k$ is the spine of $B$ rooted in $b_k$. Note that the order induced by $\{v_1,\mathrm{\dots },v_k\}$ is not specified (and so a given bottleneck on $k$ terminals admits $k!$ different direct orders). A reverse order of $B$, denoted by ${\prec }_{\leftarrow }$, is simply defined as the reverse order of a direct order ${\prec }_{\to }$.

A direct order ${\prec }_{\to }^{\text{seq}}$ of a bottleneck sequence $B(S_1,S_2,S_3)$ is a common (linear) extension of direct orders on $B_1^{+}$ and $B_2^{+}$ and reverse orders on $B_2^{-}$ and $B_3^{-}$. Note that on any bottleneck sequence, at least one direct order exists since the direct and reverse orders constrain disjoint vertex sets. In particular we have $S_1{\prec }_{\to }^{\text{seq}}{S}_2{\prec }_{\to }^{\text{seq}}{S}_3$. We check that any direct order of $B(S_1,S_2,S_3)$ is indeed $\tau$-balancing.

We now describe the reduction from Nae 3-Sat to Linear Degree Balancing. We recall that a not-all-equal 3-clause is satisfied if it has at least one satisfied literal and at least one unsatisfied literal. The Nae 3-Sat remains $\mathrm{𝖭𝖯}$-hard if each clause is on exactly three distinct positive literals, and every variable appears exactly four times positively (and zero times negatively) [6]. Let $\phi$ be any such $n$-variable Nae 3-Sat instance. As we will only deal with not-all-equal 3-clauses, we say that $\phi$ is satisfiable whenever it admits a truth assignment that, in each clause of $\phi$, sets a (positive) literal to true and another (positive) literal to false. We will build an edge-weighted graph $H:=H(\phi )$ as follows.

As mim-width is defined via branch decompositions, we adapt the balancing order problem to trees. Consider an edge-weighted graph $(H,\omega )$, and a tree $T$ such that there exists a bijective map $f:V(H)\to V(T)$. Note that $(T,f)$ is not a branch decomposition of $H$ for two reasons: vertices of $H$ are mapped to all nodes of $T$ and not merely its leaves, and $T$ is not necessarily a ternary tree (nor a rooted binary tree).

Each edge $e$ of $T$ defines a cut of $H$, which we denote $(A_e,B_e)$, where $A_e$ is the preimage by $f$ of one connected component of $T-e$, and $B_e$, of the other component. We say that $(T,f)$ is a $\tau$-balancing tree of $(H,\omega )$ if for any vertex $v\in V(H)$, for any edge $e\in E(T)$ incident to $f(v)$, the sum of the weights of edges (in $E(H)$) incident to $v$ in the cut $(A_e,B_e)$ is at most $\tau$.

Note that any graph with a $\tau$-balancing order also admits a $\tau$-balancing tree, with $T$ being the path of length $|V(H)|$, and $f$ mapping the vertices of $H$ along $T$ in the $\tau$-balancing order.

A partitioned graph is a pair $(G,𝒮)$ where $G$ is a graph and $𝒮$ is a partition of $V(G)$. A tree mapping of a partitioned graph $(G,𝒮)$ is a pair $(T,f)$ where $T$ is a tree and $f:𝒮\to V(T)$ is a bijection from the parts of $𝒮$ to the vertices of $T$. When $T$ is a path, we may call $(T,f)$ a path mapping of $𝒮$.

We say that a cut $(A,B)$ of $G$ is an $𝒮$-cut if each set in $𝒮$ is included in either $A$ or $B$. Each edge $e\in E(T)$ in a tree mapping $(T,f)$ of $(G,𝒮)$ defines an $𝒮$-cut $(A_e,B_e)$ of $G$: the union of the parts mapped to each component of $T-e$. The sim-value (resp. mim-value) of a tree mapping $(T,f)$ of $(G,𝒮)$ is the maximum taken over every edge $e\in E(T)$ of the maximum size of an induced (resp. semi-induced) matching between $A_e$ and $B_e$. The sim-balancing (resp. mim-balancing) of $(G,𝒮)$ is the minimum sim-value (resp. mim-value) among all possible tree mappings of $(G,𝒮)$. Similarly, the linear sim-balancing (resp. mim-balancing) is the minimum sim-value (resp. mim-value) among path mappings.

Note that even when $𝒮$ is the finest partition $\{\{v\}:v\in V(G)\}$, this problem is not exactly Mim-Width, as $f$ also maps vertices to internal nodes of $T$, and $T$ has no degree restriction. Linear Mim-Balancing (or Linear Sim-Balancing) is defined analogously except $T$ is forced to be a path. We may use Mim-Balancing to collectively refer to Linear Mim-Balancing and Tree Mim-Balancing; and similarly with Sim-Balancing.

At the end of this section, we will have established the following.

Let $(H,\omega )$ be an instance of Tree Degree Balancing with positive and integral weights. We build an instance of Tree Mim-Balancing $G:=G(H,\omega ),𝒮:=𝒮(H,\omega )$, as follows.

We start with the description of a gadget for each vertex of $H$.

To upper bound the linear mim-width of $G^{\ast }$, we need the next lemma on $𝒢(u)$. For each vertex $u$ of $H$, we define the caterpillar layout of $𝒢(u)$ as the left-aligned caterpillar (i.e, such that every right child is a leaf) layout with $|V(𝒢(u))|$ leaves bijectively labeled by $V(𝒢(u))$, in the order of $Q_u$ from the first vertex of $P_u^1$ to the last vertex of $P_u^b$.

We can now conclude for this direction of the reduction.

The main argument works as follows. We will prove that in any tree layout of $G^{\ast }$ of small sim-value, one can associate to each gadget $𝒢(u)$ an edge $e$ of the layout, such that a copy of $P_u$ can be found on both sides of the cut defined by $e$. Since $𝒢(u)$ is “represented” by any of its copies of $P_u$, we will use $e$ as where the vertices of $𝒢(u)$ should be moved to. With this in mind, we gradually build a tree mapping of $G$ from a tree layout of $G^{\ast }$ by “relocating” each gadget to the edge it is associated to. We start with two technical lemmas.

A hybrid tree of a partitioned graph $(J,𝒫)$ is pair $(T,f)$ where $T$ is a tree and $f:V(J)\to V(T)$ is a map such that for any node $t\in T$, either $f^{-1}(t)\in 𝒫$ or $|f^{-1}(t)|⩽1$. As for tree mappings each edge $e\in E(T)$ in a hybrid tree of $(J,𝒫)$ defines a cut $(A_e,B_e)$ of $J$: the sets of vertices mapped to each component of $T-e$. The sim-value of the hybrid tree $(T,f)$ is the maximum sim-value of all possible cuts $(A_e,B_e)$ for $e\in E(T)$.

We recall that ${𝒮}^{\ast }=\{V(𝒢(u)):u\in V(H)\}$. We observe that in the instances $(H,\omega )$ produced by the first reduction, every vertex has weight at most $2\tau$. Hence ${\max }_{u\in V(H)}|V(P_u)|⩽4\tau$. We set $\alpha :=\lceil \frac{b-1}{6\tau }\rceil -1=\tau +\gamma -1$, where $b$ is the constant introduced at the beginning of the section.

We now define a grouping operation on triples $(T,f,u)$, where $(T,f)$ is a subcubic hybrid tree of $(G^{\ast },{𝒮}^{\ast })$ of sim-value smaller than $\frac{2(b-1)}{3{\max }_{u\in V(H)}|V(P_u)|}$ (which is still very large compared to $\tau +\gamma$ by definition of $b$) and $u\in V(H)$, and denote it by $\text{group}(T,f,u)$. If there exists $t\in V(T)$ with $f^{-1}(t)=𝒢(u)$, then we set $\text{group}(T,f,u):=(T,f)$. Otherwise, Section 5.3 ensures that there is an edge $e\in E(T)$ such that a copy of $P_u$ is in both sides of the cut defined by $e$. We then define $\text{group}(T,f,u):=(T^{\prime },f^{\prime })$, where

• $\mathrm{■}$

  $T^{\prime }$ is obtained from $T$ by subdividing $e$, which adds a node, say, $t_e$, and

• $\mathrm{■}$

  $f^{\prime }$ satisfies that $f^{\prime }(x)=f(x)$ whenever $x\notin V(𝒢(u))$, and $f^{\prime }(x)=t_e$ otherwise.

Given an edge $e^{\prime }\in E(T^{\prime })$, the edge corresponding to $e^{\prime }$ in $T$ is $e^{\prime }$ if $e^{\prime }$ is an edge of $T$, and $e$ if $e^{\prime }$ is incident to $t_e$.

We make two observations on the grouping operation.

We can next show that a grouping can only decrease the sim-value.

We are now equipped to turn hybrid trees $G^{\ast }$ into tree mappings of $G^{\ast }$ no greater sim-value.

We can conclude.