11institutetext: Tokyo Institute of Technology, Meguro, Japan
11email<EMAIL_ADDRESS>
11email<EMAIL_ADDRESS>
# Characterization of the Imbalance Problem on Complete Bipartite Graphs

Steven Ge  Toshiya Itoh

###### Abstract

We study the imbalance problem on complete bipartite graphs. The imbalance
problem is a graph layout problem and is known to be NP-complete. Graph layout
problems find their applications in the optimization of networks for parallel
computer architectures, VLSI circuit design, information retrieval, numerical
analysis, computational biology, graph theory, scheduling and archaeology [2].
In this paper, we give characterizations for the optimal solutions of the
imbalance problem on complete bipartite graphs. Using the characterizations,
we can solve the imbalance problem in time polylogarithmic in the number of
vertices, when given the cardinalities of the parts of the graph, and verify
whether a given solution is optimal in time linear in the number of vertices
on complete bipartite graphs. We also introduce a generalized form of complete
bipartite graphs on which the imbalance problem is solvable in time
quasilinear in the number of vertices by using the aforementioned
characterizations.

###### Keywords:

Imbalance Problem Vertex layout Complete bipartite graph Proper interval
bipartite graph.

##  1 Introduction

Graph layout problems are combinatorial optimization problems, where the goal
is to find an ordering on the vertices that optimizes an objective function. A
large number of problems from different domains can be formulated as graph
layout problems [2]. The imbalance problem is a graph layout problem that has
applications in 3-dimensional circuit design [7].

The imbalance problem was introduced by Biedl et al. [1]. Given an ordering of
the vertices of a graph $G$, the imbalance of a vertex $v$ is the absolute
difference in the number of neighbors to the left of $v$ and the number of
neighbors to the right of $v$. The imbalance of an ordering is the sum of the
imbalances of the vertices. An instance of the imbalance problem consists of a
graph $G$ and an integer $k$. The problem asks whether there exists an
ordering on the vertices of $G$ such that the imbalance of the ordering is at
most $k$.

The imbalance problem is NP-complete for several graph classes, including
bipartite graphs with degree at most 6, weighted trees [1], general graphs
with degree at most 4 [6], and split graphs [4]. The problem becomes
polynomial time solvable on superfragile graphs [4]. The problem is linear
time solvable on proper interval graphs [4], bipartite permutation graphs, and
threshold graphs [3].

Gorzny showed that the minimum imbalance of a bipartite permutation graph
$G=(V,E)$, which class is a superclass of complete bipartite graphs and proper
interval bipartite graphs, can be computed in $\mathcal{O}(|V|+|E|)$ time [3].
We give characterizations for the optimal solutions of the imbalance problem
on complete bipartite graphs. Using the characterizations, we show that the
imbalance problem is solvable in $\mathcal{O}(\log(|V|)\cdot\log(\log(|V|)))$
time on complete bipartite graphs, when given the cardinalities of the parts
of the graph. Additionally, using the characterizations, we can verify whether
a given solution is optimal in $O(|V|)$ on complete bipartite graphs. We also
introduce a generalized form of complete bipartite graphs, which we call
chained complete bipartite graphs, on which the imbalance problem is solvable
in $\mathcal{O}(c\cdot\log(|V|)\cdot\log(\log(|V|)))$ time, where
$c=\mathcal{O}(|V|)$, by using the aforementioned characterizations. As
chained complete bipartite graphs are a subclass of proper interval bipartite
graphs, the result of Gorzny also applies to chained complete bipartite
graphs.

##  2 Preliminaries

We only consider graphs that are finite, undirected, connected, and simple
(i.e. without multiple edges or loops). A graph $G$ is denoted as $G=(V,E)$,
where $V$ denotes the set of vertices and $E\subseteq V\times V$ denotes the
set of undirected edges. For convenience, we abbreviate bipartite graph as
bigraph.

For $n\in\mathbb{N}^{+}$, let us define $[n]=\\{1,2,\dots,n\\}.$

We define $\sigma_{S}:S\rightarrow[|S|]$ to be an ordering of $S$. For
convenience, at times we denote an ordering $\sigma_{S}$ by
$(\sigma^{-1}(1),\sigma^{-1}(2),\dots,\sigma^{-1}(|S|)),$ where,
$v=\sigma^{-1}(\sigma(v))$ for $v\in S$. We also say that $v\in S$ is at
position $k$ in ordering $\sigma_{S}$ if $\sigma_{S}(v)=k$.

Let $S_{1},S_{2},\dots,S_{n}$ be a collection of disjoint sets. Let $s\in
S_{i}$, where $1\leq i\leq n$, then the concatenation of orderings is defined
as follows:
$\sigma_{S_{1}}\sigma_{S_{2}}\dots\sigma_{S_{n}}(s)=\sigma_{S_{i}}(s)+\sum\limits_{j=1}^{i-1}|S_{j}|.$
Additionally, we use the product notation to denote the concatenation over a
set. That is,
$\prod\limits_{i=1}^{n}\sigma_{S_{i}}=\sigma_{S_{1}}\sigma_{S_{2}}\dots\sigma_{S_{n}}.$

Given an ordering $\sigma_{S}$ we say that $v\in S$ occurs to the left of
$u\in S$ in $\sigma_{S}$, if and only if $\sigma_{S}(v)<\sigma_{S}(u)$. We
denote this as $v<_{\sigma_{S}}u.$ We define $>_{\sigma_{S}}$ analogously.

Given an ordering $\sigma_{S}$ we say that $\sigma_{S}^{S^{\prime}}$, where
$S^{\prime}\subseteq S$, is a subordering of $\sigma_{S}$ on $S^{\prime}$ if
$\sigma_{S}^{S^{\prime}}$ preserves the relative ordering of the elements in
$S^{\prime}$. That is $\sigma_{S}^{S^{\prime}}$ is a subordering of
$\sigma_{S}$ if and only if $\forall_{u,v\in
S^{\prime}}\forall_{\oplus\in\\{<,>\\}}~{}u\oplus_{\sigma_{S}^{S^{\prime}}}v\iff
u\oplus_{\sigma_{S}}v.$

For a graph $G=(V,E)$, the open neighborhood of a vertex $v\in V$, denoted by
$N(v)$, is the set of vertices adjacent to $v$. We call the vertices in $N(v)$
the neighbors of vertex $v$. That is $N(v)=\\{u\in V~{}|~{}\\{u,v\\}\in E\\}.$

The imbalance of a vertex $v\in V$ on the ordering $\sigma_{V}$ in graph
$G=(V,E)$, denoted by $I(v,\sigma_{V},G)$, is defined to be the absolute
difference in the number of neighbors of $v$ occurring to the left of $v$ and
the number of neighbors of $v$ occurring to the right of $v$ in $\sigma_{V}$.
That is, $I(v,\sigma_{V},G)=\big{|}|\\{u\in
N(v)~{}|~{}u<_{\sigma_{V}}v\\}|-|\\{u\in
N(v)~{}|~{}u>_{\sigma_{V}}v\\}|\big{|}.$

The imbalance of an ordering $\sigma_{V}$ on graph $G=(V,E)$, denoted by
$I(\sigma_{V},G)$, is defined to be sum over the imbalances of the vertices in
$V$ on the ordering $\sigma_{V}$ in graph $G$. That is
$I(\sigma_{V},G)=\sum\limits_{v\in V}I(v,\sigma_{V},G).$ If the ordering
and/or graph are clear from the context, we shall exclude them from the
parameters of the function $I$.

The imbalance of a graph $G=(V,E)$, denoted by $I(G)$, is defined to be the
minimum imbalance over all orderings $\sigma_{V}$. That is,
$I(G)=\min\limits_{\sigma_{V}\in S(V)}I(\sigma_{V},G),$ where $S(V)$ denotes
the set of all orderings on $V$. We call an ordering $\sigma_{V}$ whose
imbalance is equivalent to $I(G)$ an (imbalance) optimal ordering. Given a
graph $G$ and an integer $k$, the imbalance problem asks whether $I(G)\leq k$
is true or false.

A bigraph $G=(X,Y,E)$ is an interval bigraph, if there exists a set of
intervals on the real line, where for each vertex $v\in X\cup Y$ we have
exactly one corresponding interval such that the intervals corresponding to
vertices $x\in X$ and $y\in Y$ intersect if and only if there exists an edge
in $E$ connecting $x$ and $y$. We call such a set of intervals the interval
representation $I_{G}$ of graph $G$. That is,
$I_{G}=\\{[l_{v},r_{v}]~{}|~{}v\in X\cup Y\\}$ such that $\forall_{x\in
X}~{}\forall_{y\in
Y}~{}\big{(}[l_{x},r_{x}]\cap[l_{y},r_{y}]\neq\emptyset\iff\\{x,y\\}\in
E\big{)}.$

An interval bigraph $G=(X,Y,E)$ is a proper interval bigraph, abbreviated by
PI-bigraph, if it has an interval representation $I_{G}$ such that none of the
intervals are properly contained in another. That is, there exists an interval
representation $I_{G}=\\{[l_{v},r_{v}]~{}|~{}v\in X\cup Y\\}$ of $G$ such that
$\forall_{u,v\in X\cup Y}~{}(u\neq
v\iff[l_{u},r_{u}]\nsubseteq[l_{v},r_{v}]).$

