Kiel University, Kiel,
Germanybrinkop.edu@gmail.comhttps://orcid.org/0000-0002-7791-2353 Kiel
University, Kiel<EMAIL_ADDRESS>kiel.dehttps://orcid.org/0000-0001-8358-6796 Hauke Brinkop Theory of
computation Fixed parameter tractability This work was partially supported by
DFG Project Fein-granulare Komplexität und Algorithmen für Scheduling und
Packungen, JA 612 /25-1

# Solving Cut-Problems in Quadratic Time for Graphs With Bounded Treewidth

Hauke Brinkop  Klaus Jansen

###### Abstract

In the problem (Unweighted) Max-Cut we are given a graph $G=(V,E)$ and asked
for a set $S\subseteq V$ such that the number of edges from $S$ to $V\setminus
S$ is maximal. In this paper we consider an even harder problem: (Weighted)
Max-Bisection. Here we are given an undirected graph $G=(V,E)$ and a weight
function $w\colon E\to\mathds{Q}_{>0}$ and the task is to find a set
$S\subseteq V$ such that (i) the sum of the weights of edges from $S$ is
maximal; and (ii) $S$ contains $\left\lceil\frac{n}{2}\right\rceil$ vertices
(where $n=\lvert V\rvert$). We design a framework that allows to solve this
problem in time $\operatorname{\mathcal{O}}(2^{t}n^{2})$ if a tree
decomposition of width $t$ is given as part of the input. This improves the
previously best running time for Max-Bisection of [8] by a factor $t^{2}$.
Under common hardness assumptions, neither the dependence on $t$ in the
exponent nor the dependence on $n$ can be reduced [8, 6, 15]. Our framework
can be applied to other cut problems like Min-Edge-Expansion, Sparsest-Cut,
Densest-Cut, $\beta$-Balanced-Min-Cut, and Min-Bisection. It also works in the
setting with arbitrary weights and directed edges.

###### keywords:

Max-Bisection, Max-Cut, Min-Bisection, Sparsest-Cut, Densest-Cut, Min-Edge-
Expansion, Graph Problems, Balanced-Min-Cut, FPT, Treewidth

###  1 Introduction

Unweighted Max-Cut is one of Karp’s 21 NP-complete problems [12]; given a
graph $G=(V,E)$ one is asked for a set $S\subseteq V$ such that the number of
edges from $S$ to $V\setminus S$ is maximal. Formally, a _cut_ is determined
by a set of vertices $S\subseteq V$ of a graph. The _size of a cut_ is given
by the number of edges from $S$ to $V\setminus S$. We denote these edges as
$\partial S$ and, for the sake of shortness, if $S=\\{v\\}$ for some $v$, we
write $\partial v$ instead of $\partial S=\partial\\{v\\}$. If the graph is
weighted, the size of the cut is given by the sum of the edge weights
$w(\partial S)\coloneqq\sum_{e\in\partial S}w(e)$ instead of their number
$\lvert\partial S\rvert$. In this paper we consider different cut problems for
directed and weighted graphs[i][i][i]The undirected and unweighted versions
can easily be modelled as directed and weighted by setting each edge weight to
$1$ and by replacing each undirected edge between vertices $v_{1}$ and $v_{2}$
by two directed edges, $v_{1}v_{2}$ and $v_{2}v_{1}$., more precisely Max-Cut,
$\beta$-Balanced-Min-Cut, Max-Bisection, Min-Bisection, Min-Edge-Expansion,
(uniform) Sparsest-Cut, and Densest Cut. See Table 1 for precise formulations
of these problems.

Observe that Densest-Cut and Sparsest-Cut can easily be reduced on each other
in time $\operatorname{\mathcal{O}}(n^{2})$ (where $n=\lvert V\rvert$) using
the complementary graph [3]; however, this reduction might change the
treewidth and the corresponding decomposition, hence we have to consider both
problems individually.

Name |  Weights |  Objective
---|---|---
Max-Cut |  arbitrary |  $\displaystyle\max_{S\subseteq V}w(\partial S)$
$\beta$-Balanced-Min-Cut [7] |  non-negative |  $\displaystyle\min_{\begin{subarray}{c}S\subseteq V\\\ \beta\cdot\lvert V\rvert\leq\lvert S\rvert\leq(1-\beta)\cdot\lvert V\rvert\end{subarray}}\hskip-20.00003ptw(\partial S)$
Max-Bisection [10] |  non-negative |  $\displaystyle\max_{\begin{subarray}{c}S\subseteq V\\\ \big{\lvert}\lvert S\rvert-\lvert V\setminus S\rvert\big{\rvert}\leq 1\end{subarray}}w(\partial S)$
Min-Bisection [10] |  non-negative |  $\displaystyle\min_{\begin{subarray}{c}S\subseteq V\\\ \big{\lvert}\lvert S\rvert-\lvert V\setminus S\rvert\big{\rvert}\leq 1\end{subarray}}w(\partial S)$
Min-Edge-Expansion [16] |  non-negative |  $\displaystyle\min_{\begin{subarray}{c}\emptyset\neq S\subseteq V\\\ \lvert S\rvert\leq\lvert V\setminus S\rvert\end{subarray}}\frac{w(\partial S)}{\lvert S\rvert}$
Sparsest-Cut [3] |  non-negative |  $\displaystyle\min_{\emptyset\neq S\subsetneq V}\frac{w(\partial S)}{\lvert S\rvert\cdot\lvert V\setminus S\rvert}$
Densest-Cut [3] |  non-negative |  $\displaystyle\max_{\emptyset\neq S\subsetneq V}\frac{w(\partial S)}{\lvert S\rvert\cdot\lvert V\setminus S\rvert}$
Table 1: Problems that we solve in quadratic time.

We want to point out that if negative edge weights are allowed, as they are in
our algorithm, Max-Bisection and Min-Bisection coincide. This does not hold
for Max-Cut and its corresponding minimization variant; Min-Cut is solvable in
polynomial time. We call those more general variants of the problem, where we
get rid of the non-negativity restrictions, Max-Bisection’, $\beta$-Balanced-
Min-Cut’, Min-Edge-Expansion’, Sparsest-Cut’, and Densest-Cut’. As we will
see, our framework is able to solve these more general variants of the
problems.

Many graph problems are in FPT if parametrized by treewidth. This holds
especially for the problems mentioned above [3, 8, 6, 11]. The corresponding
algorithms usually assume that a tree decomposition with
$\operatorname{\mathcal{O}}(n)$ (or a similar bound like
$\operatorname{\mathcal{O}}(nt)$) nodes of width $t$ is given as part of the
input; we will later see why that is a reasonable assumption and what we can
do if a tree decomposition is not given. We show that in the above setting,
all aforementioned problems can be solved in time
$\operatorname{\mathcal{O}}(2^{t}n^{2})$.

###  2 Related Work

[10] proposed an algorithm for Max-Bisection and Min-Bisection that runs in
time $\operatorname{\mathcal{O}}(2^{t}n^{3})$ for a graph with $n$ vertices,
given a tree decomposition of width $t$ with $\operatorname{\mathcal{O}}(n)$
nodes[ii][ii][ii]The upper bound on the number of nodes occurs only implicitly
in their work within the analysis of their algorithm’s running time.. They
transform the tree decomposition into a so-called _nice tree decomposition_
[14] and then formulate a dynamic program over the nodes of the tree
decomposition. The bottleneck of their analysis are nodes that have more than
one child, the so-called _join nodes_. There might be $\Omega(n)$ join nodes
and for each the dynamic program might take time $\Omega(2^{t}n^{2})$ to
compute all the entries. [6] have been able to improve the running
time[iii][iii][iii]To be precise, they consider Min-Bisection; however, in
their paper as well as in [10], all arguments work for both problems. in its
dependence on $n$ by balancing the tree decomposition and recognizing that the
entries in join nodes can be computed via $(\max,+)$-convolution; this yields
a running time of $\operatorname{\mathcal{O}}(8^{t}t^{5}n^{2}\log n)$. [8]
proved that the algorithm of [10] does in fact run in time
$\operatorname{\mathcal{O}}(2^{t}(nt)^{2})$, using a clever idea to improve
the analysis: while for a single join node computing all entries of the
dynamic program might take $\Omega(2^{t}n^{2})$, the overall time for all join
nodes altogether is $\operatorname{\mathcal{O}}(2^{t}(nt)^{2})$.

[15] proved that Max-Cut (without a tree decomposition given as part of the
input) cannot be solved in time
$\operatorname{\mathcal{O}}^{(}(2-\varepsilon)^{t}\operatorname{poly}n)$ for
any $\varepsilon>0$ assuming the _Strong Exponential Time Hypothesis (SETH)_
[9, 4]. It is not hard to see that this result can be extended to the case
where a tree decomposition is part of the input – for the sake of
completeness, we include the corresponding proof in the appendix. By adding
isolated vertices, this result can also be applied to Max-Bisection and Min-
Bisection [8]. [6] proved that Min-Bisection (and hence Max-Bisection’) cannot
be solved in truly subquadratic time, that is
$\operatorname{\mathcal{O}}(n^{2-\varepsilon})$ for some $\varepsilon>0$, even
if a tree decomposition of width $1$ is given as part of the input, unless
$(\min,+)$-convolution can be solved in truly subquadratic time, which is
considered unlikely [5].

Given a tree decomposition of width $t$ with $\operatorname{\mathcal{O}}(nt)$
nodes, in time $\operatorname{\mathcal{O}}(2^{t}n^{3})$ the problems Sparsest-
Cut [3], Densest-Cut [3], and Min-Edge-Expansion [11] can be solved. To our
knowledge, those are the best running times achieved so far.

##### Our Contribution & Organization Of This Paper

In section 4 we show how to improve the running time by a factor $t^{2}$ for
Max-Bisection. In section 5 we then generalize this to a framework which can
be used to solve different cut problems in time
$\operatorname{\mathcal{O}}(2^{t}n^{2})$ (compare Table 1). Some problems
(like Sparsest Cut) are improved by a factor $n$, which is substantial when
$t$ is small. In section 6 we eventually show how the framework can be used to
solve aforementioned problems, including the proofs that the corresponding
models are correct.

###  3 Preliminaries

Notation For tuples we write $(a,b)\oplus(c,d)=(a+c,b+d)$ (and analogously
define $\ominus$). We write $\pi$ to denote the projection on tuples, that is:
for a tuple $t$ and an index $i$, $\pi_{i}(t)$ is the $i$-th component of $t$.

For a set $M$ and a number $k$ we write $\binom{M}{k}=\set{M^{\prime}\subseteq
M}{\lvert M\rvert=k}$. For a graph edge from $v_{1}$ to $v_{2}$ we write
$v_{1}v_{2}$ for both, directed and undirected graphs. A rooted tree
$T=(V,r,E)$ is a graph $(V,E)$ that is connected, has no circles, and where
$r\in V$.

We use $n$ as abbreviation for $\lvert V\rvert$. By
$\bar{}\mathds{Q}\coloneqq\mathds{Q}\mathbin{\dot{\cup}}\\{\infty,-\infty\\}$
we denote the rational numbers with positive and negative infinity.

As already mentioned in the previous sections, we make use of _tree
decompositions_ , which are defined as follows:

######  Definition 1 (Tree decomposition).

Let $G=(V,E)$ be an undirected graph, $I$ be a finite set and $X=(X_{i})_{i\in
I}$ be a family of sets such that for any $i\in I$ one has $X_{i}\subseteq V$.
Moreover, let $T=(I,r,H)$ be a rooted tree with root $r\in I$. Then
$(I,r,X,H)$ is called a _tree decomposition_ of $G$ if and only if $T$ has the
following properties:

  1. (i)

Node coverage: Every vertex occurs in some $X_{i}$ for some $i\in I$ (and no
further vertices occur): $\bigcup_{i\in I}X_{i}=V$;

  2. (ii)

Edge coverage: for every edge $v_{1}v_{2}\in E$ there is a node $i\in I$ such
that both, $v_{1}$ and $v_{2}$, are contained in $X_{i}$;

  3. (iii)

Coherence: for every vertex $v\in V$ the subgraph $T-\set{i\in I}{v\notin
X_{i}}$ is connected.  $\lrcorner$

By convention the nodes of the graph $G$ are called _vertices_ while the nodes
of the tree are just called _nodes_. For a node $i\in I$ the set $X_{i}$ is
called a _bag_. The _width_ of a decomposition is the largest cardinality of
any of its bags minus 1. The minimum width among all decompositions of $G$ is
called the _treewidth_ of $G$. If the node set of a decomposition is
sufficiently small, more precisely if $\lvert I\rvert\leq 4\cdot(\lvert
V\rvert+1)$, we call the decomposition _small_. A tree decomposition of a
directed graph is a tree decomposition of the underlying graph.

As the approaches mentioned before, our approach also makes use of a specific
kind of tree decompositions, which are of a very simple structure:

######  Definition 2 (Nice Tree Decomposition).

Let $G=(V,E)$ be an undirected graph and $(I,r,X,H)$ a tree decomposition of
$G$. We call $(I,r,X,H)$ a _nice tree decomposition_ if and only if for any
$i\in I$ the node $i$ is of one of the following forms:

  1. (i)

Leaf node: $i$ has no child node in $T$, that is $i$ is a _leaf_ of the tree
$T$;

  2. (ii)

Forget node: $i$ has exactly one child node $j\in I$ in $T$ and
$X_{i}\mathbin{\dot{\cup}}\\{v\\}=X_{j}$ for some $v\in X_{j}$, that is $i$
_forgets_ a vertex from $X_{j}$;

  3. (iii)

Introduce node: $i$ has exactly one child $j\in I$ in $T$ and
$X_{i}=X_{j}\mathbin{\dot{\cup}}\\{v\\}$ for some $v\in V\setminus X_{j}$,
that is $i$ _introduces_ a new vertex $v\in V\setminus X_{j}$; or

  4. (iv)

Join node: $i$ has exactly two child nodes $j\in I$, $k\in I$, $j\neq k$, in
$T$ such that $X_{i}=X_{j}=X_{k}$, that is _joining_ two branches of the tree
$T$.  $\lrcorner$

The conversion of a tree decomposition into a nice tree decomposition can be
done in time $\operatorname{\mathcal{O}}(nt^{2})$ as long as the number of
nodes of the decomposition is at most linear in the number of vertices.

######  Lemma 3 ([14, Lemma 13.1.3, p. 150]).

Given a small tree decomposition of a graph $G$ with width $t$ one can find a
nice tree decomposition of $G$ with width $t$ and with at most $4n$ nodes in
$\operatorname{\mathcal{O}}(nt^{2})$ time, where $n$ is the number of vertices
of $G$.  $\lrcorner$

It is reasonable to assume that given tree decompositions are small for the
following reason: No matter how the tree decomposition is constructed, it is
always possible to incorporate the following mechanism without asymptotically
increasing the running time: If a node $j$ with parent $i$ has $X_{j}\subseteq
X_{i}$, merge those nodes.

We claim that we now can only have $n$ edges. This is because for every node
$j$ with parent $i$, we have $X_{j}\not\subseteq X_{i}$; this means, at least
one vertex has to disappear when going from $j$ up to $i$. Since by Coherence
every vertex can disappear at most once[iv][iv][iv] It might disappear on
multiple leaf-root-paths; however, the node at which a vertex disappears, is
the same on each of those leaf-root-paths. , this upper bounds the number of
edges by $n$ and hence the number of nodes by $n+1$.

Note that this also allows us to easily extend our approach to the case where
a tree decomposition with $\operatorname{\mathcal{O}}(nt)$ nodes is given as
part of the input: simply apply the procedure described above to reduce the
number of nodes.

###  4 Max-Bisection: From $\operatorname{\mathcal{O}}(2^{t}n^{3})$ to
$\operatorname{\mathcal{O}}(2^{t}n^{2})$

