Beating Treewidth for Average-Case Subgraph Isomorphism

Abstract

For any fixed graph G, the subgraph isomorphism problem asks whether an n-vertex input graph has a subgraph isomorphic to G. A well-known algorithm of Alon et al. (J ACM 42(4):844–856, 1995. https://doi.org/10.1145/210332.210337) efficiently reduces this to the “colored” version of the problem, denoted $G{\text{-}}{\mathsf {SUB}}$, and then solves $G{\text{-}}{\mathsf {SUB}}$ in time $O(n^{{\textit{tw}}(G)+1})$ where ${\textit{tw}}(G)$ is the treewidth of G. Marx (Theory Comput 6(1):85–112, 2010. https://doi.org/10.4086/toc.2010.v006a005) conjectured that $G{\text{-}}{\mathsf {SUB}}$ requires time $\varOmega (n^{{{\mathrm {const}}}\cdot {\textit{tw}}(G)})$ and, assuming the Exponential Time Hypothesis, proved a lower bound of $\varOmega (n^{{{\mathrm {const}}}\cdot {\textit{emb}}(G)})$ for a certain graph parameter ${\textit{emb}}(G) \ge \varOmega ({\textit{tw}}(G)/\log {\textit{tw}}(G))$. With respect to the size of ${{\mathrm {AC}}}^0$ circuits solving $G{\text{-}}{\mathsf {SUB}}$ in the average case, Li et al. (SIAM J Comput 46(3):936–971, 2017. https://doi.org/10.1137/14099721X) proved (unconditional) upper and lower bounds of $O(n^{2\kappa (G)+{{\mathrm {const}}}})$ and $\varOmega (n^{\kappa (G)})$ for a different graph parameter $\kappa (G) \ge \varOmega ({\textit{tw}}(G)/\log {\textit{tw}}(G))$. Our contributions are as follows. First, we prove that ${\textit{emb}}(G)$ is $O(\kappa (G))$ for all graphs G. Next, we show that $\kappa (G)$ can be asymptotically less than ${\textit{tw}}(G)$; for example, if G is a hypercube then $\kappa (G)$ is $\varTheta \left( {\textit{tw}}(G)\big /\sqrt{\log {\textit{tw}}(G)}\right)$. This implies that the average-case complexity of $G{\text{-}}{\mathsf {SUB}}$ is $n^{o({\textit{tw}}(G))}$ when G is a hypercube. Finally, we construct ${{\mathrm {AC}}}^0$ circuits of size $O(n^{\kappa (G)+{{\mathrm {const}}}})$ that solve $G{\text{-}}{\mathsf {SUB}}$ in the average case, closing the gap between the upper and lower bounds of Li et al.

Appendices

Appendix 1: Equivalence of Threshold Weightings and Markov Chains

Theorem 1

For any threshold weighting $(\alpha ,\beta )\in \theta (G)$ there exists a function $M:V(G)\times V(G)\rightarrow {\mathbb {R}}_{\ge 0}$ such that

• 1. $M(u,u)=0$ for all u,

• 2. $M(u,v)+M(v,u) = \beta (uv)$ for all $u\ne v$, and

• 3. $\sum _{v\in V(G)} M(u,v) = \alpha (u)$ for all u.

Proof

Let $\varDelta = (\alpha ,\beta )$. The proof is by induction on v(G). If G is a single vertex u then $\theta (G)$ consists only of $\alpha =0$, so setting $M(u,u) = 0$ satisfies the requirements. Now assume $v(G) > 1$. For $A, B \subseteq G$ let $M(A, B) = \sum _{u \in V(A), v \in V(B)} M(u, v)$ (once M(u, v) is specified). Assume without loss of generality that G is a clique, since we can assign $\beta =0$ on nonexistent edges.

Let $H = {\mathrm {argmin}}_{F\subset G, 0< v(F) < v(G)}\varDelta (F)$, where ties are broken arbitrarily subject to H being an induced subgraph of G. Since $\varDelta (G)=0$,

$$\begin{aligned} \beta (H,G-H) = \varDelta (G) + \beta (H,G-H) = \varDelta (H) + \varDelta (G-H) \ge \varDelta (H), \end{aligned}$$

so for $u\in V(H), v\in V(G-H)$ we can define $M(u,v)\in [0,\beta (uv)]$ such that $M(H,G-H)=\varDelta (H)$. For $u\in V(H)$ let $\alpha _H(u) = \alpha (u) - M(u,G-H)$, and let $\varDelta _H$ be the restriction of $\alpha _H - \beta$ to subgraphs of H. For any $\emptyset \subset F\subseteq H$,

$$\begin{aligned} \varDelta _H(F) = \varDelta (F) - M(F,G-H) \ge \varDelta (F) - M(H,G-H) \ge \varDelta (H) - M(H,G-H) = 0, \end{aligned}$$

with equality if $F=H$. Therefore $\varDelta _H$ is a threshold weighting on H. Recursively define a restriction of M to $V(H)\times V(H)$ such that this restriction is a Markov Chain on H that is equivalent to $\varDelta _H$.

For $u \in V(G-H), v \in V(H)$ let $M(u,v) = \beta (uv) - M(v,u)$. For $u \in V(G-H)$ let $\alpha _{G-H}(u) = \alpha (u) - M(u,H)$, and let $\varDelta _{G-H}$ be the restriction of $\alpha _{G-H} - \beta$ to subgraphs of $G-H$. Then,

$$\begin{aligned} \varDelta _{G-H}(G-H)&= \varDelta (G-H) - M(G-H, H) = \varDelta (G-H) - \beta (G-H, H) + M(H, G-H) \\&= \varDelta (G-H) - \beta (G-H, H) + \varDelta (H) = \varDelta (G) = 0. \end{aligned}$$

For any $\emptyset \subset F\subset G-H$, if $v(F) < v(G-H)$ then

$$\begin{aligned} \varDelta _{G-H}(F) = \varDelta (F)-M(F,H) \ge \varDelta (F)-\beta (F,H) \ge \varDelta (G[V(H), V(F)])-\varDelta (H) \ge 0, \end{aligned}$$

and if $v(F) = v(G-H)$ then $\varDelta _{G-H}(F) \ge \varDelta _{G-H}(G-H) = 0$. Therefore $\varDelta _{G-H}$ is a threshold weighting on $G-H$. Recursively define a restriction of M to $V(G-H)\times V(G-H)$ such that this restriction is a Markov Chain on $G-H$ that is equivalent to $\varDelta _{G-H}$.

We now verify that $M(u,G) = \alpha (u)$ for all u; the other requirements follow easily by induction. If $u \in V(H)$ then $M(u,H) = \alpha _H(u)$ by induction, and $M(u,G-H) = \alpha (u) - \alpha _H(u)$ by the definition of $\alpha _H$. Similarly, if $u \in V(G-H)$ then $M(u,G-H) = \alpha _{G-H}(u)$ and $M(u,H) = \alpha (u) - \alpha _{G-H}(u)$. Therefore $M(u,G) = M(u,H) + M(u,G-H) = \alpha (u)$ for all u. □

Appendix 2: Proof that $\kappa \left( K_{q}^{d}\right)$ is $O(q^d/d)$ for all q

The proof below is self-contained; however in places with clear analogues in Sect. 5.2 we will give less detailed explanations of the intermediate steps and intuition.

Fix q and d. Let a query tree be a binary tree in which each node is labeled with some $U_1 \times \cdots \times U_d$ where each $U_i \subseteq [q]$. The root is labeled with $[q]^d$, each leaf is labeled with a singleton set, and for any interior node N labeled with $U_1 \times \cdots \times U_d$ there exist $i \in [d]$ and $k \in U_i$ such that the left and right children of N are labeled with $U_1 \times \cdots \times U_{i-1} \times (U_i - k) \times U_{i+1} \times \cdots \times U_d$ and $U_1 \times \cdots \times U_{i-1} \times \{k\} \times U_{i+1} \times \cdots \times U_d$ respectively. (In the latter case, $U_i$ necessarily has at least two elements.)

With respect to an implicit query tree T, let $\ell _0, \dotsc , \ell _{q^d-1}$ be the leaves in increasing order from left to right, and for $0 \le a \le q^d$ let $G(a) = K_{q}^{d}[\ell _0, \dotsc , \ell _{a-1}]$. Let $\mu _T = \max _a \varDelta _{{{\mathrm {o}}}}(G(a))$ and let $\mu$ be the maximum of $\mu _T$ over all query trees T. For a threshold weighting $\varDelta \in \theta \left( K_{q}^{d}\right)$ and $H \subseteq K_{q}^{d}$ let $\kappa _\varDelta (H) = \min _{S\in {{\mathrm {Seq}}}(H)}\max _{F\in S}\varDelta (F)$, and if H is a single-vertex graph or the empty graph then let $\kappa _\varDelta (H)=0$. By Theorem 3.8(i) it suffices to prove that $\kappa _\varDelta \left( K_{q}^{d}\right)$ is $O(q^d/d)$ for all threshold weightings $\varDelta = (1,\beta )$.

Lemma 2

Fix a query tree T. Let $0 \le a < b \le q^d$ such that $\ell _a, \dotsc , \ell _{b-1}$ are exactly the leaves descended from some node of T. Let $\varDelta = (1,\beta ) \in \theta \left( K_{q}^{d}\right)$ such that $\beta (G(a)) \ge \beta _{{{\mathrm {o}}}}(G(a))$ and $\beta (G(b)) \ge \beta _{{{\mathrm {o}}}}(G(b))$, and $\kappa _\varDelta (G(a)) \le 2\mu$. Then $\kappa _\varDelta (G(b)) \le 2\mu$.

Proof

Let N be the node of T such that the leaves descended from N are exactly $\ell _a, \dotsc , \ell _{b-1}$. Let $U_1 \times \cdots \times U_d$ be the label of N. Let $B = G(b) - G(a) = K_{q}^{d}[U_1 \times \cdots \times U_d] = K_{q}^{d}[\ell _a, \dotsc , \ell _{b-1}]$.

The proof is by induction on $\sum _i (|U_i|-1)$, for all query trees T. (It follows from the definitions that $|U_i|\ge 1$, with equality for all i if and only if N is a leaf.) In the inductive step we handle separately the cases where $\beta (B) \ge \beta _{{{\mathrm {o}}}}(B)$ and $\beta (B) < \beta _{{{\mathrm {o}}}}(B)$. The base case is a special case of the former because if B is a single vertex then $\beta (B)$ and $\beta _{{{\mathrm {o}}}}(B)$ are both zero.

Case 1 $\beta (B) \ge \beta _{{{\mathrm {o}}}}(B)$. If B is a single vertex then $\kappa _\varDelta (B) = 0 \le 2\mu$; we now obtain the same result in the case where B is not a single vertex. Let ${\mathscr {I}} = \{i\in [d] \mid |U_i|\ge 2\}$, and note that ${\mathscr {I}}$ is nonempty. For $i \in {\mathscr {I}}$ and $k \in U_i$ let $B(i,k) = B[v \in V(B) \mid v_i \ne k]$. Choose a pair $({\mathbf {i}}, {\mathbf {k}})$ uniformly at random out of all pairs (i, k) such that $i \in {\mathscr {I}}$ and $k \in U_i$. Each edge in B is also in $B({\mathbf {i}}, {\mathbf {k}})$ with the same probability $p = 1 - (|\mathscr {I}|+1)/\sum _{i\in {\mathscr {I}}}|U_i|$ (since adjacent vertices differ in a unique coordinate), so by linearity of expectation,

$$\begin{aligned} {\mathbb {E}}[\beta (B({\mathbf {i}}, {\mathbf {k}}))] = p \beta (B) \ge p \beta _{{{\mathrm {o}}}}(B) = {\mathbb {E}}[\beta _{{{\mathrm {o}}}}(B({\mathbf {i}}, {\mathbf {k}}))]. \end{aligned}$$

Therefore $\beta (B(i,k)) \ge \beta _{{{\mathrm {o}}}}(B(i,k))$ for some fixed i and k.

Now our claim that $\kappa _\varDelta (B) \le 2\mu$ follows from two applications of the inductive hypothesis. Let $T^\prime$ be any query tree in which the sequence of labels along the path from the root to the leftmost leaf includes $U_1 \times \cdots \times U_d$ followed by $U_1 \times \cdots \times (U_i - k) \times \cdots \times U_d$. With respect to $T^\prime$, an application of the inductive hypothesis with $a^\prime = 0$ and $b^\prime = (1-1/|U_i|) \prod _j |U_j|$ reveals that $\kappa _\varDelta (B(i,k)) \le 2\mu$, and then an application of the inductive hypothesis with $a^{\prime \prime } = (1-1/|U_i|) \prod _j |U_j|$ and $b^{\prime \prime } = \prod _j |U_j|$ ($= b-a$) reveals that $\kappa _\varDelta (B) \le 2\mu$.

The rest of the proof is essentially identical to the case $q = 2$. Let S be an optimal (with respect to $\varDelta$) union sequence for G(a), followed by an optimal union sequence for B, followed by $G(a) \cup B, G(a)\cup B\cup e_1, \dotsc , G(a)\cup B\cup \{e_j\}$, where the $\{e_j\}$ are the edges between G(a) and B in $K_{q}^{d}$. (If G(a) or B lacks edges then omit certain graphs from this sequence.) Then,

$$\begin{aligned} \max _{H\in S}\varDelta (H) \le \max (\kappa _\varDelta (G(a)), \kappa _\varDelta (B), \varDelta (G(a))+\varDelta (B)). \end{aligned}$$

We proceed to bound each of these three terms by $2\mu$, completing the proof. We have assumed that $\kappa _\varDelta (G(a)) \le 2\mu$, and proved that $\kappa _\varDelta (B) \le 2\mu$. We have also assumed that $\beta (G(a)) \ge \beta _{{{\mathrm {o}}}}(G(a))$, and since $\varDelta$ and $\varDelta _{{{\mathrm {o}}}}$ both evaluate to 1 on all vertices, it follows that $\varDelta (G(a)) \le \varDelta _{{{\mathrm {o}}}}(G(a)) \le \mu$ (with the last step following from the definition of $\mu$). Similarly, $\varDelta (B) \le \varDelta _{{{\mathrm {o}}}}(B) \le \mu$, and it follows that $\varDelta (G(a)) + \varDelta (B) \le 2\mu$.

Case 2 $\beta (B) < \beta _{{{\mathrm {o}}}}(B)$. For $i \in {\mathscr {I}}$ and $k \in U_i$ let $H(i,k) = K_{q}^{d}[\ell _0, \dotsc , \ell _{a-1}, V(B(i,k))]$ (where ${\mathscr {I}}$ and B(i, k) are defined as above). Choose a pair $({\mathbf {i}}, {\mathbf {k}})$ uniformly at random out of all pairs (i, k) such that $i \in {\mathscr {I}}$ and $k \in U_i$. Then there exist $p_0> p_1 > p_2 \ge 0$ (specifically, $p_0 = 1$, $p_1 = 1-|{\mathscr {I}}|/\sum _{i\in {\mathscr {I}}}|U_i|$, and $p_2 = 1 - (|{\mathscr {I}}|+1)/\sum _{i\in {\mathscr {I}}}|U_i|$) such that

$$\begin{aligned} {\mathbb {E}}[\beta (H({\mathbf {i}},{\mathbf {k}}))]&= p_0\beta (G(a)) + p_1\beta (G(a),B) + p_2\beta (B) \\&= (p_0-p_1)\beta (G(a)) + p_1\beta (G(b)) + (p_2-p_1)\beta (B) \\&> (p_0-p_1)\beta _{{{\mathrm {o}}}}(G(a)) + p_1\beta _{{{\mathrm {o}}}}(G(b)) + (p_2-p_1)\beta _{{{\mathrm {o}}}}(B) \\&= {\mathbb {E}}[\beta _{{{\mathrm {o}}}}(H({\mathbf {i}},{\mathbf {k}}))]. \end{aligned}$$

Therefore $\beta (H(i,k)) > \beta _{{{\mathrm {o}}}}(H(i,k))$ for some fixed i and k.

Preparing to apply the inductive hypothesis, let $T^{\prime \prime }$ be any query tree structured and labeled exactly like T on all ancestors of $\ell _j$ for all $j<a$, and on all ancestors of N, but now the left child of N is labeled with $U_1 \times \cdots \times (U_i - k) \times \cdots \times U_d$. With respect to $T^{\prime \prime }$, an application of the inductive hypothesis with $a^\prime = a$ and $b^\prime = a + (1-1/|U_i|) \prod _j |U_j|$ reveals that $\kappa _\varDelta (G(a + (1-1/|U_i|) \prod _j |U_j|)) \le 2\mu$, and a second application of the inductive hypothesis with $a^{\prime \prime } = a + (1-1/|U_i|) \prod _j |U_j|$ and $b^{\prime \prime } = b$ ($= a + \prod _j|U_j|$) reveals that $\kappa _\varDelta (G(b)) \le 2\mu$. □

Lemma 3

$\mu$ is $O(q^d/d)$.

Proof

We use a cruder bound here than in the case $q=2$. Let T be an arbitrary query tree and $a \in [q^d]$. Let $N_0$ be the nearest common ancestor of $\ell _0$ and $\ell _{a-1}$. If $N_0$ is a leaf then clearly $\varDelta _{{{\mathrm {o}}}}(G(a))$ is $O(q^d/d)$, so assume otherwise. Let $N_L$ and $N_R$ be the left and right children of $N_0$, and note that $\ell _{a-1}$ is a descendant of $N_R$. By Eq. (1), since $K_{q}^{d}$ is $(q-1)d$-regular it suffices to prove that $e(G(a), K_{q}^{d} - G(a))$ is $O(q^{d+1})$. Suppose $N_0$ is labeled with $U_1 \times \cdots \times U_d$ and $N_L$ is labeled with $U_1 \times \cdots \times (U_i - k) \times \cdots \times U_d$. Since each vertex in G(a) is a descendant of $N_0$, all edges between G(a) and $K_{q}^{d} - G(a)$ are in one of the following classes:

• 1. Edges (in $K_{q}^{d}$) between a leaf descended from $N_0$ and a leaf not descended from $N_0$. Each leaf descended from $N_0$ is adjacent to $\sum _{j=1}^d (q-|U_j|)$ leaves not descended from $N_0$, so this amounts to $(dq - \sum _j |U_j|) \prod _j |U_j|$ edges in total. By the AM-GM inequality, this is at most

  $$\begin{aligned} \left( \frac{(dq-\sum _j |U_j|) + \sum _j |U_j|}{d+1}\right) ^{d+1} = \left( \frac{dq}{d+1}\right) ^{d+1} = q^{d+1}\left( 1 - \frac{1}{d+1}\right) ^{d+1} < q^{d+1}/e. \end{aligned}$$

• 2. Edges (in $K_{q}^{d}$) between a leaf descended from $N_L$ and a leaf descended from $N_R$. Each leaf descended from $N_L$ is adjacent to one leaf descended from $N_R$, so this amounts to at most $\prod _j |U_j| \le q^d$ edges in total.

• 3. Edges (in $K_{q}^{d}$) between a leaf descended from $N_R$ that’s in G(a), and a leaf descended from $N_R$ that’s in $K_{q}^{d} - G(a)$. This is at most what the value of $\mu$ would be if d were $d-1$ instead. (Eliminate coordinate i, and replace $U_j$ with [q] for all $j\ne i$.)

The total number of edges in all classes is therefore $O(q^{d+1} + q^d + \cdots ) = O(q^{d+1})$. □

Finally, it follows from Lemmas 2 and 3 that $\kappa \left( K_{q}^{d}\right) \le 2\mu \le O(q^d/d)$.

Remark

The above argument holds even if we relax the definition of threshold weightings to allow $\varDelta$ to take on negative values (where all definitions in terms of threshold weightings are with respect to this revised definition).

Appendix 3: Properties of Threshold Weightings and Threshold Random Graphs

Lemma 4

If $A \subseteq U \subseteq G$ are fixed graphs, $\varDelta \in \theta (G)$, and $\varDelta (A) < \varDelta (H)$ for all $H \in (A, U]$, then conditional on ${\mathscr {A}} \in {{\mathrm {Sub}}}_{{\mathbf {X}}_{\varDelta , n}}(A)$, there are at least $n^{\varDelta (U) - \varDelta (A)}(1-o(1))$ U-extensions of ${\mathscr {A}}$ a.a.s.

Li et al. [17] stated without proof that a similar result can be obtained using Janson’s Inequality [16]:

Fact 5

(Janson’s inequality) Let ${\mathbf {B}}_1, \ldots , {\mathbf {B}}_{\ell }$ be independent Bernoulli random variables, let $W_1, \ldots , W_k \subseteq [\ell ]$, and for $i\in [k]$ let ${\mathbf {I}}_i = \prod _{j\in W_i} {\mathbf {B}}_j$. Also for $i,j\in [k], i\ne j$ let $i\sim j$ if $W_i \cap W_j \ne \emptyset$. Let ${\mathbf {S}} = \sum _i {\mathbf {I}}_i$ and $\mu = {\mathbb {E}}[{\mathbf {S}}]$. Then for all $0 \le \epsilon \le 1$,

$$\begin{aligned} P({\mathbf {S}} \le (1-\epsilon )\mu ) \le \exp \left( -\frac{\epsilon ^2}{2} \cdot \frac{\mu ^2}{\mu + \sum _{i \sim j}{\mathbb {E}}[{\mathbf {I}}_i\mathbf {I}_j]}\right) . \end{aligned}$$

Proof of Lemma 2

Let ${\mathscr {U}}_1, \dotsc , {\mathscr {U}}_k$ be the possible U-extensions of ${\mathscr {A}}$, and let ${\mathbf {I}}_i = {\mathbb {1}}\!\{\mathscr {U}_i \subseteq {\mathbf {X}}\}$. Define $\mu$ as in Fact 4; clearly $\mu = n^{\varDelta (U) - \varDelta (A)}$, by reasoning similar to the proof of Lemma 3.5. If $i \sim j$ then the projection of ${\mathscr {U}}_i \cap {\mathscr {U}}_j$ onto U must be some graph in (A, U), so

$$\begin{aligned} \sum _{i \sim j}{\mathbb {E}}[{\mathbf {I}}_i {\mathbf {I}}_j] \le \sum _{{H \in (A, U)}} \mu n^{\varDelta (U)-\varDelta (H)} = \mu ^2 \sum _{{H \in (A, U)}} n^{\varDelta (A)-\varDelta (H)} = o(\mu ^2). \end{aligned}$$

Since $\mu$ is also $o(\mu ^2)$, it follows that $\mu ^2\big /\left( \mu + \sum _{i \sim j}{\mathbb {E}}[{\mathbf {I}}_i{\mathbf {I}}_j]\right) \ge \mu ^2/o(\mu ^2) = \omega (1)$, and the result follows from Fact 4. □

Lemma 6

For all $A\subseteq B\subseteq F\subseteq H\subseteq G$ and $\varDelta \in \theta (G)$,

$$\begin{aligned} \varDelta ^*_H(B)-\varDelta ^*_H(A) \le \varDelta ^*_F(B)-\varDelta ^*_F(A). \end{aligned}$$

Proof

Since $B \subseteq \varGamma _F(B) \subseteq \varGamma _H(A) \cup \varGamma _F(B)$ it follows that $\varDelta ^*_H(B) \le \varDelta (\varGamma _H(A)\cup \varGamma _F(B))$, and since $A \subseteq \varGamma _H(A)$ and $A\subseteq B\subseteq \varGamma _F(B)$ it follows that $\varDelta ^*_F(A) \le \varDelta (\varGamma _H(A)\cap \varGamma _F(B))$. So by Lemmas 6.5 and 6.7,

$$\begin{aligned} \varDelta ^*_H(B) + \varDelta ^*_F(A)&\le \varDelta (\varGamma _H(A) \cup \varGamma _F(B)) + \varDelta (\varGamma _H(A) \cap \varGamma _F(B)) \\&= \varDelta (\varGamma _H(A)) + \varDelta (\varGamma _F(B)) \\&= \varDelta ^*_H(A) + \varDelta ^*_F(B). \end{aligned}$$

□

Lemma 7

Let $\varDelta \in \theta (G)$ and assume $L \cap R \subseteq A \subseteq B \subseteq L \subseteq G$ and $L\cap R \subseteq C \subseteq R \subseteq G$. Then, $\varDelta ^*_{L\cup R}(B\cup C)-\varDelta ^*_{L\cup R}(A\cup C) = \varDelta ^*_L(B)-\varDelta ^*_L(A)$.

Proof

For all $F\in [A,L]$ and $H\in [C,R]$,

$$\begin{aligned} F\cap H&\subseteq L\cap R&(F\subseteq L{\text { and }}H\subseteq R)\\&\subseteq A\cap C&{\text {(by assumption)}}\\&\subseteq F\cap H,&(A\subseteq F{\text { and }}C\subseteq H) \end{aligned}$$

so by Lemma 6.5,

$$\begin{aligned} \varDelta ^*_{L\cup R}(A\cup C)&= \min _{{\begin{array}{c} A\subseteq F\subseteq L \\ C\subseteq H\subseteq R \end{array}}}\varDelta (F\cup H) = \min _{{\begin{array}{c} A\subseteq F\subseteq L \\ C\subseteq H\subseteq R \end{array}}}(\varDelta (F)+\varDelta (H)-\varDelta (F\cap H)) \\&= \min _{{A\subseteq F\subseteq L}}\varDelta (F) + \min _{{C\subseteq H\subseteq R}}\varDelta (H)-\varDelta (L\cap R) = \varDelta ^*_L(A) + \varDelta ^*_R(C)-\varDelta (L\cap R). \end{aligned}$$

The same reasoning applies with B in place of A, so

$$\begin{aligned} \varDelta ^*_{L\cup R}(A\cup C) - \varDelta ^*_L(A) = \varDelta ^*_R(C) - \varDelta (L\cap R) = \varDelta ^*_{L\cup R}(B\cup C) - \varDelta ^*_L(B). \end{aligned}$$

□