##  3 Imbalance on Complete bipartite graphs

Let $G=(X,Y,E)$ be a complete bigraph. We shall prove that the minimum
imbalance of $G$ is $|X|\cdot|Y|+(|X|\mod 2)\cdot(|Y|\mod 2)$.

###### Lemma 1

If $G=(X,Y,E)$ is a complete bigraph, then there exists an ordering
$\sigma_{X\cup Y}$ such that $I(\sigma_{X\cup Y})=|X|\cdot|Y|+(|X|\mod
2)\cdot(|Y|\mod 2).$

###### Proof

The proof constructs an ordering on $X\cup Y$ and considers two cases, either
the cardinality one part is even or none of the cardinalities of the parts are
even.

###### Case 1

$(|X|\mod 2=0)\vee(|Y|\mod 2=0).$
W.l.o.g. assume that $|Y|$ is even. Let $Y_{1}$ and $Y_{2}$ partition $Y$ into
two sets of equal size. Consider ordering $\sigma_{X\cup
Y}=\sigma_{Y_{1}}\sigma_{X}\sigma_{Y_{2}}$. In this ordering, the imbalance of
any vertex in $X$ is zero and the imbalance of any vertex in $Y$ is $|X|$.
Thus the imbalance of ordering $\sigma_{X\cup Y}$ is $I(\sigma_{X\cup
Y})=|X|\cdot|Y|.$

$\sigma_{Y_{1}}\sigma_{X}\sigma_{Y_{2}}=~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$Y_{1}$$X$$Y_{2}$

Figure 1: Example of “sandwiched” ordering for $G=K_{4,9}$.

###### Case 2

$(|X|\mod 2=1)\wedge(|Y|\mod 2=1).$
Let $y_{m}\in Y$ be an element of $Y$. Let $X_{1}$ and $X_{2}$ partition $X$
into two sets such that $||X_{1}|-|X_{2}||=1$ and let $Y_{1}$ and $Y_{2}$
partition $Y\setminus\\{y_{m}\\}$ into two sets such that $|Y_{1}|=|Y_{2}|$.
Consider the ordering $\sigma_{X\cup
Y}=\sigma_{Y_{1}}\sigma_{X_{1}}\sigma_{\\{y_{m}\\}}\sigma_{X_{2}}\sigma_{Y_{2}}$.
The imbalance of any vertex in $X\cup\\{y_{m}\\}$ is 1 and the imbalance of
any vertex in $Y\setminus\\{y_{m}\\}$ is $|X|$. Thus the imbalance of the
ordering $\sigma_{X\cup Y}$ is $I(\sigma_{X\cup Y})=|X|\cdot|Y|+1$.

$\sigma_{Y_{1}}\sigma_{X_{1}}\sigma_{\\{y_{m}\\}}\sigma_{X_{2}}\sigma_{Y_{2}}=~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$
$Y_{1}$$X_{1}$$\\{y_{m}\\}$$X_{2}$$Y_{2}$

Figure 2: Example of “pseudo-sandwich” ordering for $G=K_{3,9}$.

###### Definition 1

Let $G=(X,Y,E)$ be a complete bigraph and $\sigma_{X\cup Y}$ be an arbitrary
ordering on $X\cup Y$. We define $L(Y,\sigma_{X\cup Y})\subseteq[|X|+|Y|]$ to
be the positions of the elements of $Y$ in $\sigma_{X\cup Y}$. That is
$L(Y,\sigma_{X\cup Y})=\\{\sigma_{X\cup Y}(y)~{}|~{}y\in Y\\}.$ Let us denote
the elements in $L(Y,\sigma_{X\cup Y})$ as $L(Y,\sigma_{X\cup
Y})=\\{l^{\sigma_{X\cup Y}}_{1},l^{\sigma_{X\cup
Y}}_{2},\dots,l^{\sigma_{X\cup Y}}_{|Y|}\\}$ such that $l^{\sigma_{X\cup
Y}}_{1}<l^{\sigma_{X\cup Y}}_{2}<\dots<l^{\sigma_{X\cup Y}}_{|Y|}$.
Additionally, we define $l^{\sigma_{X\cup Y}}_{0}=0$ and $l^{\sigma_{X\cup
Y}}_{|Y|+1}=|X|+|Y|+1$. We leave out the superscript in $l^{\sigma_{X\cup
Y}}_{i}$, when the ordering is clear from the context.

Additionally, we define $L^{\sigma_{X\cup Y}}_{i}$ to be the vertices of $X$
between the positions $l_{i}$ and $l_{i+1}$ in ordering $\sigma_{X\cup Y}$.
Let $Y=\\{y_{1},\dots,y_{|Y|}\\}$ be an arbitrary enumeration of the element
in $Y$. We leave out the superscript in $L^{\sigma_{X\cup Y}}_{i}$, when the
ordering is clear from the context.

$\sigma_{X\cup
Y}=~{}~{}~{}$$x_{1}$$x_{2}$$y_{1}$$x_{3}$$y_{2}$$x_{4}$$x_{5}$$x_{6}$$y_{3}$$x_{7}$$x_{8}$$y_{4}$$x_{9}$$x_{10}$$\sigma_{X\cup
Y}(v)=$1234567891011121314

$=$

$=$

$=$

$=$

$l_{1}$$l_{2}$$l_{3}$$l_{4}$$L_{0}$$L_{1}$$L_{2}$$L_{3}$$L_{4}$

Figure 3: Visualization of Definition 1 .

###### Definition 2

Let $\sigma_{X\cup
Y}=\sigma_{L_{0}}\prod\limits_{i=1}^{|Y|}\sigma_{\\{y_{i}\\}}\sigma_{L_{i}}$
be an arbitrary ordering. Let us define

$shift_{L}(\sigma_{X\cup
Y})=\sigma_{\\{y_{\lfloor\frac{|Y|}{2}\rfloor}\\}}\sigma_{L_{0}}\Bigg{(}\prod\limits_{i=1}^{\lfloor\frac{|Y|}{2}\rfloor-1}\sigma_{\\{y_{i}\\}}\sigma_{L_{i}}\Bigg{)}\sigma_{L_{\lfloor\frac{|Y|}{2}\rfloor}}\Bigg{(}\prod\limits_{i=\lfloor\frac{|Y|}{2}\rfloor+1}^{|Y|}\sigma_{\\{y_{i}\\}}\sigma_{L_{i}}\Bigg{)},$
$shift_{R}(\sigma_{X\cup
Y})=\sigma_{L_{0}}\Bigg{(}\prod\limits_{i=1}^{\lceil\frac{|Y|}{2}\rceil}\sigma_{\\{y_{i}\\}}\sigma_{L_{i}}\Bigg{)}\sigma_{L_{\lceil\frac{|Y|}{2}\rceil+1}}\Bigg{(}\prod\limits_{i=\lceil\frac{|Y|}{2}\rceil+2}^{|Y|}\sigma_{\\{y_{i}\\}}\sigma_{L_{i}}\Bigg{)}\sigma_{\\{y_{\lceil\frac{|Y|}{2}\rceil+1}\\}}.$

That is, $shift_{L}$ moves vertex $y_{\lfloor\frac{|Y|}{2}\rfloor}$ to the
left most position and $shift_{R}$ moves vertex
$y_{\lceil\frac{|Y|}{2}\rceil+1}$ to the right most position.

pt$\sigma_{X\cup Y}=$
$x_{1}$$x_{2}$$y_{1}$$x_{3}$$y_{2}$$x_{4}$$x_{5}$$x_{6}$$y_{3}$$x_{7}$$x_{8}$$y_{4}$$x_{9}$$x_{10}$pt$shift_{L}(\sigma_{X\cup
Y})=$ $y_{2}$$x_{1}$$x_{2}$$y_{1}$$x_{3}$
$x_{4}$$x_{5}$$x_{6}$$y_{3}$$x_{7}$$x_{8}$$y_{4}$$x_{9}$$x_{10}$pt$shift_{R}(\sigma_{X\cup
Y})=$ $x_{1}$$x_{2}$$y_{1}$$x_{3}$$y_{2}$$x_{4}$$x_{5}$$x_{6}$
$x_{7}$$x_{8}$$y_{4}$$x_{9}$$x_{10}$$y_{3}$$L_{0}^{\sigma_{X\cup
Y}}$$L_{1}^{\sigma_{X\cup Y}}$$L_{2}^{\sigma_{X\cup Y}}$$L_{3}^{\sigma_{X\cup
Y}}$$L_{4}^{\sigma_{X\cup Y}}$

Figure 4: Visualization of the $shift_{L}$ and $shift_{R}$ functions with an
ordering $\sigma_{X\cup Y}$ on the vertices of graph $G=K_{10,4}$.

###### Lemma 2

Let $\sigma_{X\cup Y}$ be an arbitrary imbalance optimal ordering. Let
$\sigma^{\prime}_{X\cup Y}=shift_{L}(\sigma_{X\cup Y})$. We have that
$I(\sigma_{X\cup Y})=I(\sigma^{\prime}_{X\cup Y})$.

###### Proof