In this section we focus on our idea on how the running time of the algorithm
of [10] for Max-Bisection can be improved to
$\operatorname{\mathcal{O}}(2^{t}n^{2})$, incorporating the idea of [8].

The algorithm of [10] is a subroutine used in their PTAS for the Max-Bisection
problem on planar graphs. Their approach uses Baker’s technique (see [1])
where the idea is to solve the problem for $k$-outerplanar graphs (instead of
general planar graphs), for a $k$ depending only on the approximation factor,
and then combining the results. Note that $k$-outerplanar graphs have a
treewidth in $\operatorname{\mathcal{O}}(k)$ [13]. For those $k$-outerplanar
graphs, the problem is solved exactly using the aforementioned subroutine.
Since – as opposed to the general case – tree decompositions for
$k$-outerplanar graphs can be computed in time
$\operatorname{\mathcal{O}}(kn)$ [13], this subroutine gets tree decomposition
as part of its input; otherwise the running time of the subroutine would be
dominated by the computation of the decomposition.

Let us now focus on the subroutine. We will traverse the nice tree
decomposition bottom up in the algorithm of [10], hence the following
notations come in handy: For a node $i$ the set $Y_{i}$ contains all the
vertices appearing in bags associated with nodes below $i$. Moreover, we write
$F_{i}\coloneqq Y_{i}\setminus X_{i}$ to describe the set of vertices that
?have been forgotten? somewhere below $i$, that is, that they have appeared in
bag of some node $j$ below $i$, but are not contained in $X_{i}$. Due to 1
(iii), those vertices can never reoccur in any bag above $i$.

The algorithm of [10] uses a dynamic program to compute

$\displaystyle\mathcal{B}_{i}\colon\set{0,\dots,\lvert Y_{i}\rvert}\times
2^{X_{i}}\to\bar{}\mathds{Q}_{>0}$
$\displaystyle\mathcal{B}_{i}(\ell,S)=\max_{\begin{subarray}{c}\widehat{S}\subseteq
Y_{i}\\\ \lvert\widehat{S}\rvert=\ell\\\
S\subseteq\widehat{S}\end{subarray}}w(\partial\widehat{S}\cap Y_{i}^{2}),$ (1)

given a small nice tree decomposition of a weighted, undirected graph
$G=(V,E)$ with weight function $w\colon E\to\mathds{Q}_{>0}$. The idea is that
for a node $i$ the entry $\mathcal{B}_{i}(\ell,S)$ is the size of the largest
possible cut that consists of $\ell$ vertices from $Y_{i}$ and includes the
set $S\subseteq X_{i}$. As the table might have preimages $(\ell,S)$ where
there does not exist be a cut meeting the requirements above, $\infty$ and
$-\infty$ have to be used to deal with those – we omit further details.

For the root $r$ of the tree decomposition we can compute our optimal
objective value by iterating over all entries of $\mathcal{B}_{r}$ and picking
the best value where the number of vertices is in the feasible interval for
Max-Bisection.

The dynamic program traverses the decomposition bottom up. The bottleneck of
the running time comes from the time spent at join nodes – the values for each
node of any different type can be computed in time
$\operatorname{\mathcal{O}}(2^{t}n)$ using a simple DP. For a join node $i$
with left child $j$ and right child $k$, they use the following recurrence to
compute $\mathcal{B}_{i}$:

$\mathcal{B}_{i}(\ell,S)=\max_{\begin{subarray}{c}\lvert
S\rvert\leq\ell_{1}\leq\lvert V\rvert\\\ \lvert S\rvert\leq\ell_{2}\leq\lvert
V\rvert\\\ \ell_{1}+\ell_{2}-\lvert
S\rvert=\ell\end{subarray}}\big{(}\mathcal{B}_{j}(\ell_{1},S)+\mathcal{B}_{k}(\ell_{2},S)-w(\partial
S\cap(S\times(X_{i}\setminus S)))\big{)}$ (2)

We omit the details on how the necessary values of $w$ are computed in their
case; it suffices to see that a rough analysis of the equation above, assuming
that we are given the value of the $w$ expression, is
$\operatorname{\mathcal{O}}(n^{2})$ per entry for a single join node. It is
also easy to see that there are indeed instances where the computation of an
entry for $(\ell,S)$ takes $\Theta(n^{2})$ time. This yields an overall
running time of $\operatorname{\mathcal{O}}(2^{t}n^{3})$ as stated by [10].

[8] provided an improved analysis for the algorithm of [10]. They defined
$\nu_{i}$ to be the sum of all $\lvert X_{j}\rvert$ for nodes $j$ that are
below $i$. It is not hard to see that the running time for the computation of
a single entry of a join node $i$ with left child $j$ and right child $k$ can
be done in time $\operatorname{\mathcal{O}}(\nu_{j}\nu_{k})$. Using a labeling
argument they then proved that

$\sum\limits_{i\leavevmode\nobreak\ :\leavevmode\nobreak\ \text{join node with
children $j$,$k$}}\nu_{j}\nu_{k}\leq(nt)^{2}.$

Their idea is that after labeling the vertices in all bags (possibly giving
the same vertex different labels for different bags), every pair of those
labels can occur at at most one join node. The consequence of the above
statement is that the worst case for join nodes cannot occur too often;
overall, all entries of all join nodes can be computed in time
$\operatorname{\mathcal{O}}(2^{t}(nt)^{2})$.

Our approach is now to reformulate the recurrence by something that can be
thought of as an index shift; for each node $i$ we define a table

$\displaystyle\Gamma_{i}\colon\\{0,\dots,\lvert F_{i}\rvert\\}\times
2^{X_{i}}\to\mathds{Q}$
$\displaystyle\Gamma_{i}(\ell,S)\coloneqq\max_{\widehat{S}\in\binom{F_{i}}{\ell}}w\lparen\partial\lparen
S\mathbin{\dot{\cup}}\widehat{S}\rparen\cap Y_{i}^{2}\rparen.$ (3)

In comparsion to (4), there are two differences.

  1. 1.

The indices have a different meaning: In $\Gamma_{i}(\ell,S)$ we store the
value of the best cut (with respect to $f$) that consists of the set
$S\subseteq X_{i}$ and $\ell$ further vertices that _occur in bags below $i$,
but not in $X_{i}$_.

  2. 2.

The table’s size is now $\operatorname{\mathcal{O}}(\lvert F_{i}\rvert
2^{t})$; this is not only smaller but also for every entry $(\ell,S)$ there is
a cut consisting of $\ell$ vertices from $F_{i}$ and the vertices from $S$
(hence we do not have to consider those special cases of undefinedness as it
had to be done in [10]).

For the modified recursion, the join nodes are still the bottleneck; their
recurrence is[v][v][v]Since we only did an index shift, we can reuse the
recurrence from [10] by applying the same shift to it

$\Gamma_{i}(\ell,S)=\bigg{(}\max_{\begin{subarray}{c}0\leq\ell_{1}\leq\lvert
F_{j}\rvert\\\ 0\leq\ell_{2}\leq\lvert F_{k}\rvert\\\
\ell_{2}+\ell_{1}=\ell\end{subarray}}\big{(}\Gamma_{j}(\ell_{1},S)+\Gamma_{k}(\ell_{2},S)\big{)}\bigg{)}-w(\partial
S\cap Y_{i}^{2}).$

The key observation is that the running time is dominated by computing the
$\max$ expression[vi][vi][vi] Note that $\partial S$ can only take on
$\operatorname{\mathcal{O}}(2^{t})$ different values at some fixed node $i$.
We use a simple DP to precompute the $w(\cdot)$ terms efficiently (for a fixed
node in time $\operatorname{\mathcal{O}}(2^{t}n)$). , which depends linearly
on $\lvert F_{j}\rvert\cdot\lvert F_{k}\rvert=\lvert F_{j}\times F_{k}\rvert$.
We can now show that all of those occurring Cartesian products are disjunct:

######  Proposition 4.

For each pair $(v_{1},v_{2})\in V^{2}$ there is at most one join node $i$ with
left child $j$ and right child $k$ such that $(v_{1},v_{2})\in F_{j}\times
F_{k}$.  $\lrcorner$

###### Proof.

Proof by contradiction. Assume there was a join node $i^{\prime}\neq i$ with
left child $j^{\prime}$ and right child $k^{\prime}$ such that
$(v_{1},v_{2})\in F_{j^{\prime}}\times F_{k^{\prime}}$. Then, by Coherence,
either $i^{\prime}$ is below $i$ or $i$ is below $i^{\prime}$. We assume
without loss of generality that $i^{\prime}$ is below $i$. Moreover, we assume
without loss of generality that $i^{\prime}$ is somewhere in the _left_
subtree of $i$. As $(v_{1},v_{2})\in F_{j}\times F_{k}$ by assumption, we have
in particular $v_{2}\in F_{k}$, and, additionally taking into account that
$F_{j}\cap F_{k}=\emptyset$ by Coherence, $v_{1}\notin F_{k}$. Since
$i^{\prime}$ is in the left subtree of $i$, we also have
$F_{j^{\prime}}\subseteq F_{i^{\prime}}\subseteq F_{j}$, hence $v_{1}\notin
F_{j^{\prime}}$. This is a contradiction to $(v_{1},v_{2})\in
F_{j^{\prime}}\times F_{k^{\prime}}$. ∎

Using this statement we can now deduce that

$\sum\limits_{i\leavevmode\nobreak\ :\leavevmode\nobreak\ \text{join node with
children $j$,$k$}}\hskip-10.00002pt\lvert F_{j}\times
F_{k}\rvert=\left\lvert\mathop{\dot{\bigcup}}\limits_{i\leavevmode\nobreak\
:\leavevmode\nobreak\ \text{join node with children
$j$,$k$}}\hskip-10.00002pt\big{(}F_{j}\times F_{k})\right\rvert\leq\lvert
V^{2}\rvert=n^{2}.$ (4)

We can thus deduce the overall running time of computing all entries for all
join nodes is $\operatorname{\mathcal{O}}(2^{t}n^{2})$, as we need time
$\operatorname{\mathcal{O}}(2^{t}\lvert F_{j}\times F_{k}\rvert)$ for a single
join node.

As the running time for the other node types obviously remain unchanged, this
yields an algorithm with overall running time
$\operatorname{\mathcal{O}}(2^{t}n^{2})$ for Max-Bisection.

###  5 Our Framework

In this section we discuss how we can generalize the idea from the previous
section to other cut problems. More precisely, we present a framework that can
solve several cut-problems (for directed, arbitrarily-weighted graphs
$G=(V,E)$ with weight function $w:E\to\mathds{Q}$) in time
$\operatorname{\mathcal{O}}(2^{t}n^{2})$ if a small tree decomposition of
width $t$ is given as part of the input. Without loss of generality we assume
that this small tree decomposition is also a nice tree decomposition (if not,
we could simply use 3 to convert it accordingly in sufficiently small time).

The main obstacle is finding an abstraction of the algorithm for Max-Bisection
that maintains the running time, but also allows us tackle all the listed
problems. Especially extracting the formal arguments hidden implicitly in
existing algorithms turned out to be a non-trivial task.

For our framework, we assume that we are given an objective function
$f\colon\mathds{N}_{0}\times\mathds{Q}\to\bar{}\mathds{Q}$ that is either
monotonic or antitonic[vii][vii][vii]$x\leq y\implies f(a,x)\geq f(a,y)$ in
its second argument, and a validator function
$\Lambda\colon\mathds{N}_{0}\to\\{\mathrm{true},\mathrm{false}\\}$. We use a
function of arity 2 to be able to not only model Max-Bisection and similar,
but also e.g. Sparsest-Cut, where the objective depends on the size of the cut
_and_ the number of vertices selected. The validator function is needed e.g.
for Max-Bisection, as we somehow have to tell the framework which entries
correspond to feasible solutions and which are infeasible; for Max-Bisection
we would set $\Lambda(x)\coloneqq(\lvert x-(n-x)\rvert\leq 1)$. We assume that
both, $f$ and $\Lambda$, can be evaluated in time
$\operatorname{\mathcal{O}}(1)$.

Our task is now to compute an element of all _possible preimages_ (in the
sense: there exists a corresponding cut) $\Set{\Big{(}\lvert
S\rvert,\,w(\partial S)\Big{)}}{S\subseteq V,\,\Lambda(\lvert S\rvert)}$ of
the objective function $f$ that maximizes $f$. We can reformulate this task in
a more elegant way by introducing the total quasiorder
$(\sqsubseteq)\subseteq(\\{0,\dots,n\\}\times\mathds{Q})\mathbin{\dot{\cup}}\\{\bot\\})^{2}$
defined by

$a\sqsubseteq b\iff a=\bot\lor\big{(}a\neq\bot\neq b\land f(a)\leq
f(b)\big{)}.$

The intuition behind that quasiorder is as follows: if we compare two values
$a,b\neq\bot$, then $a\sqsubseteq b$ iff $f(a)\leq f(b)$, that is, we compare
(non-$\bot$) values by their image under $f$.

The idea of the new symbol $\bot$ is to represent the case where there is no
feasible solution and hence no possible preimage to $f$ as we have to deal
with that case, too.

Our task is now to compute (where $\bigsqcup$ is the supremum operator
regarding $\sqsubseteq$).

$\Phi=\bigsqcup_{\begin{subarray}{c}S\subseteq V\\\ \Lambda(\lvert
S\rvert)\end{subarray}}\Big{(}\lvert S\rvert,\,w(\partial S)\Big{)}.$ (5)

By definition, $\bot$ is the smallest element of our order, so if there is a
feasible solution, the result cannot be $\bot$.

From a strict mathematical perspective, Equation 5 is incorrect as in general
there is no such thing as a unique supremum for a total quasiorder (there
might be multiple possible preimages of $f$ taking on the optimal value).
Taking this into account would make the description of our approach way more
complicated, as we would need to reason about equivalence classes and
eventually give a recurrence to compute a representant of the class of element
optimizing the objective function. Thus, we identify elements and their
corresponding equivalence class (set of possible preimages that have the same
objective value) in this paper.

For the sake of shortness, for a subset of edges $M\subseteq E$ we write
$w_{i}(M)\coloneqq w(M\cap Y_{i}^{2})$. We set up the dynamic program similar
to the one for Max-Bisection, that is for a node $i$ we define

$\displaystyle\Gamma_{i}\colon\\{0,\dots,\lvert F_{i}\rvert\\}\times
2^{X_{i}}\to\\{0,\dots,n\\}\times\mathds{Q}$
$\displaystyle\Gamma_{i}(\ell,S)\coloneqq\bigsqcup_{\widehat{S}\in\binom{F_{i}}{\ell}}\Big{(}\ell+\lvert
S\rvert,\,w_{i}\lparen\partial\lparen
S\mathbin{\dot{\cup}}\widehat{S}\rparen\rparen\Big{)}.$ (6)

In comparison to section 4 there are two differences.

  1. 1.

An entry is no longer just the size of the corresponding cut, but a $2$-tuple
consisting of the number of vertices selected and the size of the cut.

  2. 2.

Instead of storing values for the largest cut, as we did for Max-Bisection, we
store the tuple that maximizes the function $f$.

We can now rewrite Equation 5 in terms of $\Gamma$ (recall that $r$ is the
root of the given nice tree decomposition):

######  Lemma 5.

$\Phi=\bigsqcup_{\begin{subarray}{c}S\subseteq X_{r}\\\ 0\leq\ell\leq\lvert
F_{r}\rvert\\\ \Lambda(\ell+\lvert S\rvert)\end{subarray}}\Gamma_{r}(\ell,S)$
(7)

###### Proof.

