Imbalance - intermediate presentation

Characterization of the Imbalance Problem on Complete Bipartite Graphs

Steven Ge and Toshiya Itoh

Tokyo Institute of Technology
Department of Mathematical and Computing Science

Content

Preliminary
- Imbalance Problem description
- Practical applications: Graph drawing
Results
- Complete Bipartite Graph
- Chained Complete Bipartite Graph
Future work

Imbalance Problem description [1]

Definitions

Let $G$ be a graph.
Let $\pi$ be a permutation $\pi : V(G) \rightarrow \{1, 2, \dots, n\}$.
For $v \in V(G)$, let $N_<(v, \pi) = \{u ~|~ \{u,v\} \in E(G) \wedge \pi(u) < \pi(v)\}$.
For $v \in V(G)$, let $N_>(v, \pi) = \{u ~|~ \{u,v\} \in E(G) \wedge \pi(u) > \pi(v)\}$.
For $v \in V(G)$, we define imbalance $$I(v, \pi) = ||N_<(v, \pi)| − |N_>(v, \pi)||.$$
For $\pi : V(G) \rightarrow \{1, 2, \dots, n\}$, we define imbalance $$I(\pi) = \sum_{v \in V(G)}I(v, \pi).$$
For graph $G$, we define imbalance $$I(G) = \min_{\pi : V(G) \rightarrow \{1, 2, \dots, n\}}I(\pi).$$

$I(k, \pi) = |4-1| = 3$

$I(\pi) = |0-2|$ $+|0-3|$ $+|1-5|$ $+...+|3-0|=24$

$I(\pi_1) = 36$

Definitions

\[\begin{aligned} \textbf{Instance: } & \text{A graph } G \text{ and a positive integer } m.\\ \textbf{Question: } & \text{Does } G \text{ have imbalance at most } m \text{?}\\ \color{white}{\textbf{Parameter: }} & \color{white}{m, n} \end{aligned}\]

Practical applications: Graph drawing

Minimizing edge bends in 3-D orthogonal graph drawings [7]

Source: "Three-Dimensional (3-D) Integrated Systems" by Vasileios F. Pavlidis

Results - Existing

Imbalance complexity results

Graph Class	Complexity
Split graph	NP-complete [4]
Bipartite graph & $\Delta(G) \leq 6$	NP-complete [1]
Weighted tree	NP-complete [1]
$\Delta(G) \leq 4$	NP-complete [6]⠀
Superfragile graph	P [4]
Threshold graph	P [3]
Proper interval graph	P [4]
Bipartite permutation graph	P [3]

Results - Existing

Imbalance complexity results

Graph Class	Complexity
Split graph	NP-complete [4]
Bipartite graph & $\Delta(G) \leq 6$	NP-complete [1]
Weighted tree	NP-complete [1]
$\Delta(G) \leq 4$	NP-complete [6]⠀
Superfragile graph	P [4]
Threshold graph	P [3]
Proper interval graph	P [4]
Bipartite permutation graph	P [3]

Results - Novel

Imbalance complexity results

Condition/Graph Class	Time Complexity
Bipartite permutation graph	$\mathcal{O}(\|V\| + \|E\|)$ [3]
Complete bipartite graph	$\mathcal{O}(\|V\| + \|E\|)$ [3]
Chained complete bipartite graph	$\mathcal{O}(c \cdot \log(\|V\|) \cdot \log(\log(\|V\|)))$

Results - Novel

Imbalance complexity results

Condition/Graph Class	Time Complexity
Bipartite permutation graph	$\mathcal{O}(\|V\| + \|E\|)$ [3]
Complete bipartite graph	$\mathcal{O}(\log(\|V\|) \cdot \log(\log(\|V\|)))$
Chained complete bipartite graph	$\mathcal{O}(c \cdot \log(\|V\|) \cdot \log(\log(\|V\|)))$

where $c = \mathcal{O}( | V | )$.

Results - Complete Bipartite Graph

Theorem 1

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a complete bipartite graph, then