We have that $I(\sigma_{X\cup
Y},y_{\lfloor\frac{|Y|}{2}\rfloor})=\Bigg{|}\Bigg{(}\sum\limits_{i=0}^{\lfloor\frac{|Y|}{2}\rfloor-1}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}-\Bigg{(}\sum\limits_{i=\lfloor\frac{|Y|}{2}\rfloor}^{|Y|}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}\Bigg{|}$ and $I(\sigma^{\prime}_{X\cup
Y},y_{\lfloor\frac{|Y|}{2}\rfloor})=\sum\limits_{i=0}^{|Y|}|L^{\sigma_{X\cup
Y}}_{i}|=|X|$. For each $0\leq i\leq\lfloor\frac{|Y|}{2}\rfloor-1$, the
imbalance of all the vertices in $L^{\sigma_{X\cup Y}}_{i}$ is smaller by 2 in
$\sigma^{\prime}_{X\cup Y}$. The imbalance of the remaining vertices remain
the same.

###### Case 3

$\Bigg{(}\sum\limits_{i=0}^{\lfloor\frac{|Y|}{2}\rfloor-1}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}>\Bigg{(}\sum\limits_{i=\lfloor\frac{|Y|}{2}\rfloor}^{|Y|}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}$.
We can express the imbalance of $I(\sigma^{\prime}_{X\cup Y})$ as follows:

$\displaystyle I(\sigma^{\prime}_{X\cup Y})$ $\displaystyle=I(\sigma_{X\cup
Y})-2\cdot\Bigg{(}\sum\limits_{i=0}^{\lfloor\frac{|Y|}{2}\rfloor-1}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}-I(\sigma_{X\cup Y},y_{\lfloor\frac{|Y|}{2}\rfloor})$
$\displaystyle+I(\sigma^{\prime}_{X\cup Y},y_{\lfloor\frac{|Y|}{2}\rfloor})$
$\displaystyle=I(\sigma_{X\cup
Y})-2\cdot\Bigg{(}\sum\limits_{i=0}^{\lfloor\frac{|Y|}{2}\rfloor-1}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}-\Bigg{(}\sum\limits_{i=0}^{\lfloor\frac{|Y|}{2}\rfloor-1}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}$
$\displaystyle+\Bigg{(}\sum\limits_{i=\lfloor\frac{|Y|}{2}\rfloor}^{|Y|}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}+\sum\limits_{i=0}^{|Y|}|L^{\sigma_{X\cup Y}}_{i}|$
$\displaystyle<I(\sigma_{X\cup Y}).$

Since $\sigma_{X\cup Y}$ it is not possible that $I(\sigma^{\prime}_{X\cup
Y})<I(\sigma_{X\cup Y})$. Thus this case can not occur.

###### Case 4

$\Bigg{(}\sum\limits_{i=0}^{\lfloor\frac{|Y|}{2}\rfloor-1}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}\leq\Bigg{(}\sum\limits_{i=\lfloor\frac{|Y|}{2}\rfloor}^{|Y|}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}$.
We can express the imbalance of $I(\sigma^{\prime}_{X\cup Y})$ as follows:

$\displaystyle I(\sigma^{\prime}_{X\cup Y})$ $\displaystyle=I(\sigma_{X\cup
Y})-2\cdot\Bigg{(}\sum\limits_{i=0}^{\lfloor\frac{|Y|}{2}\rfloor-1}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}-I(\sigma_{X\cup Y},y_{\lfloor\frac{|Y|}{2}\rfloor})$
$\displaystyle+I(\sigma^{\prime}_{X\cup Y},y_{\lfloor\frac{|Y|}{2}\rfloor})$
$\displaystyle=I(\sigma_{X\cup
Y})-2\cdot\Bigg{(}\sum\limits_{i=0}^{\lfloor\frac{|Y|}{2}\rfloor-1}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}-\Bigg{(}\sum\limits_{i=\lfloor\frac{|Y|}{2}\rfloor}^{|Y|}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}$
$\displaystyle+\Bigg{(}\sum\limits_{i=0}^{\lfloor\frac{|Y|}{2}\rfloor-1}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}+\sum\limits_{i=0}^{|Y|}|L_{i}|$
$\displaystyle=I(\sigma_{X\cup Y}).$

###### Lemma 3

Let $\sigma_{X\cup Y}$ be an arbitrary imbalance optimal ordering. Let
$\sigma^{\prime}_{X\cup Y}=shift_{R}(\sigma_{X\cup Y})$. We have that
$I(\sigma_{X\cup Y})=I(\sigma^{\prime}_{X\cup Y})$.

###### Proof

Analogous to Lemma 2.

###### Remark 1

Let both $|X|$ and $|Y|$ be odd. Let $\sigma_{X\cup Y}$ be an arbitrary
imbalance optimal ordering. Let $y_{m}\in Y$ be the vertex at position
$l_{\lceil\frac{|Y|}{2}\rceil}$. We have that $I(\sigma_{X\cup Y},y_{m})=1$.
Otherwise $\sigma_{X\cup Y}$ is not imbalance optimal. This can be shown by a
proof by contradiction using Lemma 2 and Lemma 3.

###### Theorem 3.1

If $G=(X,Y,E)$ is a complete bigraph, then the minimum imbalance of $G$ is
$|X|\cdot|Y|+(|X|\mod 2)\cdot(|Y|\mod 2).$

###### Proof

Let $\sigma_{X\cup Y}$ be an arbitrary imbalance optimal ordering. Repeatedly
apply the functions $shift_{L}$ and $shift_{R}$ on $\sigma_{X\cup Y}$, until
we have the same ordering as constructed in Lemma 1. Let us denote the
obtained ordering as $\sigma^{\prime}_{X\cup Y}$. Since $I(\sigma_{X\cup
Y})=I(\sigma^{\prime}_{X\cup Y})$ by Lemma 2 and Lemma 3, and
$I(\sigma^{\prime}_{X\cup Y})=|X|\cdot|Y|+(|X|\mod 2)\cdot(|Y|\mod 2)$, we
have that $I(G)=|X|\cdot|Y|+(|X|\mod 2)\cdot(|Y|\mod 2).$

###### Corollary 1

By Lemma 2, Lemma 3, and Remark 1, any ordering $\sigma_{X\cup Y}$ of a
complete bigraph $G=(X,Y,E)$ is imbalance optimal if and only if
$\sigma_{X\cup Y}$ has the following 3 properties:

  1. 1.

$\Bigg{(}\sum\limits_{i=0}^{\lfloor\frac{|Y|}{2}\rfloor-1}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}\leq\Bigg{(}\sum\limits_{i=\lfloor\frac{|Y|}{2}\rfloor}^{|Y|}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}$

  2. 2.

$\Bigg{(}\sum\limits_{i=0}^{\lceil\frac{|Y|}{2}\rceil}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}\geq\Bigg{(}\sum\limits_{i=\lceil\frac{|Y|}{2}\rceil+1}^{|Y|}|L^{\sigma_{X\cup
Y}}_{i}|\Bigg{)}$

  3. 3.

$|X|$ and $|Y|$ are odd $\implies$ $I(\sigma_{X\cup Y},y_{m})=1$, where
$y_{m}\in Y$ is the vertex at position $l_{\lceil\frac{|Y|}{2}\rceil}$.

These properties allow us to verify whether any ordering is imbalance optimal
in $O(|X|+|Y|)$.

###### Corollary 2

Let $G=(X,Y,E)$ be a complete bigraph and let $|X|+|Y|=n$. Given $|X|$ and
$|Y|$, the minimum imbalance $I(G)$ can be computed in
$\mathcal{O}(\log(n)\cdot\log(\log(n)))$ time by using the formula of Theorem
3.1. This follows from the fact that the product of two $k$-bit integers can
be computed in $\mathcal{O}(k\cdot\log(k))$ time[5].

##  4 Imbalance on Chained Complete bipartite graphs

In this section we shall introduce the chained complete bigraph. We show that
the chained complete bigraph is a subclass of PI-bigraphs and how to use the
results of Section 3 to compute its minimum imbalance efficiently.

###### Definition 3

We define $\mathscr{C}$ to be a family of maximal subsets of the vertices of
graph $G=(V,E)$ that induce a complete bigraph on $G$. Additionally, for all
edges $e\in E$ there exists a vertex set $C_{i}\in\mathscr{C}$ such that both
endpoints of $e$ are contained in $C_{i}$. That is,
$\mathscr{C}\subseteq\mathcal{P}(V)$ such that:

$\displaystyle(\forall_{\\{u,v\\}\in
E}~{}\exists_{C_{i}\in\mathscr{C}}~{}\\{u,v\\}\subseteq
C_{i})~{}\wedge(\forall_{C_{i}\in\mathscr{C}}~{}\exists_{j,k\in\mathbb{N}}~{}G[C_{i}]=K_{j,k})~{}\wedge$
$\displaystyle(\forall_{C_{i}\in\mathscr{C}}~{}\forall_{v\in V\setminus
C_{i}}~{}\forall_{j,k\in\mathbb{N}}~{}G[C_{i}\cup\\{v\\}]\neq K_{j,k}),$

where $K_{i,j}$ denotes a complete bigraph. We call $\mathscr{C}$ the maximal
complete bigraph components, abbreviated by MCB-components, of $G$.

###### Definition 4