$\bigsqcup_{\begin{subarray}{c}S\subseteq X_{r}\\\ 0\leq\ell\leq\lvert
F_{r}\rvert\\\ \Lambda(\ell+\lvert
S\rvert)\end{subarray}}{\Gamma}_{r}(\ell,S)=\bigsqcup_{\begin{subarray}{c}S\subseteq
X_{r}\\\ 0\leq\ell\leq\lvert F_{r}\rvert\\\ \Lambda(\ell+\lvert
S\rvert)\end{subarray}}\bigsqcup_{\widehat{S}\in\binom{F_{r}}{\ell}}\Big{(}\ell+\lvert
S\rvert,\,w_{r}(\partial(S\mathbin{\dot{\cup}}\widehat{S})\Big{)}=\bigsqcup_{\begin{subarray}{c}S\subseteq
X_{r}\\\ 0\leq\ell\leq\lvert F_{r}\rvert\\\ \Lambda(\ell+\lvert S\rvert)\\\
\widehat{S}\in\binom{F_{r}}{\ell}\end{subarray}}\Big{(}\ell+\lvert
S\rvert,\,w_{r}(\partial(S\mathbin{\dot{\cup}}\widehat{S})\Big{)}\\\
=\bigsqcup_{\begin{subarray}{c}S\subseteq X_{r}\\\ \widehat{S}\subseteq
F_{r}\end{subarray}}\Big{(}\lvert
S\rvert+\lvert\widehat{S}\rvert,\,w_{r}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))\Big{)}=\bigsqcup_{\begin{subarray}{c}S\subseteq
V\\\ \Lambda(\lvert S\rvert)\end{subarray}}\Big{(}\lvert
S\rvert,\,w_{r}(\partial S)\Big{)}=\Phi\qed$

It is easy to see that, if we are given the values $\Gamma_{r}(\ell,S)$ for
all $0\leq\ell\leq\lvert F_{r}\rvert$ and all $S\subseteq X_{r}$, we can
compute $\Phi$ in time $\operatorname{\mathcal{O}}(2^{t}n)$. We claim that we
can compute the table $\Gamma$ for all nodes together in overall time
$\operatorname{\mathcal{O}}(2^{t}n^{2})$, implying that $\Phi$ can be computed
in time $\operatorname{\mathcal{O}}(2^{t}n^{2})$. To see this, we now show
that we can use a dynamic program to compute the table $\Gamma$ and eventually
$\Gamma_{r}$ in the desired time. Therefor, we first set up recurrences for
each node type that we can use to efficiently compute the value for a node $i$
of this type, given that we already know all the values _below_ $i$.

For our approach there is an important property of $\sqsubseteq$: Basically,
we are able to move the addition with a constant tuple outside of the supremum
operator, if the elements all have the same first component.

######  Lemma 6.

For any $a$, any finite set $M\subseteq\\{a\\}\times\mathds{Q}$ and any $z$ it
holds that

$z\oplus\bigsqcup_{x\in M}x=\bigsqcup_{x\in M}\big{(}z\oplus x\big{)}$

###### Proof.

As $M$ is finite, it suffices to show[viii][viii][viii]For the reader not
familiar with order theory: The binary supremum is an associative and
commutative map. If for every pair of elements there is a supremum, that is, a
smallest element that is larger than both elements of the pair, then so it
does for any finite set $M$. This can be shown by a simple inductive argument
using the aforementioned associativity/commutativity. this property for the
binary supremum $\sqcup$. Let $z=(b,w)$ and $(a,x)\in M$, $(a,y)\in M$. If
$x=y$ or $f(a,x)=f(a,y)$, the property is trivial. Thus we may assume without
loss of generality that $x>y$ and $f(a,x)\neq f(a,y)$. We now have two cases,
depending on $h\mapsto f(a,h)$. The first case is that $h\mapsto f(a,h)$
monotonic. Then our assumption implies that $f(a,x)>f(a,y)$ and hence:

$(b,z)\oplus\lparen(a,x)\sqcup(a,y)\rparen=(b,z)\oplus(a,x)=(a+b,x+z)=(a+b,x+z)\sqcup(a+b,y+z)$

The last step follows from the monotony, as $x+z\geq y+z$. The second case,
where $h\mapsto f(a,h)$ is antitonic, can be proven analogously. ∎

This property is absolutely crucial as it gives us some freedom for
transformations of section 5; it is applied multiple times in the proofs in
the appendix. Intuitively, this lemma tells us that the optimization process
works no different than it does e.g. Max-Cut or Max-Bisection; if we fix the
number of vertices we choose, given a set of cuts to pick from the cut
maximizing $f$ is either the cut of largest size or the cut of smallest size.

####  5.1 Recurrences

We now set up a recurrence, depending on the node type, to compute the table
$\Gamma$ by traversing the tree decomposition in a bottom-up fashion. In this
section we give the intuition behind the recurrences step by step. For
correctness proofs of the equations (which are very technical) we refer to the
appendix.

##### Leaf Node

Let $i$ be a leaf node. Then $F_{i}=\emptyset$. Thus, $\Gamma_{i}$ is only
defined for $\ell=0$ and $S\subseteq X_{i}$. If $S=\emptyset$, there are no
edges in the cut, hence $\Gamma_{i}(0,\emptyset)=(0,0)$. If $S=\\{v\\}$
consists of a single node, we can simply go through all its edges, that is set

$\Gamma_{i}(0,\\{v\\})=\Big{(}1,\sum_{\begin{subarray}{c}v^{\prime}\in
X_{i}\\\ vv^{\prime}\in E\end{subarray}}w(vv^{\prime})\Big{)}.$ (7)

Now let $S=S^{\prime}\mathbin{\dot{\cup}}\\{v\\}$ where
$S^{\prime}\neq\emptyset$. We will now argue how we can compute the value
$\Gamma_{i}(0,S)$ given the value $\Gamma_{i}(0,S^{\prime})$. In the situation
considered for $\Gamma_{i}(0,S^{\prime})$ we have $v\notin S^{\prime}$. If we
move $v$ into the selection and are able to track and compute the changes, we
can also compute $\Gamma_{i}(0,S)$. After moving $v$ into the selection, there
might be edges from $S^{\prime}$ to $\\{v\\}$ (which all have been in the cut
before); those edges are no more in the cut for $S$. Also, there might also be
some new edges in the cut, more precisely all edges from $v$ to
$X_{i}\setminus S$. There are no more new edges in the cut and no other edges
are removed from the cut. This yields

$\Gamma_{i}(0,\underbrace{\overset{\mathclap{\begin{subarray}{c}{\neq\emptyset}\\\
\big{\downarrow}\end{subarray}}}{S^{\prime}}\mathbin{\dot{\cup}}\\{v\\}}_{S})=\Gamma_{i}(0,S^{\prime})\oplus\Big{(}\overset{\mathclap{\begin{subarray}{c}{\lvert
S\rvert-\lvert S^{\prime}\rvert=1,\text{\leavevmode\nobreak\ we now add the
new vertex $v$}}\\\
\big{\downarrow}\end{subarray}}}{1},\,\underbrace{\sum_{\begin{subarray}{c}v^{\prime}\in
X_{i}\setminus S^{\prime}\\\ vv^{\prime}\in
E\end{subarray}}w(vv^{\prime})}_{\text{edges from $v$ to $X_{i}\setminus
S^{\prime}$}}-\underbrace{\sum_{\begin{subarray}{c}v^{\prime}\in S^{\prime}\\\
v^{\prime}v\in E\end{subarray}}w(v^{\prime}v)}_{\text{edges from $S^{\prime}$
to $v$}}\Big{)}.$ (8)

##### Forget Node

Let $i$ be a forget node with child $j$. Then there is $v\in V$ such that
$X_{i}\mathbin{\dot{\cup}}\\{v\\}=X_{j}$. Now, for the computation of the
entries $\Gamma_{i}(\ell,S)$ we only have to deal with one question: is it
better to include $v$ into the selection or not? As $v\in F_{i}$, this
question is only relevant if $\ell\geq 1$; if $\ell=0$, then
$\Gamma_{i}(\ell,S)=\Gamma_{j}(\ell,S)$. Now let $\ell\geq 1$. If we included
$v$ into our selection, we have to include $\ell-1$ further vertices from
$F_{j}$; if we do not include $v$, we have to include $\ell$ further from
$F_{j}$. We now simply pick the better result of both options. Overall, this
yields the following recurrence:

$\Gamma_{i}(\ell,S)=\begin{cases}\Gamma_{j}(\ell-1,S\mathbin{\dot{\cup}}\\{v\\})\sqcup\Gamma_{j}(\ell,S)&\ell\geq
1\\\ \Gamma_{j}(\ell,S)&\ell=0\end{cases}.$ (9)

##### Introduce Node

Let $i$ be an introduce node with child $j$. Then there is $v\in V$ such that
$X_{i}=X_{j}\mathbin{\dot{\cup}}\\{v\\}$. When computing $\Gamma_{i}(\ell,S)$
we have to make a case distinction whether $v$ is in $S$ or not.

In the first case $v\in S$ we rely on $\Gamma_{j}(\ell,S\setminus\\{v\\})$ to
compute the value. As we consider a selection of $S$ and $\ell$ further
vertices of $F_{i}$ as opposed to the entry
$\Gamma_{j}(\ell,S\setminus\\{v\\})$ which only considers a selection of
$S\setminus\\{v\\}$ and $\ell$ further vertices of $F_{j}=F_{i}$, we have to
add $1$ to the first component of $\Gamma_{j}(\ell,S\setminus\\{v\\})$ to
account for the additional vertex $v$. For the second component, the size of
the cut, we only have to add the weight of all edges from $v$ to
$X_{j}\setminus S$. Note that there are no weights that we need to subtract;
while there might be edges between $v$ and $S$, those are not considered in
the computation of $\Gamma_{j}(\ell,S\setminus\\{v\\})$ as the vertex $v$ does
not appear in $Y_{j}$ (due to Coherence and Edge Coverage). Thus, for $v\in S$
we get