$$I(G) = |{\color{#ff0000}X}| \cdot |{\color{#006cff}Y}| + (|{\color{#ff0000}X}| \mod 2) \cdot (|{\color{#006cff}Y}| \mod 2).$$

Results - Complete Bipartite Graph

Lemma 1

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a complete bipartite graph, then there exists an ordering $\sigma$ such that $$I(\sigma) = |{\color{#ff0000}X}| \cdot |{\color{#006cff}Y}| + (|{\color{#ff0000}X}| \mod 2) \cdot (|{\color{#006cff}Y}| \mod 2).$$

Proof

Case: $|{\color{#ff0000}X}|$ even or $|{\color{#006cff}Y}|$ even

$\sigma_{sw} =$

$\underbrace{~~~~~~~~~~~~~~~}_{I(v) = |{\color{#006cff}Y}|}$ $\underbrace{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}_{I(v) = 0}$ $\underbrace{~~~~~~~~~~~~~~~}_{I(v) = |{\color{#006cff}Y}|}$

$I(\sigma_{sw}) = |{\color{#ff0000}X}| \cdot |{\color{#006cff}Y}|$

Lemma 1

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a complete bipartite graph, then there exists an ordering $\sigma$ such that

$$I(\sigma) = |{\color{#ff0000}X}| \cdot |{\color{#006cff}Y}| + (|{\color{#ff0000}X}| \mod 2) \cdot (|{\color{#006cff}Y}| \mod 2).$$

$\square$

We call $\sigma_{sw}$ a sandwiched ordering.

Results - Complete Bipartite Graph

Definition 2

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a complete bipartite graph and $\sigma$ be an ordering.

Function $shift_L(\sigma) = \sigma'$.

Shift vertex ${\color{#006cff}y}_{\left\lfloor \frac{|{\color{#006cff}Y}|}{2} \right\rfloor}$ to the left most position.

Definition 2

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a complete bipartite graph and $\sigma$ be an ordering.

Function $shift_R(\sigma) = \sigma'$.

Shift vertex ${\color{#006cff}y}_{\left\lceil \frac{|{\color{#006cff}Y} |}{2} \right\rceil + 1}$ to the right most position.

Results - Complete Bipartite Graph

Lemma 2

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a complete bipartite graph ,
$\sigma$ be an imbalance optimal ordering , and
$shift_L(\sigma) = \sigma'$.

$$I(\sigma) = I(\sigma')$$

Lemma 3

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a complete bipartite graph ,
$\sigma$ be an imbalance optimal ordering , and
$shift_R(\sigma) = \sigma'$.

$$I(\sigma) = I(\sigma')$$

Results - Complete Bipartite Graph

Theorem 1

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a complete bipartite graph, then

$$I(G) = |{\color{#ff0000}X}| \cdot |{\color{#006cff}Y}| + (|{\color{#ff0000}X}| \mod 2) \cdot (|{\color{#006cff}Y}| \mod 2).$$

Proof

Follows from Lemma 1 + Lemma 2 + Lemma 3

$\sigma_{sw} =$

Sandwiched ordering is optimal!

$\square$

Results - Complete Bipartite Graph

Corollary 1

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a complete bipartite graph, then using Lemma 1 and Lemma 2, we can determine in $\mathcal{O}(|{\color{#ff0000}X}| + |{\color{#006cff}Y}|)$ time whether any arbitrary ordering is imbalance optimal.

Corollary 2

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a complete bipartite graph, then given $|{\color{#ff0000}X}|$ and $|{\color{#006cff}Y}|$ using Theorem 1 and Harvey D. et. al. [5], we can compute $I(G)$ in $\mathcal{O}(\log(|V|)\cdot \log(\log(|V|)))$ time, where $|V| = |{\color{#ff0000}X}| + |{\color{#006cff}Y}|$.

Results - Chained Complete Bipartite Graph

$\mathscr{C}=\{$ $C_1$$,$ $C_2$$,$ $C_3$ $\}$

Definition 3

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a bipartite graph. Define maximal complete bigraph (MCB) components $\mathscr{C} = \{C_1, \cdots, C_n\} \subseteq \mathcal{P}({\color{#ff0000}X} \cup {\color{#006cff}Y})$ of $G$ such that

Every edge $\{u,v\} \in E$ is contained in some $C_i \in \mathscr{C}$
Every $C_i \in \mathscr{C}$ induces a complete bipartite graph $G[C_i]$
Every $C_i \in \mathscr{C}$ is maximal.

$\mathscr{C}=\{$ $C_1$$,$ $C_2$$,$ $C_3$ $\}$

Definition 5

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a bipartite graph with corresponding MCB-components $\mathscr{C} = \{C_1, \cdots, C_n\}$. Let us write $G[C_i] = ({\color{#ff0000}X}_i, {\color{#006cff}Y}_i, E_i)$.

$\mathscr{C}=\{$ $C_1$$,$ $C_2$$,$ $C_3$ $\}$

$S$ $= \{s_1, s_2\}$ $= \{$ $x$$_2$ $,$ $y$$_5$ $\}$

Definition 4

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a bipartite graph. $G$ is a Chained Complete bipartite graph, if $G$ has a MCB-component $\mathscr{C} = \{C_1, \dots, C_n\}$ such that

$|C_i \cap C_{i+1}| = 1$
$C_i \cap C_j = \emptyset$, if $|i-j|>1$.

Definition 6

Let $G$ be a chained complete bigraph with corresponding MCB-components $\mathscr{C} = \{C_1, \dots, C_n\}$. We define overlapping vertex $s_i = C_i \cap C_{i+1}$ and $S = \{s_i ~|~ 1 \leq i \leq n-1\}$.

$\mathscr{C}=\{$ $C_1$$,$ $C_2$$,$ $C_3$ $\}$

$S$ $= \{s_1, s_2\}$ $= \{$ $x$$_2$ $,$ $y$$_5$ $\}$

Definition 7

Let $G$ be a chained complete bigraph with corresponding MCB-components $\mathscr{C}$ and overlapping set $S$. For $s_i \in S$ and $C_j \in \mathscr{C}$, we define

$g(s_i, C_j)$

$= |N(s_i) \cap C_j|$

$= \begin{cases} |{\color{#ff0000}X}_j| & \text{, if } s_i \in {\color{#006cff}Y}_j \\ |{\color{#006cff}Y}_j| & \text{, if } s_i \in {\color{#ff0000}X}_j \end{cases}$

$g({\color{#ff0000}x}_2, {\color{#ff0000}C_1}) = \|\{{\color{#006cff}y}_1, {\color{#006cff}y}_2\}\| = 2$	$g({\color{#ff0000}x}_2, {\color{#008000}C_2}) = \|\{{\color{#006cff}y}_3, {\color{#006cff}y}_4, {\color{#006cff}y}_5\}\| = 3$
$g({\color{#006cff}y}_5, {\color{#008000}C_2}) = \|\{{\color{#ff0000}x}_2, {\color{#ff0000}x}_3\}\| = 2$	$g({\color{#006cff}y}_5, {\color{#0000ff}C_3}) = \|\{{\color{#ff0000}x}_4\}\| = 1$

Results - Chained Complete Bipartite Graph

Theorem 2

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a Chained Complete Bigraph with corresponding MCB-components $\mathscr{C}$.

$I(G) = \sum\limits_{i=1}^{n}\|{\color{#ff0000}X}_i\| \cdot \|{\color{#006cff}Y}_i\| + (\|{\color{#ff0000}X}_i\| \mod 2) \cdot (\|{\color{#006cff}Y}_i\| \mod 2)$	$~~~~\leftarrow$ Complete bigraph
$~~~~~~~~-\Big( \sum\limits_{i=1}^{n-1}g(s_i,C_i)+g(s_i,C_{i+1})\Big)$	$\left.\begin{aligned} ~\\ ~\\ ~\\ ~\\ ~\\ ~\\ \end{aligned}\right\rbrace\leftarrow$ Overlapping vertex correction
$~~~~~~~~+\Big( \sum\limits_{i=1}^{n-1}\big\|g(s_i,C_i)-g(s_i,C_{i+1})\big\|\Big)$

Lemma 5

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a Chained Complete Bigraph with corresponding MCB-components $\mathscr{C}$.

$I(G) \leq \sum\limits_{i=1}^{n}|{\color{#ff0000}X}_i| \cdot |{\color{#006cff}Y}_i| + (|{\color{#ff0000}X}_i| \mod 2) \cdot (|{\color{#006cff}Y}_i| \mod 2)$

$~~~~~~~~-\Big( \sum\limits_{i=1}^{n-1}g(s_i,C_i)+g(s_i,C_{i+1})\Big)+\Big( \sum\limits_{i=1}^{n-1}\big|g(s_i,C_i)-g(s_i,C_{i+1})\big|\Big)$

Proof

Construct an ordering $\sigma$ such that

$I(\sigma, G)=\sum\limits_{i=1}^{n}|{\color{#ff0000}X}_i| \cdot |{\color{#006cff}Y}_i| + (|{\color{#ff0000}X}_i| \mod 2) \cdot (|{\color{#006cff}Y}_i| \mod 2)$

$~~~~~~~~~~~~-\Big( \sum\limits_{i=1}^{n-1}g(s_i,C_i)+g(s_i,C_{i+1})\Big)+\Big( \sum\limits_{i=1}^{n-1}\big|g(s_i,C_i)-g(s_i,C_{i+1})\big|\Big).$

(Constuction similar to Lemma 1.)

$\square$

Lemma 7

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a Chained Complete Bigraph with corresponding MCB-components $\mathscr{C}$.

$I(G) \geq \sum\limits_{i=1}^{n}|{\color{#ff0000}X}_i| \cdot |{\color{#006cff}Y}_i| + (|{\color{#ff0000}X}_i| \mod 2) \cdot (|{\color{#006cff}Y}_i| \mod 2)$

$~~~~~~~~-\Big( \sum\limits_{i=1}^{n-1}g(s_i,C_i)+g(s_i,C_{i+1})\Big)+\Big( \sum\limits_{i=1}^{n-1}\big|g(s_i,C_i)-g(s_i,C_{i+1})\big|\Big)$

Proof

Induction on $|\mathscr{C}|$.

$\square$

Theorem 2

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a Chained Complete Bigraph with corresponding MCB-components $\mathscr{C}$.

$I(G) = \sum\limits_{i=1}^{n}|{\color{#ff0000}X}_i| \cdot |{\color{#006cff}Y}_i| + (|{\color{#ff0000}X}_i| \mod 2) \cdot (|{\color{#006cff}Y}_i| \mod 2)$

$~~~~~~~~-\Big( \sum\limits_{i=1}^{n-1}g(s_i,C_i)+g(s_i,C_{i+1})\Big)$

$~~~~~~~~+\Big( \sum\limits_{i=1}^{n-1}\big|g(s_i,C_i)-g(s_i,C_{i+1})\big|\Big)$

Proof

Follows from Lemma 5 and Lemma 7.

$\square$

Future work

Verifying Chained Complete Bigraph

Can we determine in quasilinear time whether a graph is a Chained Complete Bigraph?

Multiple overlapping vertices

Do we still have a quasilinear time algorithm, when consecutive MCB-components have more than 1 overlapping vertex?

Bibliography

[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

The end

Thank you for your attention!

Appendix: Results - Complete Bipartite Graph

Lemma 1

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a complete bipartite graph, then there exists an ordering $\sigma$ such that

$$I(\sigma) = |{\color{#ff0000}X}| \cdot |{\color{#006cff}Y}| + (|{\color{#ff0000}X}| \mod 2) \cdot (|{\color{#006cff}Y}| \mod 2).$$

Proof

Case: $|{\color{#ff0000}X}|$ odd and $|{\color{#006cff}Y}|$ odd

$\sigma_{sw} =$

$\underbrace{~~~~~~~~~~~~~~~~~~~~~~~~}_{I(v) = |{\color{#ff0000}X}|}$ $\underbrace{~~~~~~~~}_{\scriptsize I(x_i) = 1}$ $\underbrace{~~~~~~}_{\scriptsize I(y_i) = 1}$ $\underbrace{~~~~~~~~~~~~~~~~}_{I(x_i) = 1}$ $\underbrace{~~~~~~~~~~~~~~~~~~~~~~~~}_{I(v) = |{\color{#ff0000}X}|}$

$I(\sigma_{sw}) =$ $ |{\color{#ff0000}X}| \cdot (|{\color{#006cff}Y}|-1)$ $+ |{\color{#ff0000}X}|$ $+ 1$ $= |{\color{#ff0000}X}| \cdot |{\color{#006cff}Y}| + 1$

Remark 1

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a complete bipartite graph such that $|{\color{#ff0000}X}|$ and $|{\color{#006cff}Y}|$ are odd and $\sigma$ be an imbalance optimal ordering.

$$I(\sigma, {\color{#006cff}y}_{\left\lceil \frac{|{\color{#006cff}Y} |}{2} \right\rceil}) = 1$$

Theorem 1

Let $G = ({\color{#ff0000}X},{\color{#006cff}Y},E)$ be a complete bipartite graph, then

$$I(G) = |{\color{#ff0000}X}| \cdot |{\color{#006cff}Y}| + (|{\color{#ff0000}X}| \mod 2) \cdot (|{\color{#006cff}Y}| \mod 2).$$

Proof

Follows from Lemma 1 + Lemma 2 + Lemma 3 + Remark 1

$\sigma_{sw} =$

Sandwiched ordering is optimal!

$\square$