A graph $G=(X,Y,E)$ is a chained complete bigraph, if $G$ has a MCB-component
family $\mathscr{C}$ such that we can label
$\mathscr{C}=\\{C_{1},\dots,C_{n}\\}$ such that consecutive vertex sets
$C_{i}$ and $C_{i+1}$ share exactly one vertex and non-consecutive vertex sets
$C_{i}$ and $C_{j}$ share no vertices. Formally, $(\forall_{1\leq
i<n}~{}|C_{i}\cap C_{i+1}|=1)\wedge(\forall_{1\leq i<j<n}~{}j-i>1\implies
C_{i}\cap C_{j}=\emptyset).$ We call a vertex that is shared by two
consecutive vertex sets of $\mathscr{C}$ an overlapping vertex.

For any chained complete bigraph $G$, with corresponding MCB-component family
$\mathscr{C}$, we can create a corresponding PI-bigraph interval
representation $I_{G}$. For each $C_{i}\in\mathscr{C}$ we create a staircase-
shaped set of intervals with the overlapping vertices at the top and bottom.

$y_{1}$$y_{2}$$y_{3}$$y_{4}$$y_{5}$$y_{6}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$C_{1}$$C_{2}$$C_{3}$
Figure 5: Example of a chained complete bigraph $G=(X,Y,E)$, where $X$ is
represented by the red vertices $x_{i}$ and $Y$ by the blue vertices $y_{i}$.
The highlighted areas represent the vertex sets of $\mathscr{C}$.

$x_{2}$$y_{2}$$y_{1}$$x_{1}$$y_{3}$$x_{3}$$y_{4}$$x_{5}$$x_{4}$$y_{6}$$y_{5}$$\mathbb{R}$$C_{1}$$C_{2}$$C_{3}$

Figure 6: Interval representation of the chained complete bigraph of Fig. 5.

###### Remark 2

By the definition of chained complete bigraph $G=(X,Y,E)$ we have
$\forall_{v\in X\cup Y}~{}1\leq|\\{C_{i}\in\mathscr{C}~{}|~{}v\in
C_{i}\\}|\leq 2.$

###### Remark 3

By the definition of MCB-components $\mathscr{C}$ of a chained complete
bigraph $\forall_{v\in X\cup
Y}~{}N(v)\subseteq\bigcup\limits_{C_{j}\in\\{C_{i}\in\mathscr{C}~{}|~{}v\in
C_{i}\\}}C_{j}.$

Let $G=(X,Y,E)$ be a chained complete bigraph with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{n}\\}$. Then we have that:

$\displaystyle I(G)$
$\displaystyle=\sum\limits_{i=1}^{n}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{n-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{n-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)},$

where $X_{i}$, $Y_{i}$, $s_{i}$, and the function $g$ are defined below.
First, we introduce additional definitions that are required to understand the
proof.

###### Definition 5

Let $G=(X,Y,E)$ be a chained complete bigraph with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{n}\\}$. We shall use the notation
$G[C_{i}]=(X_{i},Y_{i},E_{i})$ to denote the graph induced on
$C_{i}\in\mathscr{C}.$

###### Definition 6

Let $G$ be a chained complete bigraph with corresponding MCB-component family
$\mathscr{C}=\\{C_{1},\dots,C_{n}\\}$. We label the overlapping vertices of
$\mathscr{C}$ as $s_{i}\in C_{i}\cap C_{i+1},$ where $1\leq i\leq n-1$. By the
definition of chained complete bigraph, the overlapping vertex $s_{i}$ is
unique. We define $S=\\{s_{i}~{}|~{}1\leq i\leq n-1\\}.$

###### Definition 7

We define $g(s_{i},C_{j})$, where $s_{i}\in S$ and $C_{j}\in\mathscr{C}$, to
be the number of neighbors of $s_{i}$ in $C_{j}$. Equivalently,
$g(s_{i},C_{j})$ is the number of vertices in $C_{j}$ that do not belong to
the same part as $s_{i}$. That is, $g(s_{i},C_{j})=|N(s_{i})\cap
C_{j}|=\begin{cases}|X_{j}|&\text{if }s_{i}\in Y\\\ |Y_{j}|&\text{if }s_{i}\in
X\end{cases}.$

$s_{1}$$s_{2}$$y_{1}$$y_{2}$$y_{3}$$y_{5}$$y_{6}$$x_{1}$$x_{3}$$x_{4}$$x_{5}$$C_{1}$$C_{2}$$C_{3}$$G[C_{1}]=(X_{1},Y_{1},E_{1})=(\\{x_{1},s_{1}\\},\\{y_{1},y_{2}\\},X_{1}\times
Y_{1})$$G[C_{2}]=(X_{2},Y_{2},E_{2})=(\\{s_{1},x_{3}\\},\\{y_{3},s_{2}\\},X_{2}\times
Y_{2})$$G[C_{3}]=(X_{3},Y_{3},E_{3})=(\\{x_{4},x_{5}\\},\\{s_{2},y_{5},y_{6}\\},X_{3}\times
Y_{3})$$g(s_{1},C_{1})=|Y_{1}|=2$$g(s_{1},C_{2})=|Y_{2}|=2$$g(s_{2},C_{2})=|X_{2}|=2$$g(s_{2},C_{3})=|X_{3}|=2$

Figure 7: Illustration of the additional definitions of Section 4 on the
example graph of Fig. 5.

###  4.1 Proof of the upper bound

###### Lemma 4

Let $G=(X,Y,E)$ be a chained complete bigraph with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{n}\\}$. Let $C_{i}\in\mathscr{C}$ such
that $|X_{i}|=1$ or $|Y_{i}|=1$. W.l.o.g. assume that $|X_{i}|=1$, then
neither overlapping vertices $s_{i-1}$ nor $s_{i}$ can be in $X_{i}$.
Formally, $\forall_{C_{i}\in\mathscr{C}}(|X_{i}|=1\implies s_{i-1}\notin
X_{i}\wedge s_{i}\notin X_{i})~{}\wedge(|Y_{i}|=1\implies s_{i-1}\notin
Y_{i}\wedge s_{i}\notin Y_{i}).$

###### Proof

Trivial proof by contradiction. (If not, then $C_{i}$ is not maximal.)

###### Lemma 5

Given a chained complete bigraph $G=(X,Y,E)$ with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{n}\\}$, we have that

$\displaystyle I(G)$
$\displaystyle\leq\sum\limits_{i=1}^{n}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{n-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{n-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)}.$

###### Proof

The lemma is proven by constructing an ordering $\sigma_{X\cup Y}$ whose
imbalance is equivalent to the above expression. The ordering $\sigma_{X\cup
Y}$ is constructed by creating a subordering for each $C_{i}\in\mathscr{C}$
separately and concatenating those suborderings. The suborderings are created
in a similar fashion as the orderings in the proof of Lemma 1.

###  4.2 Proof of the lower bound

###### Remark 4

The imbalance of $v\in(X\cup Y)\setminus S$ is only influenced by the vertices
in $C_{i}$. That is, $\forall_{C_{i}\in\mathscr{C}}~{}\forall_{v\in
C_{i}\setminus S}~{}I(v,\sigma_{X\cup Y},G)=I(v,\sigma_{X\cup
Y}^{C_{i}},G[C_{i}]).$

###### Remark 5

The imbalance of $s_{i}$ is only influenced by the vertices in $C_{i}\cup
C_{i+1}$. That is, $\forall_{s_{i}\in S}~{}I(s_{i},\sigma_{X\cup
Y},G)=I(s_{i},\sigma_{X\cup Y}^{C_{i}\cup C_{i+1}},G[C_{i}\cup C_{i+1}]).$

###### Lemma 6

Let $G=(X,Y,E)$ be a chained complete bigraph with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{n}\\}$. For any arbitrary ordering
$\sigma_{X\cup Y}$ it holds that

$\displaystyle I(s_{n-1},\sigma_{X\cup Y}^{C_{n-1}\cup C_{n}},G[C_{n-1}\cup
C_{n}])-I(s_{n-1},\sigma_{X\cup Y}^{C_{n-1}},G[C_{n-1}])$
$\displaystyle-I(s_{n-1},\sigma_{X\cup Y}^{C_{n}},G[C_{n}])$
$\displaystyle\geq|g(s_{n-1},C_{n-1})-g(s_{n-1},C_{n})|-g(s_{n-1},C_{n-1})-g(s_{n-1},C_{n}).$

###### Proof

The expression
$|g(s_{n-1},C_{n-1})-g(s_{n-1},C_{n})|-g(s_{n-1},C_{n-1})-g(s_{n-1},C_{n})$
takes two possible values depending on the sign of
$g(s_{n-1},C_{n-1})-g(s_{n-1},C_{n})$. Either the above expression is
equivalent to $-2\cdot g(s_{n-1},C_{n})$ or $-2\cdot g(s_{n-1},C_{n-1}).$ To
relate the expressions in the inequality, we shall denote the number of
neighbors of $s_{n-1}$ to its left and to its right in $C_{n}$ and $C_{n-1}$
in ordering $\sigma_{X\cup Y}$ as:

$l_{1}=|\\{v\in C_{n-1}\cap N(s_{n-1})~{}|~{}v<_{\sigma_{X\cup
Y}}s_{n-1}\\}|$;
---
$l_{2}=|\\{v\in C_{n}\cap N(s_{n-1})~{}|~{}v<_{\sigma_{X\cup Y}}s_{n-1}\\}|$;
$r_{1}=|\\{v\in C_{n-1}\cap N(s_{n-1})~{}|~{}v>_{\sigma_{X\cup
Y}}s_{n-1}\\}|$;
$r_{2}=|\\{v\in C_{n}\cap N(s_{n-1})~{}|~{}v>_{\sigma_{X\cup Y}}s_{n-1}\\}|.$

Using the above definitions, we rewrite the expression on the left-hand side
of the inequality as follows:

$\displaystyle I(s_{n-1},\sigma_{X\cup Y}^{C_{n-1}\cup C_{n}},G[C_{n-1}\cup
C_{n}])-I(s_{n-1},\sigma_{X\cup Y}^{C_{n-1}},G[C_{n-1}])$
$\displaystyle-I(s_{n-1},\sigma_{X\cup Y}^{C_{n}},G[C_{n}])$
$\displaystyle=|l_{1}-r_{1}+l_{2}-r_{2}|-|l_{1}-r_{1}|-|l_{2}-r_{2}|.$

According to the signs of $l_{1}-r_{1}$ and $l_{2}-r_{2}$, consider the
following cases:

$(++)$ |  $l_{1}-r_{1}\geq 0$ and $l_{2}-r_{2}\geq 0$; | $(+-)$ |  $l_{1}-r_{1}\geq 0$ and $l_{2}-r_{2}<0$;
---|---|---|---
$(-+)$ |  $l_{1}-r_{1}<0$ and $l_{2}-r_{2}\geq 0$; | $(--)$ |  $l_{1}-r_{1}<0$ and $l_{2}-r_{2}<0$.

For the cases $(++)$ and $(--)$, we have that
$|l_{1}-r_{1}+l_{2}-r_{2}|-|l_{1}-r_{1}|-|l_{2}-r_{2}|=0.$ Thus, in the cases
$(++)$ and $(--)$, it holds that

$\displaystyle|l_{1}-r_{1}+l_{2}-r_{2}|-|l_{1}-r_{1}|-|l_{2}-r_{2}|=0$
$\displaystyle\geq$
$\displaystyle|g(s_{n-1},C_{n-1})-g(s_{n-1},C_{n})|-g(s_{n-1},C_{n-1})-g(s_{n-1},C_{n}).$

This follows from the fact that $-2\cdot g(s_{n-1},C_{n})\leq 0$ and $-2\cdot
g(s_{n-1},C_{n-1})\leq 0.$ For the cases $(+-)$ and $(-+)$, we have that

$|l_{1}-r_{1}+l_{2}-r_{2}|-|l_{1}-r_{1}|-|l_{2}-r_{2}|=\begin{cases}2(l_{2}-r_{2})&\text{if
}(+-)\wedge l_{1}-r_{1}+l_{2}-r_{2}\geq 0\\\ 2(r_{2}-l_{2})&\text{if
}(-+)\wedge l_{1}-r_{1}+l_{2}-r_{2}<0\\\ 2(r_{1}-l_{1})&\text{if }(+-)\wedge
l_{1}-r_{1}+l_{2}-r_{2}<0\\\ 2(l_{1}-r_{1})&\text{if }(-+)\wedge
l_{1}-r_{1}+l_{2}-r_{2}\geq 0\end{cases}.$

Observe that, by the definitions of $l_{1}$, $r_{1}$, $l_{2}$, $r_{2}$, and
function $g$, we have
$l_{1}+r_{1}=g(s_{n-1},C_{n-1})$ and $l_{2}+r_{2}=g(s_{n-1},C_{n}).$ Using the
above remark and case distinction, we derive that in the cases $(+-)$ and
$(-+)$ it holds that

$\displaystyle|l_{1}-r_{1}+l_{2}-r_{2}|-|l_{1}-r_{1}|-|l_{2}-r_{2}|$
$\displaystyle\geq|g(s_{n-1},C_{n-1})-g(s_{n-1},C_{n})|-g(s_{n-1},C_{n-1})-g(s_{n-1},C_{n}).$

###### Lemma 7

Given a chained complete bigraph $G=(X,Y,E)$ with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{n}\\}$, we have that

$\displaystyle I(G)$
$\displaystyle\geq\sum\limits_{i=1}^{n}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{n-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{n-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)}.$

###### Proof

We shall prove that the imbalance of any arbitrary ordering $\sigma_{X\cup Y}$
on the vertex set $X\cup Y$ is bounded from below by the above expression by
induction on $|\mathscr{C}|=n$.

  * $\bullet$

Base Case $(n=0\vee n=1)$:
By the definition of MCB-components $\mathscr{C}$, the graph $G$ is an empty
graph or a complete bigraph. Thus, by Theorem 3.1, the lemma holds for the
base case.

  * $\bullet$

Induction step $(n>1)$:
Let $G=(X,Y,E)$ be a chained complete bigraph with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{k+1}\\}$. Let us define

$\mathscr{C}\setminus
C_{k+1}=\bigcup\limits_{C_{i}\in\mathscr{C}\setminus\\{C_{k+1}\\}}C_{i}.$

We write the imbalance of $\sigma_{X\cup Y}$ as follows:

$\displaystyle I(\sigma_{X\cup Y})$ $\displaystyle=I(\sigma_{X\cup
Y}^{\mathscr{C}\setminus C_{k+1}},G[\mathscr{C}\setminus
C_{k+1}])+I(\sigma_{X\cup Y}^{C_{k+1}},G[C_{k+1}])$
$\displaystyle-I(s_{k},\sigma_{X\cup
Y}^{C_{k}},G[C_{k}])-I(s_{k},\sigma_{X\cup Y}^{C_{k+1}},G[C_{k+1}])$
$\displaystyle+I(s_{k},\sigma_{X\cup Y}^{C_{k}\cup C_{k+1}},G[C_{k}\cup
C_{k+1}])$ (1)
$\displaystyle\geq\Bigg{(}\sum\limits_{i=1}^{k}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)\Bigg{)}$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{k-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{k-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)}$
$\displaystyle+|X_{k+1}|\cdot|Y_{k+1}|+(|X_{k+1}|\mod 2)\cdot(|Y_{k+1}|\mod
2)$ $\displaystyle-I(s_{k},\sigma_{X\cup
Y}^{C_{k}},G[C_{k}])-I(s_{k},\sigma_{X\cup Y}^{C_{k+1}},G[C_{k+1}])$
$\displaystyle+I(s_{k},\sigma_{X\cup Y}^{C_{k}\cup C_{k+1}},G[C_{k}\cup
C_{k+1}])$ (2)
$\displaystyle\geq\Bigg{(}\sum\limits_{i=1}^{k+1}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)\Bigg{)}$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{k-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{k-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)}$
$\displaystyle-g(s_{k},C_{k+1})-g(s_{k},C_{k})+|g(s_{k},C_{k})-g(s_{k},C_{k+1})|$
(3)
$\displaystyle=\Bigg{(}\sum\limits_{i=1}^{k+1}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)\Bigg{)}$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{k}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{k}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)},$

where Eq. 1 follows from Remark 4 and Remark 5, Eq. 2 follows from the
induction hypothesis, and Eq. 3 follows from Lemma 6.

###### Theorem 4.1

Let $G=(X,Y,E)$ be a chained complete bigraph with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{n}\\}$. We have that

$\displaystyle I(G)$
$\displaystyle=\sum\limits_{i=1}^{n}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{n-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{n-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)}.$

###### Proof

Follows from Lemma 5 and Lemma 7.

###### Corollary 3

Let $G=(X,Y,E)$ be a chained complete bigraph with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{n}\\}$ and let $|X|+|Y|=m$. Given
$\\{|X_{1}|,\dots,|X_{n}|\\}$, $\\{|Y_{1}|,\dots,|Y_{n}|\\}$, and $\\{s_{1}\in
X,\dots,s_{n-1}\in X\\}$, the imbalance of $G$ can be computed in
$\mathcal{O}(n\cdot\log(m)\cdot\log(\log(m)))$ time. By applying a similar
reasoning as in Corollary 2, we verify the correctness of this corollary.

## References

  * [1] Biedl, T., Chan, T., Ganjali, Y., Hajiaghayi, M.T., Wood, D.R.: Balanced vertex-orderings of graphs. Discrete Applied Mathematics 148(1), 27 – 48 (2005). https://doi.org/https://doi.org/10.1016/j.dam.2004.12.001, http://www.sciencedirect.com/science/article/pii/S0166218X04003828
  * [2] Díaz, J., Petit, J., Serna, M.: A survey of graph layout problems. ACM Computing Surveys (CSUR) 34(3), 313–356 (2002)
  * [3] Gorzny, J.: Computing imbalance-minimal orderings for bipartite permutation graphs and threshold graphs. In: Wu, W., Zhang, Z. (eds.) Combinatorial Optimization and Applications. pp. 766–779. Springer International Publishing, Cham (2020)
  * [4] Gorzny, J., Buss, J.F.: Imbalance, cutwidth, and the structure of optimal orderings. In: Du, D.Z., Duan, Z., Tian, C. (eds.) Computing and Combinatorics. pp. 219–231. Springer International Publishing, Cham (2019)
  * [5] Harvey, D., van der Hoeven, J.: Integer multiplication in time o(n log n). Annals of Mathematics 193(2), 563–617 (2021), https://www.jstor.org/stable/10.4007/annals.2021.193.2.4
  * [6] Kára, J., Kratochvíl, J., Wood, D.R.: On the complexity of the balanced vertex ordering problem. In: Wang, L. (ed.) Computing and Combinatorics. pp. 849–858. Springer Berlin Heidelberg, Berlin, Heidelberg (2005)
  * [7] Wood, D.: Minimising the number of bends and volume in three-dimensional orthogonal graph drawings with a diagonal vertex layout. Algorithmica (New York) 39 (03 2002). https://doi.org/10.1007/s00453-004-1091-4