$\Gamma_{i}(\ell,S)=\Big{(}\overset{\mathclap{\begin{subarray}{c}{\text{\qquad\qquad\qquad\quad
we now add the new vertex $v$ to the selection $S\setminus\\{v\\}$}}\\\
\big{\downarrow}\end{subarray}}}{1},\,\underbrace{w_{i}(\partial
v\cap(\\{v\\}\times(X_{i}\setminus S))}_{\mathclap{\text{edges from $v$ to
$X_{i}\setminus S$; we will later discuss how to compute this
value}}}\Big{)}\oplus\Gamma_{j}(\ell,S\setminus\\{v\\}).$ (10)

Now let us consider the case $v\notin S$. The argumentation is very similar.
As $v\notin S$, there is no new vertex we add to the selection. However, there
are possibly new edges and that change the value of the cut: the edges from
$S$ to $\\{v\\}$. This gives us the following recurrence for the case $v\notin
S$:

$\Gamma_{i}(\ell,S)=\Big{(}0,\,\underbrace{w_{i}(\partial
S\cap(X_{i}\times\\{v\\}))}_{\mathclap{\text{edges from $S$ to $\\{v\\}$; we
will later discuss how to compute this
value}}}\Big{)}\oplus\Gamma_{j}(\ell,S).$ (11)

In both cases there is a (case-dependent) additive term that has to b eadded
to an entry of $\Gamma_{j}$. Observe that this additive term is independent of
$\ell$. As it turns out, this additive term (depending only on $S$) can be
rewritten as

$\pi_{2}\big{(}\Gamma_{i}(\ell,S)\ominus\Gamma_{j}(\ell,S)\big{)}$ (12)

for any arbitrary, but fixed $\ell$; for details we refer to 22 in the
appendix. Thus, we can do the following: for $\ell=0$ we need to explicitly
compute the additive term for all $S\subseteq X_{i}$. For all $\ell\geq 1$ we
can simply use $\pi_{2}(\Gamma_{i}(\ell-1,S)\ominus\Gamma_{i}(\ell-1,S))$ for
all $S\subseteq X_{i}$.

##### Join Node

Let $i$ be a join node with left child $j$ and right child $k$. Then
$X_{i}=X_{j}=X_{k}$. The value $\Gamma_{i}(\ell,S)$ can then be interpreted as
the tuple maximizing $f$ over all selections $\widehat{S}\subseteq Y_{i}$
where there are $\ell_{1}$ vertices from $F_{j}$ and $\ell_{2}$ from $F_{k}$
for every $0\leq\ell_{1}\leq\lvert F_{j}\rvert$, $0\leq\ell_{2}\leq\lvert
F_{k}\rvert$ where $\ell_{1}+\ell_{1}=\ell$. This is closely related to

$\Gamma_{i}(\ell,S)=\bigsqcup_{\begin{subarray}{c}0\leq\ell_{1}\leq\lvert
F_{j}\rvert\\\ 0\leq\ell_{2}\leq\lvert F_{k}\rvert\\\
\ell_{2}+\ell_{1}=\ell\end{subarray}}\big{(}\Gamma_{j}(\ell_{1},S)\oplus\Gamma_{k}(\ell_{2},S)\big{)};$

it is not hard to see that this equation almost computes the desired tuple,
with the exception that each vertex in $S$ and each edge of $E\cap X_{i}^{2}$
that is in the cut is counted twice. Thus, by subtracting the doubly counted
vertices/edge weights and applying 6 we get

$\Gamma_{i}(\ell,S)=\bigg{(}\bigsqcup_{\begin{subarray}{c}0\leq\ell_{1}\leq\lvert
F_{j}\rvert\\\ 0\leq\ell_{2}\leq\lvert F_{k}\rvert\\\
\ell_{2}+\ell_{1}=\ell\end{subarray}}\big{(}\Gamma_{j}(\ell_{1},S)\oplus\Gamma_{k}(\ell_{2},S)\big{)}\bigg{)}\ominus\Big{(}\lvert
S\rvert,\,w_{i}(\partial S)\Big{)}.$ (13)

####  5.2 Running Time

We claim that our algorithm has an overall running time of
$\operatorname{\mathcal{O}}(2^{t}n^{2})$. To prove this we first need to deal
with some preprocessing steps. The first step was already mentioned:
converting the tree decomposition into a nice tree decomposition. This can be
done in $\operatorname{\mathcal{O}}(nt^{2})$ according to 3. We model sets as
bit vectors of length $n$; we omit the (very technical) details on how set
operations can be implemented on bit vectors such that they all take only
constant time. The second preprocessing step is creating an adjacency matrix
of the graph in time $\operatorname{\mathcal{O}}(n^{2})$; this is necessary to
be able to compute the explicit sums occurring in our recurrences in time
$\operatorname{\mathcal{O}}(n)$ each. We now claim that our dynamic program
takes the running time specified in Figure 1 per node, depending on the node’s
type. As we only have $\operatorname{\mathcal{O}}(n)$ nodes in the
decomposition (it is a small decomposition), this directly implies that the
computation of $\Gamma_{i}$ only takes time
$\operatorname{\mathcal{O}}(2^{t}n^{2})$.

Leaf node |  $\operatorname{\mathcal{O}}(2^{t}n)$ |  per node
---|---|---
Forget node |  $\operatorname{\mathcal{O}}(2^{t}\lvert F_{i}\rvert)$ |  per node
Introduce node |  $\operatorname{\mathcal{O}}(2^{t}n)$ |  per node
Join node |  $\operatorname{\mathcal{O}}(2^{t}\lvert F_{j}\times F_{k}\rvert)$ |  per node
$\operatorname{\mathcal{O}}(2^{t}n^{2})$ |  for all nodes
Figure 1: Running times of the computation of $\Gamma_{i}$ for a node $i\in I$
(if there is one child $i$, let $j$ be that child, and if there are two
children, let $j,k$ be those children of $i$) depending on the node’s type

##### Leaf Node

Let $i$ be a leaf node. Then $F_{i}=\emptyset$. Hence $\Gamma_{i}$ has
$\operatorname{\mathcal{O}}(2^{t})$ entries. We make use of s 7 and 8 to
compute these entries; both equations have a constant number of sums, and each
sum can be computed in $\operatorname{\mathcal{O}}(n)$ using the adjacency
matrix and basic set operations.

##### Forget Node

Let $i$ be a forget node with child $j$. Then
$X_{i}\mathbin{\dot{\cup}}\\{v\\}=X_{j}$ for some $v\in V$. There are
$\operatorname{\mathcal{O}}(2^{t}\lvert F_{i}\rvert)$ entries in $\Gamma_{i}$.
As we only use Equation 9 to compute the values, which takes constant time per
value, the overall running time for a single forget node is
$\operatorname{\mathcal{O}}(2^{t}\lvert F_{i}\rvert)$.

##### Introduce Node

Let $i$ be an introduce node with child $j$. Then
$X_{i}=X_{j}\mathbin{\dot{\cup}}\\{v\\}$ for some $v\in V$. There are
$\operatorname{\mathcal{O}}(2^{t}\lvert
F_{i}\rvert)\subseteq\operatorname{\mathcal{O}}(2^{t}n)$ entries in
$\Gamma_{i}$ we need to compute. For the entries $\Gamma_{i}(0,S)$ for
$S\subseteq X_{i}$ we use s 10 and 11 and explicitly compute the $w_{i}$
expressions as sums in $\operatorname{\mathcal{O}}(n)$ each. There are at most
$\operatorname{\mathcal{O}}(2^{t})$ entries for $\ell=0$, thus for all these
entries we need at most $\operatorname{\mathcal{O}}(2^{t}n)$ time. For all
other
$\operatorname{\mathcal{O}}(2^{t}n-2^{t})=\operatorname{\mathcal{O}}(2^{t}n)$
entries we make use of Equation 12 which allows us now to use s 10 and 11 to
compute the remaining entries in time $\operatorname{\mathcal{O}}(1)$ each.
The overall running time for a single introduce node is hence
$\operatorname{\mathcal{O}}(2^{t}n)$.

##### Join Node

Let $i$ be a join node with left child $j$ and right child $k$. Then
$X_{i}=X_{j}=X_{k}$. There are $\operatorname{\mathcal{O}}(2^{t}\lvert
F_{i}\rvert)\subseteq\operatorname{\mathcal{O}}(2^{t}\lvert
F_{j}\rvert\cdot\lvert F_{k}\rvert)$ entries we need to compute. We only use
Equation 13 to compute them. For a fixed $S\subseteq X_{i}$, we need to
compare $\lvert F_{j}\rvert\cdot\lvert F_{k}\rvert$ different pairs in that
equation. This means that the running time – per entry – is in
$\operatorname{\mathcal{O}}(\lvert F_{j}\rvert\cdot\lvert
F_{k}\rvert)=\operatorname{\mathcal{O}}(\lvert F_{j}\times F_{k}\rvert)$.
Using Equation 4 (which is a consequence of 4) it follows that the overall
running time for all entries of all join nodes is bounded by
$\operatorname{\mathcal{O}}(2^{t}n^{2})$.

###  6 Applications

We now give applications to several cut problems. Recall that our framework
computes $\Phi$, a 2-tuple that maximizes a given map $f$. At this point we
want to point out that $\Phi=\bot$ can only occur if there is no partition of
the vertices whose cardinality satisfies $\Lambda$. This does not occur in our
applications.[ix][ix][ix]In general, we cannot think of any reason why this
case should occur in practice; it seems to us that if it occurs this is likely
to indicate an error of the model used. Note that for any instantiation of the
framework we have

$f(\Phi)=f\bigg{(}\bigsqcup_{\begin{subarray}{c}S\subseteq V\\\ \Lambda(\lvert
V\rvert)\end{subarray}}\Big{(}\lvert S\rvert,\,w(\partial
S)\Big{)}\bigg{)}=\max_{\begin{subarray}{c}S\subseteq V\\\ \Lambda(\lvert
S\rvert)\end{subarray}}f\Big{(}\lvert S\rvert,\,w(\partial S)\Big{)}.$ (14)

##### Max-Cut

Set $f(\nu,s)\coloneqq s$ and $\Lambda(x)\coloneqq\mathrm{true}$. It is not
hard to see that $f$ is monotonic in the second argument and hence fulfils the
requirements of our framework.

######  Lemma 7.

$f(\Phi)=\max_{S\subseteq V}w(\partial S)$

###### Proof.

$f(\Phi)=\max_{\begin{subarray}{c}S\subseteq V\\\ \Lambda(\lvert
S\rvert)\end{subarray}}f\Big{(}\lvert S\rvert,\,w(\partial
S)\Big{)}=\max_{S\subseteq V}f\Big{(}\lvert S\rvert,\,w(\partial
S)\Big{)}=\max_{S\subseteq V}w(\partial S)\qed$

##### Max-Bisection’

Set $f(\nu,s)\coloneqq s$ and $\Lambda(x)\coloneqq\big{(}\left\lvert
2x-n\right\rvert\leq 1\big{)}$. It is not hard to see that $f$ is monotonic in
the second argument and hence fulfils the requirements of our framework.

######  Lemma 8.

$f(\Phi)=\max_{\begin{subarray}{c}S\subseteq V\\\ \left\lvert\lvert
S\rvert-\lvert V\setminus S\rvert\right\rvert\leq 1\end{subarray}}w(\partial
S)$

###### Proof.

$f(\Phi)=\max_{\begin{subarray}{c}S\subseteq V\\\ \Lambda(\lvert
S\rvert)\end{subarray}}f\Big{(}\lvert S\rvert,\,w(\partial
S)\Big{)}=\max_{\begin{subarray}{c}S\subseteq V\\\ \left\lvert 2\lvert
S\rvert-n\right\rvert\leq 1\end{subarray}}w(\partial
S)=\max_{\begin{subarray}{c}S\subseteq V\\\ \left\lvert\lvert S\rvert-\lvert
V\setminus S\rvert\right\rvert\leq 1\end{subarray}}w(\partial S)\qed$

#####  $\beta$-Balanced-Min-Cut’

Set $f(\nu,s)\coloneqq-s$ and $\Lambda(x)\coloneqq\big{(}\beta n\leq
x\leq(1-\beta)n\big{)}$; the negation is required to model a minimization
problem in our maximization framework. It is not hard to see that $f$ is
antitonic in the second argument and hence fulfils the requirements of our
framework.

######  Lemma 9.

$-f(\Phi)=\min_{\begin{subarray}{c}S\subseteq V\\\ \beta\cdot\lvert
V\rvert\leq\lvert S\rvert\leq(1-\beta)\cdot\lvert
V\rvert\end{subarray}}w(\partial S)$

###### Proof.

$-f(\Phi)=-\max_{\begin{subarray}{c}S\subseteq V\\\ \Lambda(\lvert
S\rvert)\end{subarray}}f\Big{(}\lvert S\rvert,\,w(\partial
S)\Big{)}=\min_{\begin{subarray}{c}S\subseteq V\\\ \beta n\leq\lvert
S\rvert\leq(1-\beta)n\end{subarray}}-f\Big{(}\lvert S\rvert,\,w(\partial
S)\Big{)}=\min_{\begin{subarray}{c}S\subseteq V\\\ \beta\lvert
V\rvert\leq\lvert S\rvert\leq(1-\beta)\lvert V\rvert\end{subarray}}w(\partial
S)\qed$

##### Min-Edge-Expansion’

Set $f(\nu,s)\coloneqq\begin{cases}-\infty&\nu=0\\\
-\frac{s}{\nu}&\text{otherwise}\end{cases}$. We claim that $f$ is antitonic in
its second argument. To see this, fix $\nu$ such that $0\leq\nu\leq n$. and
let $g(s)\coloneqq f(\nu,s)$. If $\nu=0$, then for all $s$ we have that
$g(s)=f(\nu,s)=-\infty$ is a constant map and hence antitonic. If $\nu>0$,
then then for all $s$ we have that $g(s)=f(\nu,s)=-\frac{s}{\nu}$ is a linear
map with negative sign and hence also antitonic.

We now need the validator function to exclude all sets $S$ where $\lvert
S\rvert>\lvert V\setminus S\rvert$; we do not have to explicitly exclude the
empty set as our measure function evaluates to $-\infty$ for those cases (but
we may do so). Thus, we might define $\Lambda(x)\coloneqq\big{(}x\leq
n-x\big{)}$. Then the value of the Min-Edge-Expansion can be recovered from
the result of our framework $\Phi$ by computing $-f(\Phi)$. That value cannot
be $\infty$ unless the graph is empty.

######  Lemma 10.

If $n\geq 1$, then
$\displaystyle-f(\Phi)=\min_{\begin{subarray}{c}\emptyset\neq S\subseteq V\\\
\lvert S\rvert\leq\lvert V\setminus S\rvert\end{subarray}}\frac{w(\partial
S)}{\lvert S\rvert}$.  $\lrcorner$

###### Proof.

$-f(\Phi)=-\max_{\begin{subarray}{c}S\subseteq V\\\ \Lambda(\lvert
S\rvert)\end{subarray}}f\Big{(}\lvert S\rvert,\,w(\partial
S)\Big{)}=\min_{\begin{subarray}{c}S\subseteq V\\\ \lvert S\rvert\leq n-\lvert
S\rvert\end{subarray}}-f\Big{(}\lvert S\rvert,\,w(\partial S)\Big{)}\\\
=\min_{\begin{subarray}{c}S\subseteq V\\\ \lvert S\rvert\leq\lvert V\setminus
S\rvert\end{subarray}}\begin{cases}\infty&\lvert S\rvert=0\\\ \frac{w(\partial
S)}{\lvert
S\rvert}&\text{otherwise}\end{cases}=\min\left\\{\infty,\min_{\begin{subarray}{c}\emptyset\neq
S\subseteq V\\\ \lvert S\rvert\leq\lvert V\setminus
S\rvert\end{subarray}}\frac{w(\partial S)}{\lvert
S\rvert}\right\\}\overset{n\geq 1}{=}\min_{\begin{subarray}{c}\emptyset\neq
S\subseteq V\\\ \lvert S\rvert\leq\lvert V\setminus
S\rvert\end{subarray}}\frac{w(\partial S)}{\lvert
S\rvert}\qed\\!\\!\\!\\!\\!\\!$

##### Sparsest-Cut’

Sparsest Cut’ is quite similar to Min-Edge-Expansion’. We set
$f(\nu,s)\coloneqq\begin{cases}-\infty&\nu\in\\{0,n\\}\\\
-\frac{s}{\nu(n-\nu)}&\text{otherwise}\end{cases}$. This is again an antitonic
map, following the same argumentation as for Min-Edge-Expansion’. The
validator function becomes trivial for Sparsest-Cut’, that is
$\Lambda(x)\coloneqq\mathrm{true}$. Recovering the Sparsest-Cut’ from $\Phi$
works the same way as before: it can be expressed as $-f(\Phi)$ which, again,
cannot be $\infty$ unless the graph has at most one vertex.

######  Lemma 11.

If $n\geq 2$, then $\displaystyle-f(\Phi)=\min_{\emptyset\neq S\subsetneq
V}\frac{w(\partial S)}{\lvert S\rvert\cdot\lvert V\setminus S\rvert}$.
$\lrcorner$

###### Proof.

$-f(\Phi)=-\max_{\begin{subarray}{c}S\subseteq V\\\ \Lambda(\lvert
S\rvert)\end{subarray}}f\Big{(}\lvert S\rvert,\,w(\partial
S)\Big{)}=\min_{S\subseteq V}-f\Big{(}\lvert S\rvert,\,w(\partial
S)\Big{)}=\min_{S\subseteq V}\begin{cases}\infty&\lvert S\rvert\in\\{0,n\\}\\\
\frac{w(\partial S)}{\lvert S\rvert\cdot\lvert V\setminus
S\rvert}&\text{otherwise}\end{cases}\\\
=\min\left\\{\infty,\min_{\emptyset\neq S\subseteq V}\frac{w(\partial
S)}{\lvert S\rvert\cdot\lvert V\setminus S\rvert}\right\\}\overset{n\geq
2}{=}\min_{\emptyset\neq S\subsetneq V}\frac{w(\partial S)}{\lvert
S\rvert\cdot\lvert V\setminus S\rvert}\qed\\!\\!\\!\\!\\!\\!$

##### Densest-Cut’

As Densest-Cut’ is the complementary problem of Sparsest-Cut’, the
instantiation of the framework is very similar: We set
$f(\nu,s)\coloneqq\begin{cases}-\infty&\nu\in\\{0,n\\}\\\
\frac{s}{\nu(n-\nu)}&\text{otherwise}\end{cases}$ and
$\Lambda(x)\coloneqq\mathrm{true}$. Then, $f(\Phi)$ is the value of the
densest cut (and $-\infty$ if there is at most one vertex).

######  Lemma 12.

If $n\geq 2$, then $\displaystyle f(\Phi)=\max_{\emptyset\neq S\subsetneq
V}\frac{w(\partial S)}{\lvert S\rvert\cdot\lvert V\setminus S\rvert}$.
$\lrcorner$

###### Proof.

$f(\Phi)=\max_{\begin{subarray}{c}S\subseteq V\\\ \Lambda(\lvert
S\rvert)\end{subarray}}f\Big{(}\lvert S\rvert,\,w(\partial
S)\Big{)}=\max_{S\subseteq V}f\Big{(}\lvert S\rvert,\,w(\partial
S)\Big{)}=\max_{S\subseteq V}\begin{cases}-\infty&\lvert
S\rvert\in\\{0,n\\}\\\ \frac{w(\partial S)}{\lvert S\rvert\cdot\lvert
V\setminus S\rvert}&\text{otherwise}\end{cases}\\\
=\max\left\\{-\infty,\max_{\emptyset\neq S\subseteq V}\frac{w(\partial
S)}{\lvert S\rvert\cdot\lvert V\setminus S\rvert}\right\\}\overset{n\geq
2}{=}\max_{\emptyset\neq S\subsetneq V}\frac{w(\partial S)}{\lvert
S\rvert\cdot\lvert V\setminus S\rvert}\qed\\!\\!\\!\\!\\!\\!$

###  7 Conclusion

We showed that – given a small tree decomposition of width $t$ – many cut
problems can be solved in time $\operatorname{\mathcal{O}}(2^{t}n^{2})$ using
our framework. To our knowledge, the running times achieved by our framework
are better than the previously known algorithms for the considered problems.
Moreover, this running time is unlikely to be improved significantly
(improvements by factors $\operatorname{poly}t$ and/or
$\operatorname{poly}\log n$ are not excluded) in general: An algorithm
(solving Min-Bisection) that runs in time
$\operatorname{\mathcal{O}}(n^{2-\varepsilon}f(t))$ for some $f$ and some
$\varepsilon>0$ would imply an algorithm of running time
$\operatorname{\mathcal{O}}(n^{2-\delta})$ for some $\delta>0$ for
$(\min,+)$-convolution [6], which is considered unlikely [5]. An algorithm
(solving Max-Cut) cannot have a running time
$\operatorname{\mathcal{O}}((2-\varepsilon)^{t}\operatorname{poly}n)$ for some
$\varepsilon>0$ unless SETH fails [15, 8, 9, 4]. However, there might be
problems that can be solved using our framework that we have not considered
yet. Moreover, it might be possible to generalize the framework (with possibly
worse running time) to e.g be able to also cover connectivity problems (see
[2]).

###  8 References

### References

  * [1] Brenda S. Baker  “Approximation Algorithms for NP-Complete Problems on Planar Graphs”  In _Journal of the ACM_ 41.1 New York, USA: Association for Computing Machinery, 1994, pp. 153–180  DOI: 10.1145/174644.174650
  * [2] Hans L. Bodlaender, Marek Cygan, Stefan Kratsch and Jesper Nederlof  “Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth”  In _Information and Computation_ 243, 2015, pp. 86–111  DOI: 10.1016/j.ic.2014.12.008
  * [3] Paul S. Bonsma, Hajo Broersma, Viresh Patel and Artem V. Pyatkin  “The complexity of finding uniform sparsest cuts in various graph classes”  In _Journal of Discrete Algorithms_ 14, 2012, pp. 136–149  DOI: 10.1016/j.jda.2011.12.008
  * [4] Chris Calabro, Russell Impagliazzo and Ramamohan Paturi  “The Complexity of Satisfiability of Small Depth Circuits”  In _Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10–11, 2009, Revised Selected Papers_ 5917, Lecture Notes in Computer Science  Springer, 2009, pp. 75–85  DOI: 10.1007/978-3-642-11269-0\\_6
  * [5] Marek Cygan, Marcin Mucha, Karol Węgrzycki and Michał Włodarczyk  “On Problems Equivalent to (Min,+)-Convolution”  In _ACM Transactions on Algorithms_ 15.1 Association for Computing Machinery, 2019  DOI: 10.1145/3293465
  * [6] Eduard Eiben, Daniel Lokshtanov and Amer E. Mouawad  “Bisection of bounded treewidth graphs by convolutions”  In _Journal of Computer and System Sciences_ 119, 2021, pp. 125–132  DOI: 10.1016/j.jcss.2021.02.002
  * [7] Uriel Feige and Orly Yahalom  “On the Complexity of Finding Balanced Oneway Cuts”  In _Information Processing Letters_ 87.1, 2003, pp. 1–5  DOI: 10.1016/S0020-0190(03)00251-5
  * [8] Tesshu Hanaka, Yasuaki Kobayashi and Taiga Sone  “A (probably) optimal algorithm for Bisection on bounded-treewidth graphs”  In _Theoretical Computer Science_ 873, 2021, pp. 38–46  DOI: 10.1016/j.tcs.2021.04.023
  * [9] Russell Impagliazzo and Ramamohan Paturi  “On the Complexity of k-SAT”  In _Journal of Computer and System Sciences_ 62.2, 2001, pp. 367–375  DOI: 10.1006/jcss.2000.1727
  * [10] Klaus Jansen, Marek Karpinski, Andrzej Lingas and Eike Seidel  “Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs”  In _SIAM Journal on Computing_ 35.1, 2005, pp. 110–119  DOI: 10.1137/S009753970139567X
  * [11] Ramin Javadi and Amir Nikabadi  “On the Parameterized Complexity of Sparsest Cut and Small-set Expansion Problems”  In _Computing Research Repository_ abs/1910.12353, 2019  arXiv: http://arxiv.org/abs/1910.12353
  * [12] Richard M. Karp  “Reducibility among Combinatorial Problems”  In _Complexity of Computer Computations_ , 1972, pp. 85–103  DOI: 10.1007/978-1-4684-2001-2_9
  * [13] Ioannis Katsikarelis  “Computing bounded-width tree and branch decompositions of k-outerplanar graphs”  In _Computing Research Repository_ abs/1301.5896, 2013  arXiv: http://arxiv.org/abs/1301.5896
  * [14] Ton Kloks  “Treewidth, Computations and Approximations” 842, Lecture Notes in Computer Science  Berlin/Heidelberg: Springer-Verlag, 1994  DOI: 10.1007/BFb0045375
  * [15] Daniel Lokshtanov, Dániel Marx and Saket Saurabh  “Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal”  In _ACM Transactions on Algorithms_ 14.2, 2018, pp. 13:1–13:30  DOI: 10.1145/3170442
  * [16] Michael Mahoney  “Lecture: Overview of Graph Partitioning” [Online; accessed 2022-01-04]  In _Lecture Notes of?Stat260/CS294: Spectral Graph Methods?_, https://www.stat.berkeley.edu/~mmahoney/s15-stat260-cs294/Lectures/lecture05-05feb15.pdf

a

## Appendix

###  Appendix A Correctness of the Recurrences

In order to prove the correctness of our recurrences, we first need a few
calculation rules for the interaction of $\partial A$ and the intersection
with specific Cartesian products. This will be done in the following section.
Afterwards, there is one section per node type where the correctness of the
recurrence for this node type is shown formally.

####  A.1 Calculation Rules

We start with the simplest and very obvious rule that states that the weight
of edges of the disjunct union $A\mathbin{\dot{\cup}}B$ of two disjointedge
sets $A,B$ is exactly the sum of the weights of $A$ plus those of $B$:

######  Lemma 13.

For two sets disjoint edge sets $A$, $B$ we have

$w(A\mathbin{\dot{\cup}}B)=w(A)+w(B).$

###### Proof.

Follows directly from definition. ∎

Let us now consider some vertex set $A$ and the edges leaving $A$, that is the
edges going from $A$ to $\overline{A}$. It is not hard to see that the
intersection with $B\times C$ for $B\supseteq A$ and $C\supseteq\overline{A}$
leaves this set unchanged:

######  Lemma 14.

For any $A$, $B\supseteq A$, and $C\supseteq\overline{A}$ we have

$\partial A=\partial A\cap(B\times C).$

###### Proof.

$\partial A=\set{v_{1}v_{2}\in E}{v_{1}\in
A,v_{2}\in\overline{A}}=\set{v_{1}v_{2}\in E}{v_{1}\in
A,v_{2}\in\overline{A}}\cap(B\times C)\\\ =\partial A\cap(B\times C)\qed$

Now we show rules that are more complex. The following set of rules consider
some edge set $J$ and vertex sets $K$ and $L$. More precisly, the expression
$J\cap(K\times L)$ can be decomposed if there are certian relations between
the sets involved.

######  Lemma 15.

Let $A$ and $B$ be disjoint sets.

  1. (i)

$\displaystyle{\partial(A\mathbin{\dot{\cup}}B)=\partial
A\cap(A\times\overline{B})\mathbin{\dot{\cup}}\partial
B\cap(B\times\overline{A})}$

Now let $C$ be a set disjoint with both, $A$ and $B$.

  1. (ii)

$\displaystyle{\partial A\cap(A\times(B\mathbin{\dot{\cup}}C))=\partial
A\cap(A\times B)\mathbin{\dot{\cup}}\partial A\cap(A\times C)}$

  2. (iii)

$\displaystyle{\partial(A\mathbin{\dot{\cup}}B)\cap((A\mathbin{\dot{\cup}}B)\times
C)=\partial A\cap(A\times C)\mathbin{\dot{\cup}}\partial B\cap(B\times C)}$
$\lrcorner$

###### Proof.

Proof of Statement (i).

$\displaystyle\partial(A\mathbin{\dot{\cup}}B)$
$\displaystyle=\set{v_{1}v_{2}\in E}{v_{1}\in
A\mathbin{\dot{\cup}}B,v_{2}\in\overline{A\mathbin{\dot{\cup}}B}}$
$\displaystyle=\set{v_{1}v_{2}\in E}{v_{1}\in
A,v_{2}\in\overline{A\mathbin{\dot{\cup}}B}}\mathbin{\dot{\cup}}\set{v_{1}v_{2}\in
E}{v_{1}\in B,v_{2}\in\overline{A\mathbin{\dot{\cup}}B}}$
$\displaystyle=\set{v_{1}v_{2}\in E}{v_{1}\in A,v_{2}\in\overline{A}\land
v_{2}\in\overline{B}}\mathbin{\dot{\cup}}\set{v_{1}v_{2}\in E}{v_{1}\in
B,v_{2}\in\overline{A}\land v_{2}\in\overline{B}}$
$\displaystyle=\set{v_{1}v_{2}\in E}{v_{1}\in
A,v_{2}\in\overline{A}}\cap(A\times\overline{B})\mathbin{\dot{\cup}}\set{v_{1}v_{2}\in
E}{v_{1}\in B,v_{2}\in\overline{B}}\cap(B\times\overline{A})$
$\displaystyle=\partial A\cap(A\times\overline{B})\mathbin{\dot{\cup}}\partial
B\cap(B\times\overline{A})$ $\vartriangleleft$

Proof of Statement (ii). Note note that $B\mathbin{\dot{\cup}}C$ and $A$ are
disjoint, which implies
$B,C\subseteq(B\mathbin{\dot{\cup}}C)\subseteq\overline{A}$.

$\displaystyle\partial A\cap(A\times(B\mathbin{\dot{\cup}}C))$
$\displaystyle=\set{v_{1}v_{2}\in E}{v_{1}\in
A,v_{2}\in\overline{A}}\cap(A\times(B\mathbin{\dot{\cup}}C))$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{(B\mathbin{\dot{\cup}}C)\subseteq\overline{A}}\\\
\big{\downarrow}\end{subarray}}}{=}\set{v_{1}v_{2}\in E}{v_{1}\in A,v_{2}\in
B\mathbin{\dot{\cup}}C}$ $\displaystyle=\set{v_{1}v_{2}\in E}{v_{1}\in
A,v_{2}\in B}\mathbin{\dot{\cup}}\set{v_{1}v_{2}\in E}{v_{1}\in A,v_{2}\in C}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{B\subseteq\overline{A}\land
C\subseteq\overline{A}}\\\ \big{\downarrow}\end{subarray}}}{=}\partial
A\cap(A\times B)\mathbin{\dot{\cup}}\partial A\cap(A\times C)$
$\vartriangleleft$

Proof of Statement (iii). Note note that $A\mathbin{\dot{\cup}}B$ and $C$ are
disjoint, which implies $(A\mathbin{\dot{\cup}}B)\subseteq\overline{C}$, which
is equivalent to $\overline{A\mathbin{\dot{\cup}}B}\supseteq C$.

$\displaystyle\partial(A\mathbin{\dot{\cup}}B)\cap((A\mathbin{\dot{\cup}}B)\times
C)$ $\displaystyle=\set{v_{1}v_{2}\in E}{v_{1}\in
A\mathbin{\dot{\cup}}B,v_{2}\in\overline{A\mathbin{\dot{\cup}}B}}\cap((A\mathbin{\dot{\cup}}B)\times
C)$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\overline{A\mathbin{\dot{\cup}}B}\supseteq
C}\\\ \big{\downarrow}\end{subarray}}}{=}\set{v_{1}v_{2}\in E}{v_{1}\in
A\mathbin{\dot{\cup}}B,v_{2}\in C}$ $\displaystyle=\set{v_{1}v_{2}\in
E}{v_{1}\in A,v_{2}\in C}\mathbin{\dot{\cup}}\set{v_{1}v_{2}\in E}{v_{1}\in
B,v_{2}\in C}$ $\displaystyle=\partial A\cap(A\times
C)\mathbin{\dot{\cup}}\partial B\cap(B\times C)\qed$

We need those rules for the correctness proof of the join nodes as well as for
showing another rule in the following paragraph.

For the special case that $B$ contains exactly one element in the first rule
of the previous statement, we get the following rule by incorporating 14, too:

######  Corollary 16.

For all $v$ and all $S$ where $v\notin S$ it holds that

$\partial(S\mathbin{\dot{\cup}}\\{v\\})=\partial
S\cap\overline{\\{v\\}}^{2}\mathbin{\dot{\cup}}\partial
v\cap\overline{S}^{2}.$

###### Proof.

$\displaystyle\partial(S\mathbin{\dot{\cup}}\\{v\\})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\hyperref@@ii[l4:two]{\autoref*{l4}\ref*{l4:two}}}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial
S\cap(S\times\overline{\\{v\\}})\mathbin{\dot{\cup}}\partial
v\cap(\\{v\\}\times\overline{S})$
$\displaystyle\underset{\mathclap{\begin{subarray}{c}\big{\uparrow}\\\
{\text{\autoref{stmt:expand}, using $S\subseteq\overline{\\{v\\}}$ and
$\\{v\\}\subseteq\overline{S}$}}\end{subarray}}}{=}\partial
S\cap\overline{\\{v\\}}^{2}\mathbin{\dot{\cup}}\partial
v\cap\overline{S}^{2}\qed$

This rule is very important as our recurrences are usually (except join nodes)
built by inductively adding vertices to the selection set $S$.

####  A.2 Leaf Node

######  Lemma 17 (Correctness of Equation 7).

Let $i$ be a leaf node and $v\in X_{i}$. Then for all $S\subseteq X_{i}$ we
have

$\Gamma_{i}(0,\\{v\\})=\Big{(}1,\,\sum_{\begin{subarray}{c}v^{\prime}\in
X_{i}\\\ vv^{\prime}\in E\end{subarray}}w(vv^{\prime})\Big{)}.$

###### Proof.

We can simply plug in the definition of $\Gamma$ and make use of $Y_{i}=X_{i}$
as follows:

$\Gamma_{i}(0,\\{v\\})=\bigsqcup_{\widehat{S}\in\binom{F_{i}}{0}}\Big{(}\lvert\\{v\\}\rvert,\,w_{i}(\partial(\\{v\\}\mathbin{\dot{\cup}}\widehat{S}))\Big{)}=\Big{(}1,\,w_{i}(\partial
v)\Big{)}\\\ =\Big{(}1,\,w(\partial v\cap
Y_{i}^{2})\Big{)}\underset{\mathclap{\begin{subarray}{c}\big{\uparrow}\\\
{Y_{i}=X_{i}}\end{subarray}}}{=}\Big{(}1,\,w(\partial v\cap
X_{i}^{2})\Big{)}=\sum_{\begin{subarray}{c}v^{\prime}\in X_{i}\\\
vv^{\prime}\in E\end{subarray}}w(vv^{\prime})\qed$

######  Lemma 18 (Correctness of Equation 8).

Let $i$ be a leaf node and $v\in X_{i}$. Then for all $S\subseteq X_{i}$ and
all $\emptyset\neq S^{\prime}\subseteq X_{i}\setminus\\{v\\}$ we have

$\Gamma_{i}(0,S^{\prime}\mathbin{\dot{\cup}}\\{v\\})=\Gamma_{i}(0,S^{\prime})\oplus\Big{(}1,\,\sum_{\begin{subarray}{c}v^{\prime}\in
X_{i}\setminus S^{\prime}\\\ vv^{\prime}\in
E\end{subarray}}w(vv^{\prime})-\sum_{\begin{subarray}{c}v^{\prime}\in
S^{\prime}\\\ v^{\prime}v\in E\end{subarray}}w(v^{\prime}v)\Big{)}$

###### Proof.

We start by plugging in the definition of $\Gamma$:

$\Gamma_{i}(0,S^{\prime}\mathbin{\dot{\cup}}\\{v\\})=\bigsqcup_{\widehat{S}\in\binom{F_{i}}{0}}\Big{(}\lvert
S^{\prime}\mathbin{\dot{\cup}}\\{v\\}\rvert,\,w_{i}\lparen\partial\lparen
S^{\prime}\mathbin{\dot{\cup}}\\{v\\}\rparen\rparen\Big{)}=\Big{(}1+\lvert
S^{\prime}\rvert,\,w_{i}\lparen\partial\lparen
S^{\prime}\mathbin{\dot{\cup}}\\{v\\}\rparen\rparen\Big{)}$ (14)

The question is now: how can we show that the size of the cut changes (in
comparison to the size of the cut when only $S^{\prime}$ is selected instead
of $S^{\prime}\mathbin{\dot{\cup}}\\{v\\}$) as claimed in the statement, that
is

$w_{i}(\partial(S^{\prime}\mathbin{\dot{\cup}}\\{v\\})))=\sum_{\begin{subarray}{c}v^{\prime}\in
X_{i}\setminus S^{\prime}\\\ vv^{\prime}\in
E\end{subarray}}w(vv^{\prime})-\sum_{\begin{subarray}{c}v^{\prime}\in
S^{\prime}\\\ v^{\prime}v\in E\end{subarray}}w(v^{\prime}v)?$

To answer this, we explicitly consider the change of the cut, that is