##  5 Appendix - Full Proof

###  5.4 Imbalance on Chained Complete bipartite graphs

####  5.4.1 Proof of the upper bound

###### Lemma 8

Let $G=(X,Y,E)$ be a chained complete bigraph with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{n}\\}$. Let $C_{i}\in\mathscr{C}$ such
that $|X_{i}|=1$ or $|Y_{i}|=1$. W.l.o.g. assume that $|X_{i}|=1$, then
neither overlapping vertices $s_{i-1}$ nor $s_{i}$ can be in $X_{i}$.
Formally, for all $C_{i}\in\mathscr{C}$,

$(|X_{i}|=1\implies s_{i-1}\notin X_{i}\wedge s_{i}\notin
X_{i})\wedge(|Y_{i}|=1\implies s_{i-1}\notin Y_{i}\wedge s_{i}\notin Y_{i}).$

###### Proof

Assume that a vertex set $C_{i}\in\mathscr{C}$ exists such that

$\big{(}|X_{i}|=1\wedge(s_{i-1}\in X_{i}\vee s_{i}\in
X_{i})\big{)}\vee\big{(}|Y_{i}|=1\wedge(s_{i-1}\in Y_{i}\vee s_{i}\in
Y_{i})\big{)}.$

W.l.o.g. assume that $|X_{i}|=1\wedge s_{i}\in X_{i}$. Then $G[C_{i}\cup
Y_{i+1}]$ is a complete bigraph. This contradicts the maximality of $C_{i}$.
Thus, there exists no $C_{i}\in\mathscr{C}$ such that

$\displaystyle\big{(}|X_{i}|=1\wedge(s_{i-1}\in X_{i}\vee s_{i}\in
X_{i})\big{)}\vee\big{(}|Y_{i}|=1\wedge(s_{i-1}\in Y_{i}\vee s_{i}\in
Y_{i})\big{)}.$ (1)

###### Lemma 9

Given a chained complete bigraph $G=(X,Y,E)$ with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{n}\\}$, we have that

$\displaystyle I(G)$
$\displaystyle\leq\sum\limits_{i=1}^{n}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{n-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{n-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)}.$

We prove that the minimum imbalance of $G$ is bounded from above by the above
expression, by constructing an ordering $\sigma_{X\cup Y}$ whose imbalance is
equivalent to the above expression.

The ordering $\sigma_{X\cup Y}$ is constructed by creating a subordering for
each $C_{i}\in\mathscr{C}$ separately and concatenating those suborderings.

####  5.4.2 Construction of ordering $\mathbb{\sigma}_{X\cup Y}$

We shall first describe the construction of the subordering corresponding to
the vertex set $C_{i}\in\mathscr{C}$, where $2\leq i\leq n-1$. Afterwards, we
explain the additional steps required to apply the same construction for
vertex sets $C_{1}$ and $C_{n}$. For $C_{i}\in\mathscr{C}$, with $2\leq i\leq
n-1$, we have the following cases based on the signs of the cardinalities of
the parts of $G[C_{i}]$:

###### Case 5

Both $|X_{i}|$ and $|Y_{i}|$ are even.
Consider the following cases based on the set membership of the overlapping
vertices $s_{i-1}$ and $s_{i}$.

  1. 1.

Overlapping vertices $s_{i-1}$ and $s_{i}$ are contained in the same part:
W.l.o.g. assume that $s_{i-1},s_{i}\in X_{i}$. Let us partition
$X_{i}\setminus\\{s_{i-1},s_{i}\\}$ into $X_{1}$ and $X_{2}$ such that
$|X_{1}|=|X_{2}|$. We define $\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}$ as
follows:

$\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}=\sigma_{X_{1}}\sigma_{Y_{i}}\sigma_{X_{2}},$

where $\sigma_{X_{1}}$, $\sigma_{Y_{i}}$, and $\sigma_{X_{2}}$ are arbitrary
orderings on $X_{1}$, $Y_{i}$, and $X_{2}$ respectively.

$\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}=~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$$s_{i-1}$$s_{i}$$X_{1}$$Y_{i}$$X_{2}$

Figure 8: Example of an ordering where $s_{i-1},s_{i}\in X_{i}$ and
$G[C_{i}]=K_{6,6}$.

  2. 2.

Overlapping vertices $s_{i-1}$ and $s_{i}$ are contained in the different
parts:
W.l.o.g. assume that $s_{i-1}\in X_{i}\wedge s_{i}\in Y_{i}$. Let us partition
$X_{i}\setminus\\{s_{i-1}\\}$ into $X_{1}$ and $X_{2}$ such that
$|X_{1}|+1=|X_{2}|$. We also partition $Y_{i}\setminus\\{s_{i}\\}$ into
$Y_{1}$ and $Y_{2}$ such that $|Y_{1}|=|Y_{2}|+1$. We define
$\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}$ as follows:

$\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}=\sigma_{X_{1}}\sigma_{Y_{1}}\sigma_{X_{2}}\sigma_{Y_{2}},$

where $\sigma_{X_{1}}$, $\sigma_{Y_{1}}$, $\sigma_{X_{2}}$, and
$\sigma_{Y_{2}}$ are arbitrary orderings on $X_{1}$, $Y_{1}$, $X_{2}$, and
$Y_{2}$ respectively.

$\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}=~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$$s_{i-1}$$s_{i}$$X_{1}$$Y_{1}$$X_{2}$$Y_{2}$

Figure 9: Example of an ordering where $s_{i-1}\in X_{i}\wedge s_{i}\in Y_{i}$
and $G[C_{i}]=K_{6,6}$.

###### Case 6

Either $|X_{i}|$ is odd or $|Y_{i}|$ is odd.
W.l.o.g. assume that $|X_{i}|$ is odd and $|Y_{i}|$ is even. Consider the
following cases based on the set membership of the overlapping vertices
$s_{i-1}$ and $s_{i}$.

  1. 1.

Overlapping vertices $s_{i-1}$ and $s_{i}$ are contained in $X_{i}$:
Let $x\in X_{i}\setminus\\{s_{i-1},s_{i}\\}$ be chosen arbitrarily. By the
fact that $|X_{i}|$ is odd, such a vertex $x$ must exist. Let us partition
$X_{i}\setminus\\{s_{i-1},s_{i},x\\}$ into $X_{1}$ and $X_{2}$ such that
$|X_{1}|=|X_{2}|$. We also partition $Y_{i}$ into $Y_{1}$ and $Y_{2}$ such
that $|Y_{1}|=|Y_{2}|$. We define $\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}$
as follows:

$\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}=\sigma_{X_{1}}\sigma_{Y_{1}}\sigma_{\\{x\\}}\sigma_{Y_{2}}\sigma_{X_{2}},$

where $\sigma_{X_{1}}$, $\sigma_{Y_{1}}$, $\sigma_{\\{x\\}}$,
$\sigma_{Y_{2}}$, and $\sigma_{X_{2}}$ are arbitrary orderings on $X_{1}$,
$Y_{1}$, $\\{x\\}$, $Y_{2}$, and $X_{2}$ respectively.

$\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}=~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$$s_{i-1}$$s_{i}$$X_{1}$$Y_{1}$$\\{x\\}$$Y_{2}$$X_{2}$

Figure 10: Example of an ordering where $s_{i-1},s_{i}\in X_{i}$ and
$G[C_{i}]=K_{7,6}$.

  2. 2.

Overlapping vertices $s_{i-1}$ and $s_{i}$ are contained in $Y_{i}$:
Let us partition $Y_{i}\setminus\\{s_{i-1},s_{i}\\}$ into $Y_{1}$ and $Y_{2}$
such that $|Y_{1}|=|Y_{2}|$. We define
$\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}$ as follows:

$\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}=\sigma_{Y_{1}}\sigma_{X_{i}}\sigma_{Y_{2}},$

where $\sigma_{Y_{1}}$, $\sigma_{X_{i}}$, and $\sigma_{Y_{2}}$ are arbitrary
orderings on $Y_{1}$, $X_{i}$, and $Y_{2}$ respectively.

$\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}=~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$$s_{i-1}$$s_{i}$$Y_{1}$$X_{i}$$Y_{2}$

Figure 11: Example of an ordering where $s_{i-1},s_{i}\in Y_{i}$ and
$G[C_{i}]=K_{7,6}$.

  3. 3.