$\displaystyle
w_{i}(\partial(S^{\prime}\mathbin{\dot{\cup}}\\{v\\}))-w_{i}(\partial
S^{\prime})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{l2}}}\\\
\big{\downarrow}\end{subarray}}}{=}w(\partial
S^{\prime}\cap(X_{i}\setminus\\{v\\})^{2}\mathbin{\dot{\cup}}\partial
v\cap(X_{i}\setminus S^{\prime})^{2})-w_{i}(\partial S^{\prime})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{rule:alpha}}}\\\
\big{\downarrow}\end{subarray}}}{=}w(\partial
S^{\prime}\cap(X_{i}\setminus\\{v\\})^{2})+w(\partial v\cap(X_{i}\setminus
S^{\prime})^{2})-w_{i}(\partial S^{\prime})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{l2}}}\\\
\big{\downarrow}\end{subarray}}}{=}w(\partial
S^{\prime}\cap(X_{i}\setminus\\{v\\})^{2})+w(\partial v\cap(X_{i}\setminus
S^{\prime})^{2})$ $\displaystyle\phantom{{}={}}-w(\partial
S^{\prime}\cap(X_{i}\times(X_{i}\setminus\\{v\\}))\mathbin{\dot{\cup}}\partial
S^{\prime}\cap(X_{i}\times\\{v\\}))$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{rule:alpha}}}\\\
\big{\downarrow}\end{subarray}}}{=}w(\partial
S^{\prime}\cap(X_{i}\setminus\\{v\\})^{2})+w(\partial v\cap(X_{i}\setminus
S^{\prime})^{2})$ $\displaystyle\phantom{{}={}}-w(\partial
S^{\prime}\cap(X_{i}\times(X_{i}\setminus\\{v\\})))-w(\partial
S^{\prime}\cap(X_{i}\times\\{v\\}))$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{v\in X_{i}\setminus
S^{\prime},\,S^{\prime}\subseteq X_{i},\,\text{\autoref{stmt:reduce}}}\\\
\big{\downarrow}\end{subarray}}}{=}w(\partial
S^{\prime}\cap(X_{i}\times(X_{i}\setminus\\{v\\})))+w(\partial
v\cap(X_{i}\setminus S^{\prime})^{2})$
$\displaystyle\phantom{{}={}}-w(\partial
S^{\prime}\cap(X_{i}\times(X_{i}\setminus\\{v\\})))-w(\partial
S^{\prime}\cap(X_{i}\times\\{v\\}))$ $\displaystyle=w(\partial
v\cap(X_{i}\setminus S^{\prime})^{2})-w(\partial
S^{\prime}\cap(X_{i}\times\\{v\\}))$
$\displaystyle=\sum_{\begin{subarray}{c}v^{\prime}\in X_{i}\setminus
S^{\prime}\\\ vv^{\prime}\in
E\end{subarray}}w(vv^{\prime})-\sum_{\begin{subarray}{c}v^{\prime}\in
S^{\prime}\\\ v^{\prime}v\in E\end{subarray}}w(v^{\prime}v).$

We can use this and Equation 14 to deduce

$\displaystyle\Gamma_{i}(0,S^{\prime}\mathbin{\dot{\cup}}\\{v\\})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{proof:correctness:leaf:ii:1}}}\\\
\big{\downarrow}\end{subarray}}}{=}\Big{(}1+\lvert
S^{\prime}\rvert,\,w_{i}(\partial(S^{\prime}\mathbin{\dot{\cup}}\\{v\\}))\Big{)}$
$\displaystyle=\Big{(}1+\lvert
S^{\prime}\rvert,\,w_{i}(\partial(S^{\prime}\mathbin{\dot{\cup}}\\{v\\}))-w_{i}(\partial
S^{\prime})+w_{i}(\partial S^{\prime})\Big{)}$ $\displaystyle=\Big{(}\lvert
S^{\prime}\rvert,\,w_{i}(\partial
S^{\prime})\Big{)}\oplus\Big{(}1,\,w_{i}(\partial(S^{\prime}\mathbin{\dot{\cup}}\\{v\\}))-w_{i}(\partial
S^{\prime})\Big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{Statement
above}}\\\ \big{\downarrow}\end{subarray}}}{=}\Big{(}\lvert
S^{\prime}\rvert,\,w_{i}(\partial
S^{\prime})\Big{)}\oplus\Big{(}1,\,\sum_{\begin{subarray}{c}v^{\prime}\in
X_{i}\setminus S^{\prime}\\\ vv^{\prime}\in
E\end{subarray}}w(vv^{\prime})-\sum_{\begin{subarray}{c}v^{\prime}\in
S^{\prime}\\\ v^{\prime}v\in E\end{subarray}}w(v^{\prime}v)\Big{)}$
$\displaystyle=\Gamma_{i}(0,S^{\prime})\oplus\Big{(}1,\,\sum_{\begin{subarray}{c}v^{\prime}\in
X_{i}\setminus S^{\prime}\\\ vv^{\prime}\in
E\end{subarray}}w(vv^{\prime})-\sum_{\begin{subarray}{c}v^{\prime}\in
S^{\prime}\\\ v^{\prime}v\in E\end{subarray}}w(v^{\prime}v)\Big{)}\qed$

####  A.3 Forget Node

######  Lemma 19 (Correctness of Equation 9).

Let $i$ be a forget node with child $j$. Let $v\in V$ such that
$X_{i}\mathbin{\dot{\cup}}\\{v\\}=X_{j}$. Then for all $S\subseteq X_{i}$ and
all $0\leq\ell\leq\lvert F_{i}\rvert$ it holds that

$\Gamma_{i}(\ell,S)=\begin{cases}\Gamma_{j}(\ell-1,S\mathbin{\dot{\cup}}\\{v\\})\sqcup\Gamma_{j}(\ell,S)&\ell\geq
1\\\ \Gamma_{j}(\ell,S)&\ell=0\end{cases}.$

###### Proof.

Fix $S\subseteq X_{i}$ and $0\leq\ell\leq\lvert F_{i}\rvert$.

$\displaystyle\Gamma_{i}(\ell,S)$
$\displaystyle=\bigsqcup_{\widehat{S}\in\binom{F_{i}}{\ell}}\Big{(}\ell+\lvert
S\rvert,\,w_{i}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))\Big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{F_{i}=F_{j}\mathbin{\dot{\cup}}\\{v\\}}\\\
\big{\downarrow}\end{subarray}}}{=}\bigsqcup_{\widehat{S}\in\binom{F_{j}\mathbin{\dot{\cup}}\\{v\\}}{\ell}}\Big{(}\ell+\lvert
S\rvert,\,w_{i}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))\Big{)}$ Now we
make a case distinction wether $v\in\widehat{S}$; if $v\in\widehat{S}$ we may
select $\ell-1$ further vertices from $F_{j}\setminus\\{v\\}$, otherwise we
may select $\ell$ vertices from $F_{j}\setminus\\{v\\}$. This allows us to
split the supremum into the supremum of two suprema:
$\displaystyle=\left(\bigsqcup_{\widehat{S}\in\binom{F_{j}}{\ell-1}}\Big{(}\ell+\lvert
S\rvert,\,w_{i}(\partial(S\mathbin{\dot{\cup}}\widehat{S}\mathbin{\dot{\cup}}\\{v\\}))\Big{)}\right)\sqcup\left(\bigsqcup_{\widehat{S}\in\binom{F_{j}}{\ell}}\Big{(}\ell+\lvert
S\rvert,\,w_{i}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))\Big{)}\right)$
Note that the left supremum is applied on an empty set if $\ell=0$ (and thus
vanishes in that case, as $\bigsqcup\emptyset=\bot$); incorporating this and
using the definition of $\Gamma_{j}$ we eventuall get
$\displaystyle=\begin{cases}{\Gamma}_{j}(\ell-1,S\mathbin{\dot{\cup}}\\{v\\})\sqcup{\Gamma}_{j}(\ell,S)&\ell\geq
1\\\ {\Gamma}_{j}(\ell,S)&\ell=0\end{cases}.\qed$

####  A.4 Introduce Node

######  Lemma 20 (Correctness of Equation 10).

Let $i$ be an introduce node with child $j$. Let $v\in V$ such that
$X_{i}=X_{j}\mathbin{\dot{\cup}}\\{v\\}$. Then for all $S\subseteq X_{i}$
where $v\in S$ and all $0\leq\ell\leq\lvert F_{i}\rvert$ it holds that

$\Gamma_{i}(\ell,S)=\Big{(}1,\,w_{i}(\partial
v\cap(\\{v\\}\times(X_{i}\setminus
S)))\Big{)}\oplus\Gamma_{j}(\ell,S\setminus\\{v\\}).$ (10)

###### Proof.

Fix $S\subseteq X_{i}$ and $0\leq\ell\leq\lvert F_{i}\rvert$. By the
definition of $\Gamma$ we have

$\displaystyle\Gamma_{i}(\ell,S)$
$\displaystyle=\bigsqcup_{\widehat{S}\in\binom{F_{i}}{\ell}}\Big{(}\ell+\lvert
S\rvert,\,w_{i}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))\Big{)}$

We want to focus on the $w_{i}(\dots)$ expression in the equation above.
Therefor, let $S^{\prime}\coloneqq S\setminus\\{v\\}$. Consider the term
$w_{i}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))$. For the sake of
shortness, let $\widetilde{S}\coloneqq
S^{\prime}\mathbin{\dot{\cup}}\widehat{S}$. We then have

$\displaystyle w_{i}(\partial(\widetilde{S}\mathbin{\dot{\cup}}\\{v\\}))$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{l2}}}\\\
\big{\downarrow}\end{subarray}}}{=}w_{i}(\partial\widetilde{S}\cap\overline{\\{v\\}}^{2}\mathbin{\dot{\cup}}\partial
v\cap\overline{\widetilde{S}}^{2})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{rule:alpha}}}\\\
\big{\downarrow}\end{subarray}}}{=}w_{i}(\partial\widetilde{S}\cap\overline{\\{v\\}}^{2})+w_{i}(\partial
v\cap\overline{\widetilde{S}}^{2})$
$\displaystyle=w(\partial\widetilde{S}\cap\overline{\\{v\\}}^{2}\cap
Y_{i}^{2})+w(\partial v\cap\overline{\widetilde{S}}^{2}\cap Y_{i}^{2})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\overline{\\{v\\}}=Y_{i}\setminus\\{v\\},\,\overline{\widetilde{S}}=Y_{i}\setminus\widetilde{S}}\\\
\big{\downarrow}\end{subarray}}}{=}w(\partial\widetilde{S}\cap(Y_{i}\setminus\\{v\\})^{2})+w(\partial
v\cap(Y_{i}\setminus\widetilde{S})^{2})$ Now note that $v$ has just been
introduced; due to 1 (ii) and 1 (iii) there cannot be an edge from $v$ to any
vertex in $F_{i}$, thus, using $Y_{i}=X_{i}\mathbin{\dot{\cup}}F_{i}$, we have
$\displaystyle=w(\partial\widetilde{S}\cap(X_{i}\setminus\\{v\\})^{2})+w(\partial
v\cap(X_{i}\setminus\widetilde{S})^{2})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{X_{i}=X_{j}\mathbin{\dot{\cup}}\\{v\\}}\\\
\big{\downarrow}\end{subarray}}}{=}w(\partial\widetilde{S}\cap
X_{j}^{2})+w(\partial v\cap(X_{i}\setminus\widetilde{S})^{2})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\widetilde{S}\subseteq
X_{i},\,\text{\autoref{stmt:reduce}}}\\\
\big{\downarrow}\end{subarray}}}{=}w_{j}(\partial\widetilde{S})+w(\partial
v\cap(\\{v\\}\times(X_{i}\setminus\widetilde{S})))$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\widetilde{S}=S^{\prime}\mathbin{\dot{\cup}}\widehat{S}}\\\
\big{\downarrow}\end{subarray}}}{=}w_{j}(\partial\widetilde{S})+w(\partial
v\cap(\\{v\\}\times(X_{i}\setminus(S^{\prime}\mathbin{\dot{\cup}}\widehat{S}))))$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\widehat{S}\subseteq
F_{i}\implies\widehat{S}\cap X_{i}=\emptyset}\\\
\big{\downarrow}\end{subarray}}}{=}w_{j}(\partial\widetilde{S})+w(\partial
v\cap(\\{v\\}\times(X_{i}\setminus S^{\prime})))$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{vv\notin
E,\,\text{\autoref{stmt:reduce}},\,S^{\prime}=S\setminus\\{v\\}}\\\
\big{\downarrow}\end{subarray}}}{=}w_{j}(\partial\widetilde{S})+w(\partial
v\cap(\\{v\\}\times(X_{i}\setminus S)))$

Hence, we can rewrite $\Gamma_{i}(\ell,S)$ as follows:

$\displaystyle\Gamma_{i}(\ell,S)$
$\displaystyle=\bigsqcup_{\widehat{S}\in\binom{F_{i}}{\ell}}\Big{(}\underbrace{\ell+\lvert
S\rvert}_{=\mathrlap{\;1+\ell+\lvert
S^{\prime}\rvert}},\,w_{i}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))\Big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{F_{i}=F_{j}}\\\
\big{\downarrow}\end{subarray}}}{=}\bigsqcup_{\widehat{S}\in\binom{F_{j}}{\ell}}\Big{(}1+\ell+\lvert
S^{\prime}\rvert,\,w_{i}(\partial(S^{\prime}\mathbin{\dot{\cup}}\widehat{S}))\Big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{Statement
above}}\\\
\big{\downarrow}\end{subarray}}}{=}\bigsqcup_{\widehat{S}\in\binom{F_{j}}{\ell}}\Big{(}1+\ell+\lvert
S^{\prime}\rvert,\,w_{j}(\partial(S^{\prime}\mathbin{\dot{\cup}}\widehat{S}))+w(\partial
v\cap(\\{v\\}\times(X_{i}\setminus S^{\prime})))\Big{)}$
$\displaystyle=\bigsqcup_{\widehat{S}\in\binom{F_{j}}{\ell}}\left\lparen\Big{(}1,\,w(\partial
v\cap(\\{v\\}\times(X_{i}\setminus
S^{\prime})))\Big{)}\oplus\Big{(}\ell+\lvert
S^{\prime}\rvert,\,w_{j}(\partial(S^{\prime}\mathbin{\dot{\cup}}\widehat{S}))\Big{)}\right\rparen$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{stmt:compatible}}}\\\
\big{\downarrow}\end{subarray}}}{=}\Big{(}1,\,w(\partial
v\cap(\\{v\\}\times(X_{i}\setminus
S^{\prime})))\Big{)}\oplus\bigsqcup_{\widehat{S}\in\binom{F_{j}}{\ell}}\Big{(}\ell+\lvert
S^{\prime}\rvert,\,w_{j}(\partial(S^{\prime}\mathbin{\dot{\cup}}\widehat{S}))\Big{)}$
$\displaystyle=\Big{(}1,\,w(\partial v\cap(\\{v\\}\times(X_{i}\setminus
S^{\prime})))\Big{)}\oplus\Gamma_{j}(\ell,S^{\prime})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{S^{\prime}=S\setminus\\{v\\}}\\\
\big{\downarrow}\end{subarray}}}{=}\Big{(}1,\,w(\partial
v\cap(\\{v\\}\times(X_{i}\setminus
S^{\prime})))\Big{)}\oplus\Gamma_{j}(\ell,S\setminus\\{v\\})\qed$

######  Lemma 21 (Correctness of Equation 11).

Let $i$ be an introduce node with child $j$. Let $v\in V$ such that
$X_{i}=X_{j}\mathbin{\dot{\cup}}\\{v\\}$. Then for all $S\subseteq X_{i}$
where $v\notin S$ and all $0\leq\ell\leq\lvert F_{i}\rvert$ it holds that

$\Gamma_{i}(\ell,S)=\Big{(}0,\,w_{i}(\partial
S\cap(X_{i}\times\\{v\\}))\Big{)}\oplus\Gamma_{j}(\ell,S).$ (11)

###### Proof.

Fix $S\subseteq X_{i}$ such that $v\in S$, and $0\leq\ell\leq\lvert
F_{i}\rvert$. By the definition of $\Gamma$ we have

$\displaystyle\Gamma_{i}(\ell,S)$
$\displaystyle=\bigsqcup_{\widehat{S}\in\binom{F_{i}}{\ell}}\Big{(}\ell+\lvert
S\rvert,\,w_{i}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))\Big{)}.$

We want to focus on the $w_{i}(\dots)$ expression. Note that
$w_{i}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))=w(\partial\widetilde{S}\cap
Y_{i}^{2})$ where $\widetilde{S}\coloneqq S\mathbin{\dot{\cup}}\widehat{S}$,
thus we will have a closer look at the term $\widetilde{S}\cap Y_{i}^{2}$.

$\displaystyle\partial\widetilde{S}\cap Y_{i}^{2}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{stmt:reduce}}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial\widetilde{S}\cap(\widetilde{S}\times(Y_{i}\setminus\widetilde{S}))$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{Y_{i}=Y_{j}\mathbin{\dot{\cup}}\\{v\\}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial\widetilde{S}\cap(\widetilde{S}\times((Y_{j}\mathbin{\dot{\cup}}\\{v\\})\setminus\widetilde{S}))$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{v\notin\widetilde{S}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial\widetilde{S}\cap(\widetilde{S}\times((Y_{j}\setminus\widetilde{S})\mathbin{\dot{\cup}}\\{v\\}))$
$\displaystyle=\partial\widetilde{S}\cap(\widetilde{S}\times(Y_{j}\setminus\widetilde{S}))\mathbin{\dot{\cup}}\partial\widetilde{S}\cap(\widetilde{S}\times\\{v\\})$
$\displaystyle=\partial\widetilde{S}\cap(\widetilde{S}\times(Y_{j}\setminus\widetilde{S}))\mathbin{\dot{\cup}}\partial\widetilde{S}\cap(X_{i}\times\\{v\\})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\widetilde{S}\subseteq
Y_{j},\,\text{\autoref{stmt:reduce}}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial\widetilde{S}\cap
Y_{j}^{2}\mathbin{\dot{\cup}}\partial\widetilde{S}\cap(X_{i}\times\\{v\\}).$

Now focus on the second term of the union above:

$\displaystyle\partial\widetilde{S}\cap(X_{i}\times\\{v\\})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\widetilde{S}=S\mathbin{\dot{\cup}}\widehat{S}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial(S\mathbin{\dot{\cup}}\widehat{S})\cap(X_{i}\times\\{v\\})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\hyperref@@ii[l4:two]{\autoref*{l4}\ref*{l4:two}}}}\\\
\big{\downarrow}\end{subarray}}}{=}(\partial
S\cap(S\times\overline{\widehat{S}})\mathbin{\dot{\cup}}\partial\widehat{S}\cap(\widehat{S}\times\overline{S}))\cap(X_{i}\times\\{v\\})$
$\displaystyle=\partial
S\cap(S\times\overline{\widehat{S}})\cap(X_{i}\times\\{v\\})\mathbin{\dot{\cup}}\partial\widehat{S}\cap(\widehat{S}\times\overline{S})\cap(X_{i}\times\\{v\\})$
$\displaystyle=\partial S\cap((\underbrace{S\cap
X_{i}}_{=\mathrlap{\;S}})\times(\underbrace{\overline{\widehat{S}}\cap\\{v\\}}_{=\mathrlap{\;\\{v\\}}}))\mathbin{\dot{\cup}}\partial\widehat{S}\cap((\underbrace{\widehat{S}\cap
X_{i}}_{=\mathrlap{\;\emptyset}})\times(\overline{S}\cap\\{v\\}))$
$\displaystyle=\partial S\cap(S\times\\{v\\})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{S\subseteq
X_{i},\,\text{\autoref{stmt:reduce}}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial S\cap(X_{i}\times\\{v\\}).$

Combing both just shown equalities we get that

$\partial\widetilde{S}\cap Y_{i}^{2}=\partial\widetilde{S}\cap
Y_{j}^{2}\mathbin{\dot{\cup}}\partial S\cap(X_{i}\times\\{v\\}).$

We can thus deduce, using 13, that

$w_{i}(\partial\widetilde{S})=w_{j}(\partial\widetilde{S})+w(\partial
S\cap(X_{i}\times\\{v\\})).$

This allows us to rewrite $\Gamma_{i}(\ell,S)$ as follows:

$\displaystyle\Gamma_{i}(\ell,S)$
$\displaystyle=\bigsqcup_{\widehat{S}\in\binom{F_{i}}{\ell}}\Big{(}\ell+\lvert
S\rvert,\,w_{i}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))\Big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{Statement
above}}\\\
\big{\downarrow}\end{subarray}}}{=}\bigsqcup_{\widehat{S}\in\binom{F_{i}}{\ell}}\Big{(}\ell+\lvert
S\rvert,\,w_{j}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))+w(\partial
S\cap(X_{i}\times\\{v\\}))\Big{)}$
$\displaystyle=\bigsqcup_{\widehat{S}\in\binom{F_{i}}{\ell}}\left\lparen\Big{(}\ell+\lvert
S\rvert,\,w_{j}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))\Big{)}\oplus\Big{(}0,\,w(\partial
S\cap(X_{i}\times\\{v\\}))\Big{)}\right\rparen$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{stmt:compatible}}}\\\
\big{\downarrow}\end{subarray}}}{=}\Big{(}0,\,w(\partial
S\cap(X_{i}\times\\{v\\}))\Big{)}\oplus\bigsqcup_{\widehat{S}\in\binom{F_{i}}{\ell}}\Big{(}\ell+\lvert
S\rvert,\,w_{j}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))\Big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{F_{i}=F_{j}}\\\
\big{\downarrow}\end{subarray}}}{=}\Big{(}0,\,w(\partial
S\cap(X_{i}\times\\{v\\}))\Big{)}\oplus\bigsqcup_{\widehat{S}\in\binom{F_{j}}{\ell}}\Big{(}\ell+\lvert
S\rvert,\,w_{j}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))\Big{)}$
$\displaystyle=\Big{(}0,\,w(\partial
S\cap(X_{i}\times\\{v\\}))\Big{)}\oplus\Gamma_{j}(\ell,S)\qed$

######  Lemma 22 (Correctness of Equation 12).

Let $i$ be an introduce node with child $j$. Let $v\in V$ such that
$X_{i}=X_{j}\mathbin{\dot{\cup}}\\{v\\}$. Then for all $S\subseteq X_{i}$ and
all $0\leq\ell\leq\lvert F_{i}\rvert$ it holds that

$\pi_{2}\big{(}\Gamma_{i}(\ell,S)\ominus\Gamma_{j}(\ell,S\cap
X_{j})\big{)}=\begin{dcases}w_{i}(\partial v\cap(\\{v\\}\times(X_{i}\setminus
S)))&v\in S\\\ w_{i}(\partial S\cap(X_{i}\times\\{v\\}))&v\notin
S\end{dcases}.$ (12)

###### Proof.

Fix $S\subseteq X_{i}$ and $0\leq\ell\leq\lvert F_{i}\rvert$. If $v\in S$,
then by 20

$\Gamma_{i}(\ell,S)=\Big{(}1,\,w_{i}(\partial
v\cap(\\{v\\}\times(X_{i}\setminus
S)))\Big{)}\oplus\Gamma_{j}(\ell,S\setminus\\{v\\})$

and hence

$\displaystyle\pi_{2}\big{(}\Gamma_{i}(\ell,S)\ominus\Gamma_{j}(\ell,S\cap
X_{j})\big{)}$ $\displaystyle=\pi_{2}\left\lparen\Big{(}1,\,w_{i}(\partial
v\cap(\\{v\\}\times(X_{i}\setminus
S)))\Big{)}\oplus\Gamma_{j}(\ell,S\setminus\\{v\\})\ominus\Gamma_{j}(\ell,S\cap
X_{j})\right\rparen$ $\displaystyle=\pi_{2}\Big{(}1,\,w_{i}(\partial
v\cap(\\{v\\}\times(X_{i}\setminus
S)))\Big{)}\oplus\pi_{2}\big{(}\Gamma_{j}(\ell,S\setminus\\{v\\})\big{)}\ominus\pi_{2}\big{(}\Gamma_{j}(\ell,S\cap
X_{j})\big{)}$ $\displaystyle\overset{\mathclap{\begin{subarray}{c}{v\in
S\implies S\cap X_{j}=S\setminus\\{v\\}}\\\
\big{\downarrow}\end{subarray}}}{=}\pi_{2}\Big{(}1,\,w_{i}(\partial
v\cap(\\{v\\}\times(X_{i}\setminus
S)))\Big{)}\oplus\pi_{2}\big{(}\Gamma_{j}(\ell,S\setminus\\{v\\})\big{)}\ominus\pi_{2}\big{(}\Gamma_{j}(\ell,S\setminus\\{v\\})\big{)}$
$\displaystyle=\pi_{2}\Big{(}1,\,w_{i}(\partial
v\cap(\\{v\\}\times(X_{i}\setminus S)))\Big{)}$ $\displaystyle=w_{i}(\partial
v\cap(\\{v\\}\times(X_{i}\setminus S))).$

Now let $v\notin S$. Then, by 21,

$\displaystyle\pi_{2}\big{(}\Gamma_{i}(\ell,S)\ominus\Gamma_{j}(\ell,S\cap
X_{j})\big{)}$ $\displaystyle=\pi_{2}\left\lparen\Big{(}0,\,w_{i}(\partial
S\cap(X_{i}\times\\{v\\}))\Big{)}\oplus\Gamma_{j}(\ell,S)\ominus\Gamma_{j}(\ell,S\cap
X_{j})\right\rparen$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{v\notin S\implies S\cap
X_{j}=S}\\\
\big{\downarrow}\end{subarray}}}{=}\pi_{2}\left\lparen\Big{(}0,\,w_{i}(\partial
S\cap(X_{i}\times\\{v\\}))\Big{)}\oplus\Gamma_{j}(\ell,S)\ominus\Gamma_{j}(\ell,S)\right\rparen$
$\displaystyle=\pi_{2}{\Big{(}0,\,w_{i}(\partial
S\cap(X_{i}\times\\{v\\}))\Big{)}}\oplus\pi_{2}\big{(}\Gamma_{j}(\ell,S)\big{)}\ominus\pi_{2}\big{(}\Gamma_{j}(\ell,S)\big{)}$
$\displaystyle=\pi_{2}{\Big{(}0,\,w_{i}(\partial
S\cap(X_{i}\times\\{v\\}))\Big{)}}$ $\displaystyle=w_{i}(\partial
S\cap(X_{i}\times\\{v\\})).\qed$

####  A.5 Join Node

In order to prove the correctness for join nodes, we first need an auxiliary
statement. The next proposition is meant to deal with the aforementioned
?doubly counted edges? when building the maximum. Recall that for a join node
we claimed that

$\Gamma_{i}(\ell,S)=\bigg{(}\bigsqcup_{\begin{subarray}{c}0\leq\ell_{1}\leq\lvert
F_{j}\rvert\\\ 0\leq\ell_{2}\leq\lvert F_{k}\rvert\\\
\ell_{2}+\ell_{1}=\ell\end{subarray}}\big{(}\Gamma_{j}(\ell_{1},S)\oplus\Gamma_{k}(\ell_{2},S)\big{)}\bigg{)}\ominus\Big{(}\lvert
S\rvert,\,w_{i}(\partial S)\Big{)}.$

When considering the special case of Max-Bisection, this simplifies to

$\Gamma_{i}(\ell,S)=\bigg{(}\max_{\begin{subarray}{c}0\leq\ell_{1}\leq\lvert
F_{j}\rvert\\\ 0\leq\ell_{2}\leq\lvert F_{k}\rvert\\\
\ell_{2}+\ell_{1}=\ell\end{subarray}}\big{(}\Gamma_{j}(\ell_{1},S)+\Gamma_{k}(\ell_{2},S)\big{)}\bigg{)}-w_{i}(\partial
S).$

The intuition behind the subtraction is somewhat clear: If
$\Gamma_{j}(\ell_{1},S)$ is the largest possible cut in $G[Y_{j}]$ using $S$
and further $\ell_{1}$ vertices, and $\Gamma_{k}(\ell_{2},S)$ is the largest
possible cut in $G[Y_{k}]$ using $S$ and further $\ell_{2}$ vertices, their
sum includes some summands twice: The term $w_{i}(S)$. This is because all
other edges in the largest cut have at least on endpoint that is only in
$Y_{j}$ or only in $Y_{k}$ (outside $X_{i}$). The following proposition now
shows this formally; we need it for the proof of the correctness of the
equation for join nodes in the _general_ case as well as for the specific case
for Max-Bisection.

######  Proposition 23.

Let $i$ be a join node with left child $j$ and right child $j$. Then for all
$S\subseteq X_{i}$, $\widehat{S}_{1}\subseteq F_{j}$, and
$\widehat{S}_{2}\subseteq F_{k}$ we have

$w_{i}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2}))=w_{j}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}))+w_{k}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2}))-w_{i}(\partial
S\cap X_{i}^{2}).\penalty 9999\hbox{}\nobreak\hfill\quad\hbox{$\lrcorner$}$

###### Proof.

Fix $S\subseteq X_{i}$, $\widehat{S}_{1}\subseteq F_{j}$, and
$\widehat{S}_{2}\subseteq F_{k}$. We claim that it suffices to show that

  1. (i)

Show that
$\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})\cap
Y_{i}^{2}=\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap
Y_{j}^{2}\cup\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2})\cap Y_{k}^{2}$;
and

  2. (ii)

$\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap
Y_{j}^{2}\cap\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2})\cap
Y_{k}^{2}=\partial S\cap X_{i}^{2}$.

To see this, assume that both statements hold. We then have

$\displaystyle\\!\\!\\!\\!w_{i}(\partial
S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})$
$\displaystyle=\sum_{e\in(\partial
S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})\cap
Y_{i}^{2}}w(e)$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{(i)}}\\\
\big{\downarrow}\end{subarray}}}{=}\sum_{e\in\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap
Y_{j}^{2}\cup\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2})\cap
Y_{k}^{2}}w(e)$
$\displaystyle=\sum_{e\in\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap
Y_{j}^{2}}w(e)+\sum_{e\in\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2})\cap
Y_{k}^{2}}w(e)-\sum_{e\in\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap
Y_{j}^{2}\cap\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2})\cap
Y_{k}^{2}}w(e)$
$\displaystyle=w(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap
Y_{j}^{2})+w(\in\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2})\cap
Y_{k}^{2})-w(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap
Y_{j}^{2}\cap\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2})\cap Y_{k}^{2})$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{(ii)}}\\\
\big{\downarrow}\end{subarray}}}{=}w(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap
Y_{j}^{2})+w(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2})\cap
Y_{k}^{2})-w(\partial S\cap X_{i}^{)}$
$\displaystyle=w_{j}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}))+w_{k}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2}))-w_{i}(\partial
S\cap X_{i}^{2}).$

In order to prove (i) and (ii), we approach as follows: We simplify
$\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})\cap
Y_{i}^{2}$, $\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap Y_{j}^{2}$ and
$\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2})\cap Y_{k}^{2}$ each to a
disjunct union of simple terms. We the compare those ?summands? to prove our
goals. We start with the left hand side of the equation in (i), that is, the
term
$\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})\cap
Y_{i}^{2}$:

$\displaystyle\\!\\!\\!\\!\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})\cap
Y_{i}^{2}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{stmt:reduce}}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})\cap\big{(}(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})\times(Y_{i}\setminus(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2}))\big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{Def $Y_{i}$}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})\cap\big{(}(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})\times((X_{i}\mathbin{\dot{\cup}}F_{i}))\setminus(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2}))\big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{$i$ is join
node}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})\cap\big{(}(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})\times((X_{i}\mathbin{\dot{\cup}}F_{j}\mathbin{\dot{\cup}}F_{k}))\setminus(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2}))\big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{S\subseteq
X_{i},\,\widehat{S}_{1}\subseteq F_{j},\,\widehat{S}_{2}\subseteq F_{k}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})\cap\big{(}(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2})\times((X_{i}\setminus
S)\mathbin{\dot{\cup}}(F_{j}\setminus\widehat{S}_{1})\mathbin{\dot{\cup}}(F_{k}\setminus\widehat{S}_{2}))\big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{{\text{\hyperref@@ii[l4:three:left]{\autoref*{l4}\ref*{l4:three:left}}},\,\text{\hyperref@@ii[l4:three:right]{\autoref*{l4}\ref*{l4:three:right}}}}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial S\cap(S\times(X_{i}\setminus
S))\mathbin{\dot{\cup}}\partial
S\cap(S\times(F_{j}\setminus\widehat{S}_{1}))\mathbin{\dot{\cup}}\partial
S\cap(S\times(F_{k}\setminus\widehat{S}_{2}))$
$\displaystyle\phantom{{}={}}\mathbin{\dot{\cup}}\partial\widehat{S}_{1}\cap(\widehat{S}_{1}\times(X_{i}\setminus
S))\mathbin{\dot{\cup}}\partial\widehat{S}_{1}\cap(\widehat{S}_{1}\times(F_{j}\setminus\widehat{S}_{1}))\mathbin{\dot{\cup}}\underbrace{\partial\widehat{S}_{1}\cap(\widehat{S}_{1}\times(F_{k}\setminus\widehat{S}_{2}))}_{=\emptyset}$
$\displaystyle\phantom{{}={}}\mathbin{\dot{\cup}}\partial\widehat{S}_{2}\cap(\widehat{S}_{2}\times(X_{i}\setminus
S))\mathbin{\dot{\cup}}\underbrace{\partial\widehat{S}_{2}\cap(\widehat{S}_{2}\times(F_{j}\setminus\widehat{S}_{1}))}_{=\emptyset}{}\mathbin{\dot{\cup}}{}\partial\widehat{S}_{2}\cap(\widehat{S}_{2}\times(F_{k}\setminus\widehat{S}_{2}))$
(H1) Let us now consider the first expression on the right side of the
equation of (i):
$\displaystyle\\!\\!\\!\\!\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap
Y_{j}^{2}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{stmt:reduce}}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap\big{(}(S\mathbin{\dot{\cup}}\widehat{S}_{1})\times(Y_{j}\setminus(S\mathbin{\dot{\cup}}\widehat{S}_{1}))\big{)}$
$\displaystyle=\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap\big{(}(S\mathbin{\dot{\cup}}\widehat{S}_{1})\times((F_{j}\mathbin{\dot{\cup}}X_{j})\setminus(S\mathbin{\dot{\cup}}\widehat{S}_{1}))\big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{X_{i}=X_{j}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap\big{(}(S\mathbin{\dot{\cup}}\widehat{S}_{1})\times((F_{j}\mathbin{\dot{\cup}}X_{i})\setminus(S\mathbin{\dot{\cup}}\widehat{S}_{1}))\big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{S\subseteq
X_{i},\,\widehat{S}_{1}\subseteq F_{j}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap\big{(}(S\mathbin{\dot{\cup}}\widehat{S}_{1})\times((X_{i}\setminus
S)\mathbin{\dot{\cup}}(F_{j}\setminus\widehat{S}_{1}))\big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{{\text{\hyperref@@ii[l4:three:left]{\autoref*{l4}\ref*{l4:three:left}}},\,\text{\hyperref@@ii[l4:three:right]{\autoref*{l4}\ref*{l4:three:right}}}}}\\\
\big{\downarrow}\end{subarray}}}{=}\partial S\cap(S\times(X_{i}\setminus
S))\mathbin{\dot{\cup}}\partial S\cap(S\times(F_{j}\setminus\widehat{S}_{1}))$
$\displaystyle\phantom{{}={}}\mathbin{\dot{\cup}}\partial\widehat{S}_{1}\cap(\widehat{S}_{1}\times(X_{i}\setminus
S))\mathbin{\dot{\cup}}\partial\widehat{S}_{1}\cap(\widehat{S}_{1}\times(F_{j}\setminus\widehat{S}_{1}))$
(H2) Analogously, we can also show
$\displaystyle\\!\\!\\!\\!\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1})\cap
Y_{k}^{2}$ $\displaystyle=\partial S\cap(S\times(X_{i}\setminus
S))\mathbin{\dot{\cup}}\partial S\cap(S\times(F_{k}\setminus\widehat{S}_{2}))$
$\displaystyle\phantom{{}={}}\mathbin{\dot{\cup}}\partial\widehat{S}_{2}\cap(\widehat{S}_{2}\times(X_{i}\setminus
S))\mathbin{\dot{\cup}}\partial\widehat{S}_{2}\cap(\widehat{S}_{2}\times(F_{k}\setminus\widehat{S}_{2}))$
(H3)

Now observe that each ?summand? (that is not the empty set) in (H1) appears in
(H2) and (H3), and vice versa. This proves (i).

For (ii), let us compare the ?summands? of (H2) and (H3). First observe, that
each pair of those has to be identical or disjunct. This is due to the fact
that all ?summands? of (H2) and (H3) also appear in (H1), as we observed
above, and (H1) is a disjunct union. It is now not hard to see which pair of
summands are identical and which are disjunct: Any ?summand? starting with
$\partial\widehat{S}_{1}$ (recall that $\widehat{S}_{1}\subseteq F_{j})$ in
(H2) cannot occur in (H3) due to coherence (unless the ?summand? is
$\emptyset$), and analogously, no ?summand? starting with
$\partial\widehat{S}_{2}$ (recall that $\widehat{S}_{2}\subseteq F_{k}$) in
(H3) can occur in (H2). Moreover, the same applies to ?summands? in (H2) that
are intersected with a subset of $V\times F_{j}$; and analogously, to
?summands? in (H3) that are intersected with a subset of $V\times F_{k}$. The
only ?summand? left is $\partial S\cap(S\times(X_{i}\setminus S))$, and this
summand occurs (in this very syntactical form) in both, (H2) and (H3). This
shows (ii) and hence eventually the claim. ∎

######  Lemma 24 (Correctness of Equation 13).

Let $i$ be a join node with left child $j$ and right child $j$. Then for all
$0\leq\ell\leq\lvert F_{i}\rvert$ and all $S\subseteq X_{i}$ we have

$\Gamma_{i}(\ell,S)=\bigg{(}\bigsqcup_{\begin{subarray}{c}0\leq\ell_{1}\leq\lvert
F_{j}\rvert\\\ 0\leq\ell_{2}\leq\lvert F_{k}\rvert\\\
\ell_{2}+\ell_{1}=\ell\end{subarray}}\big{(}\Gamma_{j}(\ell_{1},S)\oplus\Gamma_{k}(\ell_{2},S)\big{)}\bigg{)}\ominus\Big{(}\lvert
S\rvert,\,w_{i}(\partial S)\Big{)}.$

###### Proof.

Fix $S\subseteq X_{i}$ and $0\leq\ell\leq\lvert F_{i}\rvert$. By the
definition of $\Gamma$ we have:

$\displaystyle\\!\\!\\!\\!{\Gamma}_{i}(\ell,S)$
$\displaystyle=\bigsqcup_{\widehat{S}\in\binom{F_{i}}{\ell}}\Big{(}\ell+\lvert
S\rvert,\,w_{i}(\partial(S\mathbin{\dot{\cup}}\widehat{S}))\Big{)}$
$\displaystyle=\bigsqcup_{\begin{subarray}{c}0\leq\ell_{1}\leq\ell\\\
\ell_{2}=\ell-\ell_{1}\\\ \widehat{S}_{1}\in\binom{F_{j}}{\ell_{1}}\\\
\widehat{S}_{2}\in\binom{F_{k}}{\ell_{2}}\end{subarray}}\Big{(}\ell+\lvert
S\rvert,\,w_{i}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}\mathbin{\dot{\cup}}\widehat{S}_{2}))\Big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{stmt:join:propo}}}\\\
\big{\downarrow}\end{subarray}}}{=}\bigsqcup_{\begin{subarray}{c}0\leq\ell_{1}\leq\ell\\\
\ell_{2}=\ell-\ell_{1}\\\ \widehat{S}_{1}\in\binom{F_{j}}{\ell_{1}}\\\
\widehat{S}_{2}\in\binom{F_{k}}{\ell_{2}}\end{subarray}}\Big{(}\ell+\lvert
S\rvert,\,w_{j}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}))+w_{k}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2}))-w_{i}(\partial
S)\Big{)}$
$\displaystyle=\bigsqcup_{\begin{subarray}{c}0\leq\ell_{1}\leq\ell\\\
\ell_{2}=\ell-\ell_{1}\end{subarray}}\bigsqcup_{\widehat{S}_{1}\in\binom{F_{j}}{\ell_{1}}}\bigsqcup_{\widehat{S}_{2}\in\binom{F_{k}}{\ell_{2}}}\Big{(}\ell+\lvert
S\rvert,\,w_{j}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}))+w_{k}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2}))-w_{i}(\partial
S)\Big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{stmt:compatible}}}\\\
\big{\downarrow}\end{subarray}}}{=}\phantom{x\,}\left(\bigsqcup_{\begin{subarray}{c}0\leq\ell_{1}\leq\ell\\\
\ell_{2}=\ell-\ell_{1}\end{subarray}}\bigsqcup_{\widehat{S}_{1}\in\binom{F_{j}}{\ell_{1}}}\bigsqcup_{\widehat{S}_{2}\in\binom{F_{k}}{\ell_{2}}}\Big{(}\ell+2\lvert
S\rvert,\,w_{j}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}))+w_{k}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2}))\Big{)}\right)$
$\displaystyle\phantom{{}={}}\ominus\Big{(}\lvert S\rvert,\,w_{i}(\partial
S)\Big{)}$
$\displaystyle\overset{\mathclap{\begin{subarray}{c}{\text{\autoref{stmt:compatible}}}\\\
\big{\downarrow}\end{subarray}}}{=}\phantom{x\,}\left(\bigsqcup_{\begin{subarray}{c}0\leq\ell_{1}\leq\ell\\\
\ell_{2}=\ell-\ell_{1}\end{subarray}}\bigsqcup_{\widehat{S}_{1}\in\binom{F_{j}}{\ell_{1}}}\bigsqcup_{\widehat{S}_{2}\in\binom{F_{k}}{\ell_{2}}}\\!\\!\\!\\!\left\lparen\Big{(}\ell_{1}+\lvert
S\rvert,\,w_{j}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}))\Big{)}\oplus\Big{(}\ell_{2}+\lvert
S\rvert,\,w_{k}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2}))\Big{)}\right\rparen\\!\\!\right)\hskip-20.00003pt$
$\displaystyle\phantom{{}={}}\ominus\Big{(}\lvert S\rvert,\,w_{i}(\partial
S)\Big{)}$ $\displaystyle=\left(\bigsqcup_{\begin{subarray}{c}\lvert
S\rvert\leq\ell_{1}\leq\ell\\\
\ell_{2}=\ell-\ell_{1}\end{subarray}}\left\lparen\bigsqcup_{\widehat{S}_{1}\in\binom{F_{j}}{\ell_{1}}}\\!\\!\\!\\!\Big{(}\ell_{1}+\lvert
S\rvert,\,w_{j}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{1}))\Big{)}\oplus\bigsqcup_{\widehat{S}_{2}\in\binom{F_{k}}{\ell_{2}}}\\!\\!\\!\\!\Big{(}\ell_{2}+\lvert
S\rvert,\,w_{k}(\partial(S\mathbin{\dot{\cup}}\widehat{S}_{2}))\Big{)}\\!\\!\right\rparen\\!\\!\right)\hskip-20.00003pt$
$\displaystyle\phantom{{}={}}\ominus\Big{(}\lvert S\rvert,\,w_{i}(\partial
S)\Big{)}$
$\displaystyle=\left(\bigsqcup_{\begin{subarray}{c}0\leq\ell_{1}\leq\ell\\\
\ell_{2}=\ell-\ell_{1}\end{subarray}}\big{(}{\Gamma}_{j}(\ell_{1},S)\oplus{\Gamma}_{k}(\ell_{2},S)\big{)}\right)\ominus\Big{(}\lvert
S\rvert,\,w_{i}(\partial S)\Big{)}.\qed$

###  Appendix B Running Time Of Our Framework

###  Appendix C Hardness

We need the following Proposition in order to be able to show that the
hardness result of Max-Cut by [15] can be extended to the case where a tree
decomposition is given as part of the input. The idea is to compute such a
decomposition for the result of their reduction from SAT to Max-Cut in
polynomial time.

######  Proposition 25.

Let $G=(V,E)$ and $S\subseteq V$. If $G-S$ is a forest, then (given $S$) one
can compute a small tree decomposition of $G$ that has width $\leq\lvert
S\rvert+1$ in time $\operatorname{\mathcal{O}}(\operatorname{poly}(\lvert
E\rvert+\lvert V\rvert))$.  $\lrcorner$

###### Proof.

Fix $G=(V,E)$ and $S$. Note that it is trivially possible to compute a small
tree decomposition of a tree in time linear in its nodes and edges. Compute
the tree decompositions for all connected components in $G^{\prime}\coloneqq
G-S$ (which are all trees by assumption). Rename the node sets (and all the
occurrences accordingly) of the decompositions such that the union of all node
sets is of the form $[k]\setminus\set{1}$ for some $k\in\mathds{N}$ and the
node sets are disjunct. Add a new node $1$ to the forest of tree
decompositions and set the associated bag to be $X_{1}\coloneqq\emptyset$.
Connect the new node $1$ to an arbitrary node of each tree decomposition. It
is easy to check that we just constructed a small tree decomposition for
$G^{\prime}$ of width $1$. Now modify this decomposition to a small tree
decomposition of $G$ as follows: Add the set $S$ to all bags. Again, it is
easy to check that we obtain a small tree decomposition of $G$. The same holds
for the running time. The width of the constructed decomposition is bounded
from above by the term $1+\lvert S\rvert$ as every bag of the decomposition
for $G^{\prime}$ had at most $2$ vertices before we added the vertices within
$S$. ∎

######  Lemma 26.

There is no
$\operatorname{\mathcal{O}}((2-\varepsilon)^{t}\operatorname{poly}n)$
algorithm to decide Max-Cut for any $\varepsilon\geq 0$.  $\lrcorner$

###### Proof.

Consider the graph created in the reduction by [15] and observe that following
statements:

  1. 1.

The number of vertices after the reduction is
$\operatorname{\mathcal{O}}(\lvert\phi\rvert+n)=\operatorname{\mathcal{O}}(\lvert\phi\rvert)$;

  2. 2.

For every clause there is exactly one cycle created;

  3. 3.

Any pair of such cycles does share exactly one vertex: $x_{0}$;

  4. 4.

Apart from those partially overlapping cycles, there are only $n$ additional
vertices;

  5. 5.

Every vertex on those cycles that is not $x_{0}$ has degree at most $3$ as it
is connected to at most one $\widehat{v}_{i}$;

From (4) and (5) we can now deduce that the number of edges after the
reduction is $\operatorname{\mathcal{O}}(\lvert\phi\rvert)$. Thus the encoding
of the graph has asymptotically the same size as the encoding of $\phi$. The
correctness of the reduction was shown in [15].

Now observe that (3) and (4) imply that removing all variable vertices
$\widehat{v}_{i}$ and $x_{0}$ does result in a set of paths. This is exactly
the statement we need in order to be able to apply 25 which completes the
proof. ∎