Overlapping vertices $s_{i-1}$ and $s_{i}$ are contained in different parts:
W.l.o.g. assume that $s_{i-1}\in X_{i}$ and $s_{i}\in Y_{i}$. Let us partition
$X_{i}\setminus\\{s_{i-1}\\}$ into $X_{1}$ and $X_{2}$ such that
$|X_{1}|+2=|X_{2}|$. We also partition $Y_{i}\setminus\\{s_{i}\\}$ into
$Y_{1}$ and $Y_{2}$ such that $|Y_{1}|=|Y_{2}|+1$. We define
$\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}$ as follows:

$\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}=\sigma_{X_{1}}\sigma_{Y_{1}}\sigma_{X_{2}}\sigma_{Y_{2}},$

where $\sigma_{X_{1}}$, $\sigma_{Y_{1}}$, $\sigma_{X_{2}}$, and
$\sigma_{Y_{2}}$ are arbitrary orderings on $X_{1}$, $Y_{1}$, $X_{2}$, and
$Y_{2}$ respectively.

$\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}=~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$$s_{i-1}$$s_{i}$$X_{1}$$Y_{1}$$X_{2}$$Y_{2}$

Figure 12: Example of an ordering where $s_{i-1}\in X_{i}\wedge s_{i}\in
Y_{i}$ and $G[C_{i}]=K_{7,6}$.

###### Case 7

Both $|X_{i}|$ and $|Y_{i}|$ are odd.
Consider the following cases based on the set membership of the overlapping
vertices $s_{i-1}$ and $s_{i}$.

  1. 1.

Overlapping vertices $s_{i-1}$ and $s_{i}$ are contained in the same part:
W.l.o.g. assume that $s_{i-1},s_{i}\in X_{i}$. Let us choose $x_{m}\in
X_{i}\setminus\\{s_{i-1},s_{i}\\}$ arbitrarily. Let $X_{1}$ and $X_{2}$
partition $X_{i}\setminus\\{s_{i-1},s_{i},x_{m}\\}$ such that
$|X_{1}|=|X_{2}|$. Additionally, let $Y_{1}$ and $Y_{2}$ partition $Y$ such
that $||Y_{1}|-|Y_{2}||=1$. We define
$\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}$ as follows:

$\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}=\sigma_{X_{1}}\sigma_{Y_{1}}\sigma_{\\{x_{m}\\}}\sigma_{Y_{2}}\sigma_{X_{2}},$

where $\sigma_{X_{1}}$, $\sigma_{Y_{1}}$, $\sigma_{Y_{2}}$, and
$\sigma_{X_{2}}$ are arbitrary orderings on $X_{1}$, $Y_{1}$, $Y_{2}$, and
$X_{2}$ respectively.

$\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}=~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$$s_{i-1}$$s_{i}$$X_{1}$$Y_{1}$$\\{x\\}$$Y_{2}$$X_{2}$

Figure 13: Example of an ordering where $s_{i-1},s_{i}\in X_{i}$ and
$G[C_{i}]=K_{7,7}$.

  2. 2.

Overlapping vertices $s_{i-1}$ and $s_{i}$ are contained in the different
parts:
W.l.o.g. assume that $s_{i-1}\in X_{i}\wedge s_{i}\in Y_{i}$. Let us partition
$X_{i}\setminus\\{s_{i-1}\\}$ into $X_{1}$ and $X_{2}$ such that
$|X_{1}|=|X_{2}|$. We also partition $Y_{i}\setminus\\{s_{i}\\}$ into $Y_{1}$
and $Y_{2}$ such that $|Y_{1}|=|Y_{2}|$. We define
$\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}$ as follows:

$\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}=~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}$$s_{i-1}$$s_{i}$$X_{1}$$Y_{1}$$\\{x\\}$$Y_{2}$$X_{2}$

Figure 14: Example of an ordering where $s_{i-1}\in X_{i}\wedge s_{i}\in
Y_{i}$ and $G[C_{i}]=K_{7,7}$.

The vertex set $C_{1}$ contains exactly one overlapping vertex, namely
$s_{1}$. We apply the above described construction to create $\sigma_{C_{1}}$
by arbitrarily picking a vertex in $C_{1}\setminus\\{s_{1}\\}$ to be $s_{0}$.
Similarly, for the vertex set $C_{n}$, we construct $\sigma_{C_{n}}$ by
arbitrarily picking a vertex in $C_{n}\setminus\\{s_{n-1}\\}$ to be $s_{n}$
and applying the above construction.

Note that each constructed subordering
$\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}$
is imbalance optimal for the graph induced by the vertices of $C_{i}$. That
is,
$\forall_{C_{i}\in\mathscr{C}}I(G[C_{i}])=I(G[C_{i}],\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}})$.

Using the above constructed suborderings, we define ordering $\sigma_{X\cup
Y}$ as:

$\displaystyle\sigma_{X\cup Y}=$
$\displaystyle\sigma_{\\{s_{0}\\}}\sigma_{C_{1}\setminus\\{s_{0},s_{1}\\}}\sigma_{\\{s_{1}\\}}\sigma_{C_{2}\setminus\\{s_{1},s_{2}\\}}\sigma_{\\{s_{2}\\}}\dots$
$\displaystyle\sigma_{C_{n-1}\setminus\\{s_{n-2},s_{n-1}\\}}\sigma_{\\{s_{n-1}\\}}\sigma_{C_{n}\setminus\\{s_{n-1},s_{n}\\}}\sigma_{\\{s_{n}\\}}.$

$s_{1}$$s_{2}$$y_{1}$$y_{2}$$y_{3}$$y_{5}$$s_{3}$$s_{0}$$x_{3}$$x_{4}$$x_{5}$$C_{1}$$C_{2}$$C_{3}$
Figure 15: Example of a chained complete bigraph with assigned $s_{0}$, and
$s_{n}$.

$\sigma_{C_{1}}=$$y_{1}$$y_{2}$$\sigma_{C_{2}}=$$y_{3}$$x_{3}$$\sigma_{C_{3}}=$$x_{4}$$y_{5}$$x_{5}$$\sigma_{X\cup
Y}=$$s_{0}$$y_{1}$$y_{2}$$s_{1}$$y_{3}$$x_{3}$$s_{2}$$x_{4}$$y_{5}$$x_{5}$$s_{3}$

Figure 16: Constructed suborderings and final ordering of the example graph
above.

####  5.4.3 Proof of Lemma 9

To prove Lemma 9 we require several remarks on the constructed ordering
$\sigma_{X\cup Y}$.

###### Remark 5

From the definition of chained complete bigraphs, a vertex $v\in(X\cup
Y)\setminus S$ is contained in exactly one vertex set $C_{i}\in\mathscr{C}$.
Additionally, by Remark 3, the neighborhood of $v$ is a subset of $C_{i}$.
Therefore, the imbalance of $v$ is only influenced by the vertices in $C_{i}$.
That is, $\forall_{C_{i}\in\mathscr{C}}~{}\forall_{v\in C_{i}\setminus
S}~{}I(v,\sigma_{X\cup Y},G)=I(v,\sigma_{X\cup Y}^{C_{i}},G[C_{i}]).$

###### Remark 6

From the definition of chained complete bigraphs, an overlapping vertex
$s_{i}\in S$ is contained in exactly two vertex sets
$C_{i},C_{i+1}\in\mathscr{C}$. Additionally, by Remark 3, the neighborhood of
$s_{i}$ is a subset of $C_{i}\cup C_{i+1}$. Therefore, the imbalance of
$s_{i}$ is only influenced by the vertices in $C_{i}\cup C_{i+1}$. That is,
$\forall_{s_{i}\in S}~{}I(s_{i},\sigma_{X\cup Y},G)=I(s_{i},\sigma_{X\cup
Y}^{C_{i}\cup C_{i+1}},G[C_{i}\cup C_{i+1}]).$ From the position of
overlapping vertex $s_{i}$ in ordering
$\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}\sigma_{C_{i+1}\setminus\\{s_{i},s_{i+1}\\}}\sigma_{\\{s_{i+1}\\}}$,
we deduce that the imbalance of $s_{i}$ in ordering

$\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}\sigma_{C_{i+1}\setminus\\{s_{i},s_{i+1}\\}}\sigma_{\\{s_{i+1}\\}}$

is $|g(s_{i},C_{i})-g(s_{i},C_{i+1})|$. That is,

$\displaystyle
I(s_{i},\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}\sigma_{C_{i+1}\setminus\\{s_{i},s_{i+1}\\}}\sigma_{\\{s_{i+1}\\}},G[C_{i}\cup
C_{i+1}])$ $\displaystyle=|g(s_{i},C_{i})-g(s_{i},C_{i+1})|.$

###### Remark 7

By applying a similar analysis as in Lemma 1 together with Lemma 4, we derive
that for all $C_{i}\in\mathscr{C}$ the ordering
$\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}$
is an imbalance optimal ordering for complete bigraph $G[C_{i}]$. That is, by
Theorem 3.1 and the aforementioned analysis, for all $C_{i}\in\mathscr{C}$ we
have

$I(\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}},G[C_{i}])=|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2).$

###### Remark 8

Since overlapping vertex $s_{i}\in S$ is the rightmost vertex in ordering
$\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}$,
we deduce that the imbalance of $s_{i}$ in ordering
$\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}$
is the cardinality of the part of $G[C_{i}]$ in which $s_{i}$ is not
contained. That is, for all $s_{i}\in S$ we have

$I(s_{i},\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}},G[C_{i}])=g(s_{i},C_{i}).$

Similarly, since overlapping vertex $s_{i}\in S$ is the leftmost vertex in
ordering
$\sigma_{\\{s_{i}\\}}\sigma_{C_{i+1}\setminus\\{s_{i},s_{i+1}\\}}\sigma_{\\{s_{i+1}\\}}$,
we deduce that the imbalance of $s_{i}$ in ordering
$\sigma_{\\{s_{i}\\}}\sigma_{C_{i+1}\setminus\\{s_{i},s_{i+1}\\}}\sigma_{\\{s_{i+1}\\}}$
is the cardinality of the part of $G[C_{i+1}]$ in which $s_{i}$ is not
contained. That is, for all $s_{i}\in S$ we have

$I(s_{i},\sigma_{\\{s_{i}\\}}\sigma_{C_{i+1}\setminus\\{s_{i},s_{i+1}\\}}\sigma_{\\{s_{i+1}\\}},G[C_{i+1}])=g(s_{i},C_{i+1}).$

###### Proof

The imbalance of the ordering $\sigma_{X\cup Y}=:\sigma_{V}$, constructed
using the method of Section 5.4.2, can be written as follows:

$\displaystyle I(\sigma_{V})$ $\displaystyle=\Bigg{(}\sum\limits_{v\in(X\cup
Y)\setminus S}I(v,\sigma_{X\cup Y},G)\Bigg{)}+\Bigg{(}\sum\limits_{v\in
S}I(v,\sigma_{X\cup Y},G)\Bigg{)}$
$\displaystyle=\sum\limits_{i=1}^{n}I(\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}},G[C_{i}])$
$\displaystyle-\sum\limits_{i=1}^{n-1}I(s_{i},\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}},G[C_{i}])$
$\displaystyle-\sum\limits_{i=1}^{n-1}I(s_{i},\sigma_{\\{s_{i}\\}}\sigma_{C_{i+1}\setminus\\{s_{i},s_{i+1}\\}}\sigma_{\\{s_{i+1}\\}},G[C_{i+1}])$
$\displaystyle+\sum\limits_{s_{i}\in
S}I(s_{i},\sigma_{\\{s_{i-1}\\}}\sigma_{C_{i}\setminus\\{s_{i-1},s_{i}\\}}\sigma_{\\{s_{i}\\}}\sigma_{C_{i+1}\setminus\\{s_{i},s_{i+1}\\}}\sigma_{\\{s_{i+1}\\}},G[C_{i}\cup
C_{i+1}])$ (2)
$\displaystyle=\sum\limits_{i=1}^{n}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{n-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{n-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)},$
(3)

where Eq. 2 follows from Remark 5, Remark 6 and the construction method of
Section 5.4.2. Eq. 3 follows from Remark 7 and Remark 8.

Note that in the expression at Eq. 2 the first term twice adds an “incorrect
imbalance” for each vertex in $S$. This “incorrect imbalance” is removed by
the second and third term of the expression.

####  5.4.4 Proof of the lower bound

###### Lemma 7

Given a chained complete bigraph $G=(X,Y,E)$ with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{n}\\}$, we have that

$\displaystyle I(G)$
$\displaystyle\geq\sum\limits_{i=1}^{n}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{n-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{n-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)}.$

###### Proof

We shall prove that the imbalance of any arbitrary ordering $\sigma_{X\cup Y}$
on the vertex set $X\cup Y$ is bounded from below by the above expression by
induction on $|\mathscr{C}|=n$.

  * $\bullet$

Base Case $(n=0)$:
By the definition of MCB-components $\mathscr{C}$, the graph $G$ is an empty
graph. Thus,

$\displaystyle I(G)=0$
$\displaystyle=\sum\limits_{i=1}^{n}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{n-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{n-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)}.$

  * $\bullet$

Base case $(n=1)$:
By the definition of MCB-components $\mathscr{C}$, the graph $G$ is a complete
bigraph. Thus, by Theorem 3.1

$\displaystyle I(G)$ $\displaystyle=|X|\cdot|Y|+(|X|\mod 2)\cdot(|Y|\mod 2)$
$\displaystyle=\sum\limits_{i=1}^{n}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{n-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{n-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)}.$

  * $\bullet$

Induction hypothesis:
For any chained complete bigraph $G=(X,Y,E)$ with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{k}\\}$, where $0\leq k<n$, it holds that

$\displaystyle I(G)$
$\displaystyle\geq\sum\limits_{i=1}^{k}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{k-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{k-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)}.$

  * $\bullet$

Induction step $(n>1)$:
Let $G=(X,Y,E)$ be a chained complete bigraph with corresponding MCB-component
family $\mathscr{C}=\\{C_{1},\dots,C_{k+1}\\}$. Let us define
$\mathscr{C}\setminus C_{k+1}$ as follows:

$\mathscr{C}\setminus
C_{k+1}=\bigcup\limits_{C_{i}\in\mathscr{C}\setminus\\{C_{k+1}\\}}C_{i}.$

$s_{1}$$s_{2}$$y_{1}$$y_{2}$$y_{3}$$y_{5}$$y_{6}$$x_{1}$$x_{3}$$x_{4}$$x_{5}$$\mathscr{C}\setminus
C_{k+1}$$C_{k+1}$ Figure 17: Illustration of the definitions of
$\mathscr{C}\setminus C_{k+1}$ and $C_{k+1}$.

Using the above definition, we write the imbalance of $\sigma_{X\cup Y}$ as
follows:

$\displaystyle I(\sigma_{X\cup Y})$ $\displaystyle=I(\sigma_{X\cup
Y}^{\mathscr{C}\setminus C_{k+1}},G[\mathscr{C}\setminus
C_{k+1}])+I(\sigma_{X\cup Y}^{C_{k+1}},G[C_{k+1}])$
$\displaystyle-I(s_{k},\sigma_{X\cup
Y}^{C_{k}},G[C_{k}])-I(s_{k},\sigma_{X\cup Y}^{C_{k+1}},G[C_{k+1}])$
$\displaystyle+I(s_{k},\sigma_{X\cup Y}^{C_{k}\cup C_{k+1}},G[C_{k}\cup
C_{k+1}])$ (4) $\displaystyle\geq I(G[\mathscr{C}\setminus
C_{k+1}])+I(G[C_{k+1}])-I(s_{k},\sigma_{X\cup Y}^{C_{k}},G[C_{k}])$
$\displaystyle-I(s_{k},\sigma_{X\cup
Y}^{C_{k+1}},G[C_{k+1}])+I(s_{k},\sigma_{X\cup Y}^{C_{k}\cup
C_{k+1}},G[C_{k}\cup C_{k+1}])$
$\displaystyle\geq\Bigg{(}\sum\limits_{i=1}^{k}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)\Bigg{)}$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{k-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{k-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)}$
$\displaystyle+|X_{k+1}|\cdot|Y_{k+1}|+(|X_{k+1}|\mod 2)\cdot(|Y_{k+1}|\mod
2)$ $\displaystyle-I(s_{k},\sigma_{X\cup
Y}^{C_{k}},G[C_{k}])-I(s_{k},\sigma_{X\cup Y}^{C_{k+1}},G[C_{k+1}])$
$\displaystyle+I(s_{k},\sigma_{X\cup Y}^{C_{k}\cup C_{k+1}},G[C_{k}\cup
C_{k+1}])$ (5)
$\displaystyle=\Bigg{(}\sum\limits_{i=1}^{k+1}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)\Bigg{)}$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{k-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{k-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)}$
$\displaystyle-I(s_{k},\sigma_{X\cup
Y}^{C_{k}},G[C_{k}])-I(s_{k},\sigma_{X\cup Y}^{C_{k+1}},G[C_{k+1}])$
$\displaystyle+I(s_{k},\sigma_{X\cup Y}^{C_{k}\cup C_{k+1}},G[C_{k}\cup
C_{k+1}])$
$\displaystyle\geq\Bigg{(}\sum\limits_{i=1}^{k+1}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)\Bigg{)}$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{k-1}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{k-1}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)}$
$\displaystyle-g(s_{k},C_{k+1})-g(s_{k},C_{k})+|g(s_{k},C_{k})-g(s_{k},C_{k+1})|$
(6)
$\displaystyle=\Bigg{(}\sum\limits_{i=1}^{k+1}|X_{i}|\cdot|Y_{i}|+(|X_{i}|\mod
2)\cdot(|Y_{i}|\mod 2)\Bigg{)}$
$\displaystyle-\Bigg{(}\sum\limits_{i=1}^{k}g(s_{i},C_{i})+g(s_{i},C_{i+1})\Bigg{)}+\Bigg{(}\sum\limits_{i=1}^{k}|g(s_{i},C_{i})-g(s_{i},C_{i+1})|\Bigg{)},$

where Eq. 4 follows from Remark 5 and Remark 6, Eq. 5 follows from the
induction hypothesis, and Eq. 6 follows from Lemma 6.

Similar to the analysis in Section 5.4.3, in the expression at Eq. 4, the
first term twice adds an “incorrect imbalance” of vertex $s_{k}$. The
“incorrect imbalance” is removed by the second and third term of the
expression. The fourth term of the expression adds the correct imbalance of
$s_{k}$.