Improved Approximation of Layout Problems on Random Graphs

Kevin K. H. Cheung¹, Patrick Girardet²

¹School of Mathematics and Statistics, Carleton University, Ottawa, ON, Canada.
²Department of Mathematics, University of California San Diego, La Jolla, CA, USA.

DOI: 10.4236/ojdm.2020.101003                

Abstract

Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs, Discrete Mathematics, 235, 2001, 245-253), we show that several well-known graph layout problems are approximable to within a factor arbitrarily close to 1 of the optimal with high probability for random graphs drawn from an Erdös-Renyi distribution with appropriate sparsity conditions using only elementary probabilistic analysis. Moreover, we show that the same results hold for the analogous problems on directed acyclic graphs.

Keywords

Graph Arrangements, Random Graphs, Approximation Algorithms, Undirected Graphs, Directed Acyclic Graphs

1. Introduction

Many well-known optimization problems on graphs fall into the category of graph layout problems. A layout of a graph on n vertices consists of a bijection between the vertices of the graph and the set $\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ of natural numbers, which can be interpreted as arranging the vertices of the graph in some order on a line. A graph layout problem then consists of optimizing some objective function over the set of possible layouts of a graph. There is an analogous notion of layout and layout problems for directed acyclic graphs, i.e. directed graphs with no directed cycles $\left\{\left(v_1\mathrm{,}{v}_2\right)\mathrm{,}\left(v_2\mathrm{,}{v}_3\right)\mathrm{,}\cdots \mathrm{,}\left(v_n\mathrm{,}{v}_1\right)\right\}$ where $\left(v_i\mathrm{,}{v}_{i+1}\right)$ is a directed edge from the vertex $v_i$ to $v_{i+1}$ with the indices taken modulo n. A layout of a directed acyclic graph is simply a topological sort of it, so that the layout respects edge directions. The particular layout problems we consider in this paper are Minimum Cut Linear Arrangement (also known as Cutwidth), Vertex Separation, Edge Bisection, and Vertex Bisection, along with the analogous problems on directed acyclic graphs. These problems are well known to find applications in VLSI design, job scheduling, parallel computing, graph drawing, etc. We direct the interested reader to a survey [1] on the topic.

Graph layout problems are often computationally difficult to solve exactly. The decision versions of both the undirected and directed vertex separation problems are known to be NP-complete [2]. The same is true for the undirected [3] and directed [4] minimum cut linear arrangement problems, and the vertex bisection [5] and edge bisection (shown in [6] as a special case of minimum cut into bounded sets) problems on undirected graphs. We do not know of a reference which proves the NP-hardness of the vertex and edge bisection problems on directed graphs, though we have no reason to believe that they are not. Due to the practical applications of the problems considered, many researchers have sought to find approximation algorithms for these problems. It is common to analyze the performance of algorithms on random instances as a proxy for their “real” performance, so that one might seek to analyze the approximability of layout problems on random graphs. Diaz et al. [7] showed that for any of the undirected layout problems considered above, if $C>2$, then for large enough random graphs with appropriate sparsity conditions, any solution of the problem has cost within a factor C of the optimal with high probability. Hence, these problems can be trivially approximated to within any factor of $C>2$ for large enough random graphs with high probability.

In this paper, in addition to showing that the constant of approximation can be improved to any $C>1$ with slightly weaker sparsity and convergence results, we show that the same result holds for the directed versions of the problems which were not considered in [7]. Moreover, we only use the Hoeffding inequality for tail bounds of sums of independent and identically distributed (i.i.d) random variables and some well-known asymptotic estimates to obtain these results, thus avoiding the more technical “mixing graph” framework used in [7]. In summary, for large enough random graphs with appropriate sparsity conditions, any solution of these layout problems will have cost arbitrarily close to optimal with high probability.

2. Definitions

We first recall some terminology in [7]. Given an undirected graph $G=\left(V,E\right)$ with $\left|V\right|=n$, a linear arrangement (or a layout) of G is an bijective function $\varphi \mathrm{<mo>\; :\; </mo>}V\to \left\{\mathrm{1,}\cdots \mathrm{,}n\right\}$. The problems we consider all take the form of optimizing some objective function over the set of linear arrangements of a graph. For a linear arrangement $\varphi$ of G and each $i\in \left\{\mathrm{1,}\cdots \mathrm{,}n\right\}$, the two sets

$L\left(i\mathrm{,}\varphi \mathrm{,}G\right)=\left\{u\in V|\varphi \left(u\right)\le i\right\}$

$R\left(i,\varphi ,G\right)=\left\{u\in V|\varphi \left(u\right)>i\right\}$

and the two objective functions

$\theta \left(i,\varphi ,G\right)=\left|\left\{uv\in E|u\in L\left(i,\varphi ,G\right)\wedge v\in R\left(i,\varphi ,G\right)\right\}\right|,$

$\delta \left(i,\varphi ,G\right)=\left|\left\{u\in L\left(i,\varphi ,G\right)|\exists v\in R\left(i,\varphi ,G\right)\wedge uv\in E\right\}\right|.$

are defined. We may interpret $\theta \left(i,\varphi ,G\right)$ as the number of edges lying over the i-th “gap” in the arrangement, i.e. edges whose left vertex is in at most the i-th position in the arrangement and whose right vertex is in at least the $\left(i+1\right)$ -th position. Additionally, we may interpret $\delta \left(i,\varphi ,G\right)$ as the number of vertex to the left of the i-th “gap” which are connected by an edge to some vertex to the right of the gap. (In this paper, we sometimes casually refer to $L\left(i,\varphi ,G\right)$ as the set on the left and $R\left(i,\varphi ,G\right)$ as the set on the right.)

Let ${\Lambda }_G$ denote the set of linear arrangements of G. The problems we consider for undirected graphs are given in Table 1. These problems are all known to be NP-hard.

We also consider analogous problems on directed graphs. Given a directed acyclic graph $G=\left(V\mathrm{,}E\right)$ with $\left|V\right|=n$, a linear arrangement (or layout) of G is an bijective function $\varphi \mathrm{<mo>\; :\; </mo>}V\to \left\{\mathrm{1,}\cdots \mathrm{,}n\right\}$ such that if $\left(u\mathrm{,}v\right)\in E$ is a directed edge from $u\in V$ to $v\in V$ then $\varphi \left(u\right)<\varphi \left(v\right)$. Note that this is simply a topological sort of G, which exists as G is directed acyclic. Again, we let ${\Lambda }_G$ denote the set of linear arrangements of G. The definitions of $L\left(i,\varphi ,G\right)$, $R\left(i,\varphi ,G\right)$, $\theta \left(i,\varphi ,G\right)$, and $\delta \left(i,\varphi ,G\right)$ remain unchanged for directed acyclic graphs. The following problems are directed versions of the problems listed in Table 1.

• Directed cutwidth (DCUTWIDTH): Given a directed acyclic graph $G=\left(V\mathrm{,}E\right)$, compute

$\text{MINDCW}\left(G\right)=\underset{\varphi \in {\Lambda }_G}{\min }\text{DCW}\left(G\mathrm{,}\varphi \right)\mathrm{,}$

where $\text{DCW}\left(G\mathrm{,}\varphi \right)=\underset{i\in \left\{1,\cdots ,n\right\}}{\max }\theta \left(i\mathrm{,}\varphi \mathrm{,}G\right)$.

Table 1. Undirected layout problems.

• Directed vertex separation (DVERTSEP): Given a directed acyclic graph $G=\left(V\mathrm{,}E\right)$, compute

$\text{MINDVS}\left(G\right)=\underset{\varphi \in {\Lambda }_G}{\min }\text{DVS}\left(G\mathrm{,}\varphi \right)\mathrm{,}$

where $\text{DVS}\left(G\mathrm{,}\varphi \right)=\underset{i\in \left\{1,\cdots ,n\right\}}{\max }\delta \left(i,\varphi ,G\right)$.

• Directed edge bisection (DEDGEBIS): Given a directed acyclic graph $G=\left(V\mathrm{,}E\right)$, compute

$\text{MINDEB}\left(G\right)=\underset{\varphi \in {\Lambda }_G}{\min }\text{DEB}\left(G\mathrm{,}\varphi \right),$

where $\text{DEB}\left(G\mathrm{,}\varphi \right)=\theta \left(\lfloor \frac{n}{2}\rfloor \mathrm{,}\varphi \mathrm{,}G\right)$.

• Directed vertex bisection (DVERTBIS): Given a directed acyclic graph $G=\left(V\mathrm{,}E\right)$, compute

$\text{MINDVB}\left(G\right)=\underset{\varphi \in {\Lambda }_G}{\min }\text{DVB}\left(G\mathrm{,}\varphi \right)\mathrm{,}$

where $\text{DVB}\left(G\mathrm{,}\varphi \right)=\delta \left(\lfloor \frac{n}{2}\rfloor \mathrm{,}\varphi \mathrm{,}G\right)$.

For each arrangement problem considered above, we also define the maximum-cost solution of the problem on a graph. For example, for CUTWIDTH, in contrast to $\text{MINCW}\left(G\right)$, we define $\text{MAXCW}\left(G\right)={\max }_{\varphi }\text{CW}\left(G\mathrm{,}\varphi \right)$, and similarly for every other problem considered above. Moreover, we define the gap of a problem on a given graph G to be the ratio of the maximum-cost solution to the minimum-cost solution. For example, for CUTWIDTH, the gap is

$\text{GAPCW}\left(G\right)=\frac{\text{MAXCW}\left(G\right)}{\text{MINCW}\left(G\right)}\mathrm{,}$

and this quantity is defined in the same way for every other arrangement problem considered above.

Any discussion on random graphs requires a probability distribution on graphs. In this paper, we adopt a variant of the Erdös-Renyi probability distribution [8] for undirected graphs defined as follows:

For a positive integer n and probability $0\le p\le 1$, the Erdös-Renyi distribution $G\left(n\mathrm{,}p\right)$ on the set of n-vertex graphs assigns an n-vertex graph

$G=\left(V\mathrm{,}E\right)$ probability $p^m{\left(1-p\right)}^{\left(\begin{array}{c}n\\ 2\end{array}\right)-m}$, where $\left|E\right|=m$. That is, we sample n-vertex graphs by including each possible edge with probability p.

For a probability distribution on directed acyclic graphs, we use a variant of the Erdös-Renyi probability distribution [9] which produces directed acyclic graphs, defined as follows:

For a positive integer n and probability $0\le p\le 1$, the distribution $D\left(n\mathrm{,}p\right)$ on the set of n-vertex directed acyclic graphs first samples a random graph from $G\left(n\mathrm{,}p\right)$ on the vertex set $\left\{\mathrm{1,}\cdots \mathrm{,}n\right\}$ and orients each edge $\left\{i\mathrm{,}j\right\}$ from i to j if $i<j$.

As the edges in the sampled directed graph always point from a lower numbered vertex to a higher numbered vertex, it is clear that the sampled graph is acyclic.

3. Preliminary Lemmas

We first list some technical lemmas necessary for carrying out the probabilistic analysis in our main theorems.

Lemma 1 (Hoeffding’s inequality). Suppose that $X_1\mathrm{,}\cdots \mathrm{,}{X}_n$ are independent identically distributed Bernoulli random variables with mean p, and let $H\left(n\right)=\overline{X_1}+\overline{X_2}+\cdots +\overline{X_n}$, where $\overline{X_i}$ is a sample of $X_i$. Then for $\gamma >0$,

$P\left[H\left(n\right)\le \left(p-\gamma \right)n\right]\le \exp \left(-2{\gamma }^{2}n\right)$

$P\left[H\left(n\right)\ge \left(p+\gamma \right)n\right]\le \exp \left(-2{\gamma }^{2}n\right)\mathrm{.}$

Proof. This is a special case of Theorem 1 in Hoeffding’s original paper [10] for Bernoulli random variables.

Lemma 2. If $k=o\left(n\right)$, then

$\log \left(\begin{array}{c}n\\ k\end{array}\right)=\left(1+o\left(1\right)\right)k\log \frac{n}{k}$

Proof. Recall the well-known inequalities

${\left(\frac{n}{k}\right)}^k\le \left(\begin{array}{c}n\\ k\end{array}\right)\le {\left(\frac{ne}{k}\right)}^k\mathrm{,}$

which can be obtained via Stirling’s approximation. It follows that

$k\log \frac{n}{k}\le \log \left(\begin{array}{c}n\\ k\end{array}\right)\le k\left(\log \frac{n}{k}+1\right)\mathrm{.}$

If $k=o\left(n\right)$, then $\log \frac{n}{k}\to \infty$. By the above chain of inequalities, we have that

$\log \left(\begin{array}{c}n\\ k\end{array}\right)=\left(1+o\left(1\right)\right)k\log \frac{n}{k}\mathrm{,}$

as desired.

Lemma 3. Suppose that $f\left(n\right)=\Omega \left(n^{-c}\right)$ and $g\left(n\right)=O\left(n^d\right)$ where $0<c<d$. If $f\left(n\right)=o\left(1\right)$, then

$\underset{n\to \infty }{\lim }{\left(1-f\left(n\right)\right)}^{g\left(n\right)}=0.$

Proof. Taking logarithms, we find that

$\log \left(\underset{n\to \infty }{\lim }{\left(1-f\left(n\right)\right)}^{g\left(n\right)}\right)=\underset{n\to \infty }{\lim }g\left(n\right)\log \left(1-f\left(n\right)\right)\le \underset{n\to \infty }{\lim }{k}_1{n}^d\log \left(1-k_2{n}^{-c}\right)$

for appropriate constants $k_1,k_2>0$. But then by L’Hopital’s rule,

$\underset{n\to \infty }{\lim }{k}_1{n}^d\log \left(1-k_2{n}^{-c}\right)=\underset{n\to \infty }{\lim }\frac{\log \left(1-k_2{n}^{-c}\right)}{k_1{n}^{-d}}=-\underset{n\to \infty }{\lim }\frac{c{k}_2{n}^{-c-1}}{\left(1-k_2{n}^{-c}\right)d{k}_1{n}^{-d-1}}.$

Since $0<c<d$, we have that

$\frac{c{k}_2{n}^{-c-1}}{\left(1-k_2{n}^{-c}\right)d{k}_1{n}^{-d-1}}=\left(\frac{c{k}_2}{\left(1-k_2{n}^{-c}\right)d{k}_1}\right)n^{d-c}\to \infty$

as $n\to \infty$. It follows that

$\log \left(\underset{n\to \infty }{\lim }{\left(1-f\left(n\right)\right)}^{g\left(n\right)}\right)=-\underset{n\to \infty }{\lim }\frac{c{k}_2{n}^{-c-1}}{\left(1-k_2{n}^{-c}\right)d{k}_1{n}^{-d-1}}=-\infty .$

Hence,

$\underset{n\to \infty }{\lim }{\left(1-f\left(n\right)\right)}^{g\left(n\right)}=0$

as desired.

4. Main Results

4.1. Undirected Graph Problems

For the theorems that follow, let ${\left\{G_n\right\}}_{n=1}^{\infty }$ be a sequence of random graphs such that for each $n=1,2,\cdots$, $G_n$ is given by $G\left(n\mathrm{,}{p}_n\right)$ with edge probability $p_n$. The following theorems show that for each of the undirected graph arrangement problems GAPCW, GAPEP, GAPVS, and GAPVB that the ratio of the maximum value to the minimum value of the corresponding objective function over all arrangements of $G_n$ is asymptotically close to 1 with high probability, subject to appropriate sparsity conditions.

Theorem 1. Let $p_n$ satisfy $p_n=\Omega \left(n^{-c}\right),c<1/2$. Then for all $ϵ>0,\delta >0$ there exists an N such that for all $n\ge N$,

$P\left[\text{GAPCW}\left(G_n\right)<1+\delta \right]>1-ϵ.$

Theorem 2. Let $p_n$ satisfy $p_n=\Omega \left(n^{-c}\right),c<1/2$. Then for all $ϵ>0,\delta >0$ there exists an N such that for all $n\ge N$,

$P\left[\text{GAPEB}\left(G_n\right)<1+\delta \right]>1-ϵ.$

Theorem 3. Let $p_n$ satisfy $p_n=\Omega \left(n^{-c}\right),c<1$. Then for all $ϵ>0,\delta >0$ there exists an N such that for all $n\ge N$,

$P\left[\text{GAPVS}\left(G_n\right)<1+\delta \right]>1-ϵ.$

Theorem 4. Let $p_n$ satisfy $p_n=\Omega \left(n^{-c}\right),c<1$. Then for all $ϵ>0,\delta >0$ there exists an N such that for all $n\ge N$,

$P\left[\text{GAPVB}\left(G_n\right)<1+\delta \right]>1-ϵ.$

To prove Theorem 1, we first establish the following lemmas:

Lemma 4. Let $p_n$ satisfy $p_n=\Omega \left(n^{-c}\right),c<1/2$. Then for all $ϵ>0,\delta >0$ there exists an N such that for all $n\ge N$,

$P\left[\text{MINCW}\left(G_n\right)\ge \frac{n^2{p}_n\left(1-\delta \right)}{4}\right]>1-ϵ\mathrm{.}$

Lemma 5. Suppose that $p_n=\Omega \left(n^{-c}\right),c<1/2$. Then for all $ϵ>0,\delta >0$ there exists an N such that for all $n\ge N$,

$P\left[\text{MAXCW}\left(G_n\right)\le \frac{n^2{p}_n\left(1+\delta \right)}{4}\right]>1-ϵ.$

We will make use of the following definition in our proofs for the above lemmas: For a graph $G=\left(V,E\right)$ and $A\subseteq V$, $c\left(G\mathrm{,}A\right)$ is defined to be the number of edges joining a vertex in A and a vertex in $V-A$. That is,

$c\left(G\mathrm{,}A\right)=\left|\left\{uv\in E|u\in A\wedge v\in V-A\right\}\right|\mathrm{.}$

Proof of Lemma 4. For a linear arrangement $\varphi \in {\Lambda }_G$, define

$L_{\varphi }=L\left(\lfloor n/2\rfloor ,\varphi ,G\right)=\left\{u\in V|\varphi \left(u\right)\le \lfloor n/2\rfloor \right\}.$

Clearly, $\text{CW}\left(G\right)\ge c\left(G\mathrm{,}{L}_{\varphi }\right)$. It follows that $\text{MINCW}\left(G\right)\ge {\min }_{\varphi }c\left(G\mathrm{,}{L}_{\varphi }\right)$. Suppose that $\left|V\right|=n$. Observe that ${\min }_{\varphi }c\left(G\mathrm{,}{L}_{\varphi }\right)={\min }_{S\in \mathcal{B}}c\left(G\mathrm{,}S\right)$ where $\mathcal{B}=\left\{S\subseteq V|\left|S\right|=\lfloor n/2\rfloor \right\}$. Hence, for all $\alpha \ge 0$,

$P\left[\text{MINCW}\left(G_n\right)\ge \alpha \right]\ge P\left[\underset{S\in \mathcal{B}}{\min }c\left(G_n\mathrm{,}S\right)\ge \alpha \right]\mathrm{.}$

To prove the lemma, it suffices to show that

$P\left[\underset{S\in \mathcal{B}}{\min }c\left(G_n\mathrm{,}S\right)\ge \frac{n^2{p}_n\left(1-\delta \right)}{4}\right]>1-ϵ$

for n sufficiently large.

Let S be an arbitrary subset of V with $\left|S\right|=\lfloor n/2\rfloor$. As $G_n$ is an Erdös-Renyi random graph with vertex set V and edge probability $p_n$, $c\left(G_n\mathrm{,}S\right)$ is a binomial random variable with mean $\mu =\lfloor n/2\rfloor \lceil n/2\rceil p_n\ge \frac{\left(n^2-1\right)p_n}{4}$.

Applying the first inequality in Lemma 1 with $\gamma ={\gamma }_n$ where ${\gamma }_n>0$, we obtain that

$P\left[c\left(G_n\mathrm{,}S\right)\le \mu \left(1-\frac{{\gamma }_n}{p_n}\right)\right]\le \exp \left(-\left(n^2-1\right){\gamma }_n^2/2\right)\mathrm{.}$

As $p_n=\Omega \left(n^{-c}\right)$ with $c<1/2$, we can choose ${\gamma }_n$ to get the desired convergence. Indeed, setting ${\gamma }_n=n^{-l}$ where l satisfies $c<l<1/2$, we have ${\gamma }_n=o\left(p_n\right)$ and ${\gamma }_n^2=\Omega \left(n^{-1+s}\right)$ for some $s>0$. Hence,

$\begin{array}{c}P\left[c\left(G_n,S\right)\le \mu \left(1-\frac{{\gamma }_n}{p_n}\right)\right]\le \exp \left(-\left(n^2-1\right){\gamma }_n^2/2\right)\\ =\exp \left(-\left(n^2-1\right)\Omega \left(n^{-1+s}\right)\right)\\ =\exp \left(-\Omega \left(n^{1+s}\right)\right).\end{array}$

Note that $\left(\begin{array}{c}n\\ \lfloor n/2\rfloor \end{array}\right)\le 2^n$. Hence, by the union bound,

$\begin{array}{l}P\left[\underset{S\in \mathcal{B}}{{\displaystyle V}}c\left(G_n,S\right)\le \mu \left(1-\frac{{\gamma }_n}{p_n}\right)\right]\le {\displaystyle \underset{S\in \mathcal{B}}{\sum }}P\left[c\left(G_n,S\right)\le \mu \left(1-\frac{{\gamma }_n}{p_n}\right)\right]\le {\displaystyle \underset{S\in \mathcal{B}}{\sum }}\exp \left(-\Omega \left(n^{1+s}\right)\right)\\ =\left(\begin{array}{c}n\\ \lfloor n/2\rfloor \end{array}\right)\exp \left(-\Omega \left(n^{1+s}\right)\right)\le 2^n\exp \left(-\Omega \left(n^{1+s}\right)\right)<ϵ\end{array}$

for n sufficiently large. Thus,

$P\left[\underset{S\in \mathcal{B}}{\min }c\left(G_n\mathrm{,}S\right)\ge \mu \left(1-\frac{{\gamma }_n}{p_n}\right)\right]\ge 1-P\left[\underset{S\in \mathcal{B}}{{\displaystyle V}}c\left(G_n,S\right)\le \mu \left(1-\frac{{\gamma }_n}{p_n}\right)\right]>1-ϵ$

for n sufficiently large.

Since $\frac{{\gamma }_n}{p_n}=O\left(n^{c-l}\right)=o\left(1\right)$, for a sufficiently large n,

$\mu \left(1-\frac{{\gamma }_n}{p_n}\right)\ge \frac{\left(n^2-1\right)p_n}{4}\left(1-\frac{{\gamma }_n}{p_n}\right)\ge \frac{n^2{p}_n\left(1-\delta \right)}{4}\mathrm{.}$

Hence, for n sufficiently large,

$P\left[\underset{S\in \mathcal{B}}{\min }c\left(G_n\mathrm{,}S\right)\ge \frac{n^2{p}_n\left(1-\delta \right)}{4}\right]>1-ϵ$

as desired.

Proof of 5. Let $ϵ,\delta >0$. Observe that for all $\alpha \ge 0$,

$P\left[\text{MAXCW}\left(G_n\right)\le \alpha \right]=P\left[\underset{\begin{array}{c}S\subseteq V\\ \left|S\right|\le \lfloor n\rfloor /2\end{array}}{\max }c\left(G_n\mathrm{,}S\right)\le \alpha \right]\mathrm{,}$

and that

$P\left[c\left(G_n\mathrm{,}S\right)\le \alpha \right]\ge P\left[c\left(G_n\mathrm{,}T\right)\le \alpha \right]$

for all $S\mathrm{,}T\subseteq V$ such that $\left|S\right|\le \lfloor n/2\rfloor$ and $\left|T\right|=\lfloor n/2\rfloor$. To see the second inequality, note that $c\left(G_n\mathrm{,}S\right)$ is the sum of $\left|S\right|\left(n-\left|S\right|\right)$ i.i.d. Bernoulli random variables with probability of success $p_n$ and $\left|S\right|\left(n-\left|S\right|\right)$ is maximized at $\left|S\right|=\lfloor n/2\rfloor$. Hence, to prove the lemma, it suffices to show that

$P\left[\underset{\begin{array}{c}T\subseteq V\\ \left|T\right|=\lfloor n\rfloor /2\end{array}}{\max }c\left(G_n\mathrm{,}T\right)\le \frac{n^2{p}_n\left(1+\delta \right)}{4}\right]>1-ϵ$

for n sufficiently large.

Let $\mathcal{B}$ denote the set $\left\{S\subseteq V|\left|S\right|=\lfloor n/2\rfloor \right\}$. Let $T\in \mathcal{B}$. Then, by the second inequality in Lemma 1 with $\gamma ={\gamma }_n$ where ${\gamma }_n>0$, we obtain that

$P\left[c\left(G_n\mathrm{,}T\right)\ge \mu \left(1+\frac{{\gamma }_n}{p_n}\right)\right]\le \exp \left(-\left(n^2-1\right){\gamma }_n^2/2\right)$

where $\mu =\lfloor n/2\rfloor \lceil n/2\rceil p_n$ as in the proof of Lemma 4.

As $p_n=\Omega \left(n^{-c}\right)$ with $c>1/2$, we again set ${\gamma }_n=n^{-l}$ where l satisfies $c<l<1/2$, so that ${\gamma }_n=o\left(p_n\right)$ and ${\gamma }_n^2=\Omega \left(n^{-1+s}\right)$ for some $s>0$. Then,

$P\left[c\left(G_n\mathrm{,}T\right)\ge \mu \left(1+\frac{{\gamma }_n}{p_n}\right)\right]\le \exp \left(-\Omega \left(n^{1+s}\right)\right)\mathrm{.}$

Hence,

${\displaystyle \underset{T\in \mathcal{B}}{\sum }}P\left[c\left(G_n\mathrm{,}T\right)\ge \mu \left(1+\frac{{\gamma }_n}{p_n}\right)\right]\le 2^n\exp \left(-\Omega \left(n^{1+s}\right)\right)<ϵ$

for a sufficiently large n.

As $\frac{{\gamma }_n}{p_n}=O\left(n^{c-l}\right)$, we have that

$\frac{n^2{p}_n\left(1+\frac{{\gamma }_n}{p_n}\right)}{4}\le \frac{n^2{p}_n\left(1+\delta \right)}{4}\mathrm{,}$

for a sufficiently large n. Thus, for n sufficiently large,

$\begin{array}{l}P\left[\underset{T\in \mathcal{B}}{\max }c\left(G_n\mathrm{,}T\right)\le \frac{n^2{p}_n\left(1+\delta \right)}{4}\right]\\ \ge 1-{\displaystyle \underset{T\in \mathcal{B}}{\sum }}P\left[c\left(G_n\mathrm{,}T\right)\ge \frac{n^2{p}_n\left(1+\frac{{\gamma }_n}{p_n}\right)}{4}\right]>1-ϵ\end{array}$

as desired.

With these two lemmas, the main theorem for the cut width gap can be readily established.

Proof of Theorem 1. As in the statement of the theorem, let $p_n$ satisfy $p_n=\Omega \left(n^{-c}\right)$ for some $c<1/2$, and let $\delta \mathrm{,}ϵ>0$ be given. Since

$\underset{x\to 0}{\lim }\frac{1+x}{1-x}=1,$

there exists ${\delta }^{\prime }$ satisfying $\frac{1+{\delta }^{\prime }}{1-{\delta }^{\prime }}<1+\delta$. By Lemma 4, there exists $N_1$ such that for $n\ge N_1$,

$P\left[\text{MINCW}\left(G_n\right)\ge \frac{n^2{p}_n\left(1-{\delta }^{\prime }\right)}{4}\right]>1-ϵ/2\mathrm{.}$

By Lemma 5, there exists $N_2$ such that for $n\ge N_2$,

$P\left[\text{MAXCW}\left(G_n\right)\le \frac{n^2{p}_n\left(1+{\delta }^{\prime }\right)}{4}\right]>1-ϵ/2\mathrm{.}$

Hence, if $N=\max \left\{N_1\mathrm{,}{N}_2\right\}$, then for $n\ge N$ we have that

$\begin{array}{l}1-ϵ=1-2\left(ϵ/2\right)\\ \le P\left[\left(\text{MINCW}\left(G_n\right)\ge \frac{n^2{p}_n\left(1-{\delta }^{\prime }\right)}{4}\right)\wedge \left(\text{MAXCW}\left(G_n\right)\le \frac{n^2{p}_n\left(1+{\delta }^{\prime }\right)}{4}\right)\right]\mathrm{.}\end{array}$

As $\left(a\ge b>0\right)\wedge \left(0<c\le d\right)\Rightarrow \frac{c}{a}\ge \frac{d}{b}$, it follows that

$P\left[\frac{\text{MAXCW}\left(G_n\right)}{\text{MINCW}\left(G_n\right)}\le \frac{1+{\delta }^{\prime }}{1-{\delta }^{\prime }}\right]>1-ϵ\mathrm{.}$

Thus, $P\left[\text{GAPCW}\left(G_n\right)<1+\delta \right]>1-ϵ$ as desired.

Since edge bisection is essentially a restricted version of the cutwidth problem, it is straightforward to carry over the proofs above to prove Theorem 2.

Proof of Theorem 2. Note that for a graph G, $\text{MINEB}\left(G\right)$ is simply the minimization of $c\left(G\mathrm{,}S\right)$ over subsets $S\subset V$ with $\left|S\right|=\lfloor n/2\rfloor$, and $\text{MAXEB}\left(G\right)$ the corresponding maximization. Hence, the proof of Lemma 4 carries through to give that

$P\left[\text{MINEB}\left(G_n\right)\ge \frac{n^2{p}_n\left(1-\delta \right)}{4}\right]>1-ϵ$

for any given $ϵ\mathrm{,}\delta >0$ when n is sufficiently large.

Similarly, the proof of Lemma 5 carries through to yield that

$P\left[\text{MAXEB}\left(G_n\right)\le \frac{n^2{p}_n\left(1+\delta \right)}{4}\right]>1-ϵ$

for any given $ϵ\mathrm{,}\delta >0$ when n is sufficiently large. Combining these two results in the same manner as in the proof of Theorem 1 gives the desired result.

The following lemma essentially proves Theorem 3.

Lemma 6. Let $p_n$ satisfy $p_n=\Omega \left(n^{-c}\right),c<1$. Then for all $ϵ>0,\delta >0$ there exists an N such that for all $n\ge N$,

$P\left[\text{MINVS}\left(G_n\right)\ge \left(1-\delta \right)n-1\right]>1-ϵ\mathrm{.}$

We will make use of the following definition in our proof for the above lemma. For a graph $G=\left(V,E\right)$ and $A\subseteq V$, $v\left(G\mathrm{,}A\right)$ is defined to be the number of vertices in A which are connected to a vertex in $V-A$. That is,

$v\left(G\mathrm{,}A\right)=\left|\left\{u\in A|\exists v\in V-A\wedge uv\in E\right\}\right|\mathrm{.}$

Proof of Lemma 6. So as to obtain the desired convergence, for each positive integer n, set

${\delta }_n=n^{-l},{ϵ}_n=n^{-s},$

where $0<s<1-c,0<l<\frac{s}{2}$. Consider a linear arrangement $\varphi \in {\Lambda }_{G_n}$. Note that for any k, $\text{VS}\left(G_n\right)\ge v\left(G_n\mathrm{,}L\left(k\mathrm{,}\varphi \mathrm{,}{G}_n\right)\right)$. In particular, if we define

$S_{\varphi ,{\epsilon }_n}=L\left(\lfloor \left(1-{\epsilon }_n\right)n\rfloor ,\varphi ,G_n\right),$

then $\text{VS}\left(G_n\right)\ge v\left(G_n,S_{\varphi ,{ϵ}_n}\right)$. It follows then that $\text{MINVS}\left(G_n\right)\ge {\min }_{\varphi }v\left(G_n\mathrm{,}{S}_{\varphi \mathrm{,}{ϵ}_n}\right)$. Observe that

${\min }_{\varphi }v\left(G_n\mathrm{,}{S}_{\varphi \mathrm{,}{ϵ}_n}\right)={\min }_{S\in \mathcal{B}}v\left(G_n\mathrm{,}S\right)$

where $\mathcal{B}=\left\{S\subseteq V|\left|S\right|=\lfloor \left(1-{ϵ}_n\right)n\rfloor \right\}$. Hence, for all $\alpha \ge 0$,

$P\left[\text{MINVS}\left(G_n\right)\ge \alpha \right]\ge P\left[\underset{S\in \mathcal{B}}{\min }v\left(G_n\mathrm{,}S\right)\ge \alpha \right]\mathrm{.}$

To prove the lemma, it suffices to show that for any $\delta \mathrm{,}ϵ>0$,

$P\left[\underset{S\in \mathcal{B}}{\min }v\left(G_n\mathrm{,}S\right)\ge \left(1-\delta \right)n-1\right]>1-ϵ$

for n sufficiently large.

Let S be an arbitrary element of $\mathcal{B}$. As there are $\lceil {ϵ}_{n}n\rceil$ vertices in $V-S$, the probability of a given vertex $v\in S$ not being connected to any vertex in $V-S$ is ${\left(1-p_n\right)}^{\lceil {ϵ}_{n}n\rceil }$. Hence, $v\left(G_n\mathrm{,}S\right)$ is a binomial random variable on $m=\lfloor \left(1-{ϵ}_n\right)n\rfloor$ trials with event probability $q=1-{\left(1-p_n\right)}^{\lceil {ϵ}_{n}n\rceil }$. By Lemma 1, we have that

$P\left[v\left(G_n\mathrm{,}S\right)\le \left(q-{\delta }_n\right)m\right]\le \exp \left(-2{\delta }_n^{2}m\right)\mathrm{.}$

As $\left|\mathcal{B}\right|=\left(\begin{array}{c}n\\ \lceil {ϵ}_{n}n\rceil \end{array}\right)$,

$\begin{array}{l}P\left[\underset{S\in \mathcal{B}}{{\displaystyle V}}v\left(G_n,S\right)\le \left(q-{\delta }_n\right)m\right]\le {\displaystyle \underset{S\in \mathcal{B}}{\sum }}P\left[v\left(G_n,S\right)\le \left(q-{\delta }_n\right)m\right]\\ =\left(\begin{array}{c}n\\ \lceil {ϵ}_{n}n\rceil \end{array}\right)P\left[v\left(G_n,S\right)\le \left(q-{\delta }_n\right)m\right]\\ \le \left(\begin{array}{c}n\\ \lceil {ϵ}_{n}n\rceil \end{array}\right)\exp \left(-2{\delta }_n^{2}m\right).\end{array}$

The first and third lines of the above computation follow respectively from the union bound and the preceding inequality. The second line follows from the fact that if $S\mathrm{,}{S}^{\prime }$ are any two elements of $\mathcal{B}$, then the distributions of the random variables $v\left(G_n\mathrm{,}S\right)\mathrm{,}v\left(G_n\mathrm{,}{S}^{\prime }\right)$ with $G_n$ sampled from $G\left(n\mathrm{,}{p}_n\right)$ are isomorphic via any permutation of the vertex set $\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ which carries S to $S^{\prime }$. In particular

$P\left[v\left(G_n\mathrm{,}S\right)\le \left(q-{\delta }_n\right)m\right]=P\left[v\left(G_n\mathrm{,}{S}^{\prime }\right)\le \left(q-{\delta }_n\right)m\right]\mathrm{,}$

so that the second line follows from the fact that $\left|\mathcal{B}\right|=\left(\begin{array}{c}n\\ \lceil {ϵ}_{n}n\rceil \end{array}\right)$.

By Lemma 2, we find that

$\log \left(\begin{array}{c}n\\ \lceil {ϵ}_{n}n\rceil \end{array}\right)=\left(1+o\left(1\right)\right)\lceil {ϵ}_{n}n\rceil \log \frac{1}{{ϵ}_n}$

since $\lceil {ϵ}_{n}n\rceil =\lceil n^{1-s}\rceil =o\left(n\right)$, so that

$\begin{array}{l}\log P\left[\underset{S\in \mathcal{B}}{{\displaystyle V}}v\left(G_n,S\right)\le \left(q-{\delta }_n\right)m\right]\le \log \left(\left(\begin{array}{c}n\\ \lceil {ϵ}_{n}n\rceil \end{array}\right)\exp \left(-2{\delta }_n^{2}m\right)\right)\\ =\log \left(\begin{array}{c}n\\ \lceil {ϵ}_{n}n\rceil \end{array}\right)+\log \exp \left(-2{\delta }_n^{2}m\right)\\ =\left(1+o\left(1\right)\right)\lceil {ϵ}_{n}n\rceil \log \frac{1}{{ϵ}_n}-2{\delta }_n^{2}m.\end{array}$

Substituting in our definitions ${\delta }_n=n^{-l},{ϵ}_n=n^{-s}$, we find that since $\lfloor n\rfloor =n\left(1-o\left(1\right)\right)$,

$\begin{array}{l}\log P\left[\underset{S\in \mathcal{B}}{{\displaystyle V}}v\left(G_n,S\right)\le \left(q-{\delta }_n\right)m\right]\\ \le \left(1+o\left(1\right)\right)\lceil n^{1-s}\rceil \log \left(n^s\right)-2n^{-2l}\lfloor \left(1-n^{-s}\right)n\rfloor \\ =\left(s+o\left(1\right)\right)\lceil n^{1-s}\rceil \log \left(n\right)-2n^{1-2l}\left(1-n^{-s}\right)\left(1-o\left(1\right)\right).\end{array}$

This expression tends to negative infinity as $n\to \infty$ since $1-2l>1-s$ by the condition that $l<\frac{s}{2}$, implying that

$P\left[\underset{S\in \mathcal{B}}{{\displaystyle V}}v\left(G_n\mathrm{,}S\right)\le \left(q-{\delta }_n\right)m\right]$

tends to 0 from above. Thus, for n sufficiently large, we have that

$P\left[\underset{S\in \mathcal{B}}{{\displaystyle V}}v\left(G_n\mathrm{,}S\right)\le \left(q-{\delta }_n\right)m\right]<ϵ\mathrm{,}$

and hence

$P\left[\underset{S\in \mathcal{B}}{\min }v\left(G_n\mathrm{,}S\right)\ge \left(q-{\delta }_n\right)m\right]>1-ϵ\mathrm{.}$

Moreover, if we substitute in our definitions $q=1-{\left(1-p_n\right)}^{\lceil {ϵ}_{n}n\rceil }$, ${\delta }_n=n^{-l}$, $m=\lfloor \left(1-{ϵ}_n\right)n\rfloor$, we find that

$\left(q-{\delta }_n\right)m=\left(1-{\left(1-p_n\right)}^{\lceil n^{1-s}\rceil }-n^{-l}\right)\lfloor \left(1-n^{-s}\right)n\rfloor .$

Since by definition $s<1-c$, where $p_n=\Omega \left(n^{-c}\right)$, we have that $1-s>c$, and hence by Lemma 3, we have that ${\left(1-p_n\right)}^{\lceil n^{1-s}\rceil }\to 0$ as $n\to \infty$. Thus,

$\begin{array}{c}\left(q-{\delta }_n\right)m=\left(1-{\left(1-p_n\right)}^{\lceil n^{1-s}\rceil }-n^{-l}\right)\lfloor \left(1-n^{-s}\right)n\rfloor \\ =\left(1-o\left(1\right)\right)\lfloor \left(1-n^{-s}\right)n\rfloor \\ =\left(1-o\left(1\right)\right)n-1,\end{array}$

so that for any $\delta >0$,

$\left(q-{\delta }_n\right)m\ge \left(1-\delta \right)n-1.$

for n sufficiently large. Hence, for any $\delta ,ϵ>0$, we find that for n sufficiently large,

$\begin{array}{l}P\left[\text{MINVS}\left(G_n\right)\ge \left(1-\delta \right)n-1\right]\\ \ge P\left[\text{MINVS}\left(G_n\right)\ge \left(q-{\delta }_n\right)m\right]\\ \ge P\left[\underset{S\in \mathcal{B}}{\min }v\left(G_n,S\right)\ge \left(q-{\delta }_n\right)m\right]\\ >1-ϵ,\end{array}$

as desired.

Proof of Theorem 3. Observe that $\text{MAXVS}\left(G_n\right)\le n-1$. Let $\delta ,ϵ>0$ be given. Since $\frac{n-1}{\left(1-x\right)n-1}\to 1$ from above as $x\to 0$, set ${\delta }^{\prime }$ so that for large n, $\frac{n-1}{\left(1-{\delta }^{\prime }\right)n-1}<1+\delta$. By Lemma 6, there exists a natural number N such that for $n\ge N$,

$P\left[\text{MINVS}\left(G_n\right)\ge \left(1-{\delta }^{\prime }\right)n-1\right]>1-ϵ\mathrm{.}$

Thus, with probability greater than $1-ϵ$,

$\frac{\text{MAXVS}\left(G_n\right)}{\text{MINVS}\left(G_n\right)}\le \frac{n-1}{\left(1-{\delta }^{\prime }\right)n-1}<1+\delta ,$

so that

$P\left[\text{GAPVS}\left(G_n\right)<1+\delta \right]>1-ϵ$

as desired.

Even though our proof of Theorem 4 does not follow quite as readily from the proof of Theorem 3 as for the edge bisection/cut width case above, it does not require any new techniques.

Proof of Theorem 4. Let $\delta ,ϵ>0$ be given. Since $\frac{1}{1-x}\to 1$ from above as $x\to 0$, choose ${\delta }^{\prime }>0$ so that $\frac{1}{1-{\delta }^{\prime }}<1+\delta$. As $\text{MAXVB}\left(G_n\right)\le \lfloor \frac{n}{2}\rfloor$ trivially,

we focus on the lower bound for $\text{MINVB}\left(G_n\right)$. Set ${\delta }_n=n^{-s}$ such that $1-s>c$, where $p_n=n^{-c}$. Since ${\delta }_n\to 0$, we have that

$P\left[\text{MINVB}\left(G_n\right)\le \lfloor \frac{n}{2}\rfloor \left(1-{\delta }^{\prime }\right)\right]\le P\left[\text{MINVB}\left(G_n\right)\le \lfloor \frac{n}{2}\rfloor \left(1-{\delta }_n\right)\right]$

for all n sufficiently large. We will show that

$P\left[\text{MINVB}\left(G_n\right)\le \lfloor \frac{n}{2}\rfloor \left(1-{\delta }_n\right)\right]\to \mathrm{0,}$

which will prove the theorem.

For all $v\in V$, we denote the set of neighbors of v by $N\left(v\right)$ ; that is, $N\left(v\right)=\left\{u\in V|uv\in E\right\}$. If $\varphi \in {\Lambda }_{G_n}$ is a linear arrangement such that $\text{VB}\left(G_n\mathrm{,}\varphi \right)\le \lfloor \frac{n}{2}\rfloor \left(1-{\delta }_n\right)$, then there must exist a subset $S\subset V$ with $\left|S\right|\ge \lfloor \frac{n}{2}\rfloor {\delta }_n$ such that

$\left|{\displaystyle \underset{v\in S}{\cap }N{\left(v\right)}^c}\right|\ge \lfloor \frac{n}{2}\rfloor \mathrm{,}$

where $N{\left(v\right)}^c$ is the complement of $N\left(v\right)$ in V. Indeed, if $\text{VB}\left(G_n\mathrm{,}\varphi \right)\le \lfloor \frac{n}{2}\rfloor \left(1-{\delta }_n\right)$ then by definition there exist ${\delta }_n\lfloor \frac{n}{2}\rfloor$ vertices in the left half of the arrangement $\varphi$ which are not connected to any of the $\lfloor \frac{n}{2}\rfloor$ vertices in the right half.

We estimate the probability that such a set S can exist. Note that it suffices to bound the probability that such an S with $\left|S\right|=\lceil {\delta }_n\lfloor \frac{n}{2}\rfloor \rceil$ can exist since for any such S with $\left|S\right|\ge {\delta }_n\lfloor \frac{n}{2}\rfloor$, we have that there exists a subset $S^{\prime }\subset S$ with $\left|S^{\prime }\right|=\lceil {\delta }_n\lfloor \frac{n}{2}\rfloor \rceil$ satisfying $\left|{\displaystyle {\cap }_{v\in S^{\prime }}}N{\left(v\right)}^c\right|$. Let $S\subset V$ of size $\lceil {\delta }_n\lfloor \frac{n}{2}\rfloor \rceil$ be fixed. Each vertex $u\in S^c$ lies in $N{\left(v\right)}^c$ with probability $1-p_n$, so that for each $u\in S^c$,

$P\left[u\in {\displaystyle \underset{v\in S}{\cap }}N\left(v\right)\right]={\left(1-p_n\right)}^{\left|S\right|}={\left(1-p_n\right)}^{\lceil {\delta }_n\lfloor \frac{n}{2}\rfloor \rceil }={\left(1-p_n\right)}^{n{\delta }_n\left(1+o\left(1\right)\right)/2}\mathrm{.}$

Let $X_n$ be the random variable over the set of random graphs on n vertices with edge probability $p_n$ whose value is the cardinality of ${\displaystyle {\cap }_{v\in S}}N{\left(v\right)}^c$. (Recall that S has been fixed.) Applying the above reasoning to each vertex $u\in S^c$, we

see that $X_n$ is a Bernoulli random variable on $N=\left|S^c\right|=n\left(1-\frac{{\delta }_n}{2}\right)\left(1+o\left(1\right)\right)$ trials with event probability $q={\left(1-p_n\right)}^{n{\delta }_n\left(1+o\left(1\right)\right)/2}$. Since $1-s>c$ by construction, we have that

$q={\left(1-p_n\right)}^{n{\delta }_n\left(1+o\left(1\right)\right)/2}={\left(1-p_n\right)}^{n^{1-s}\left(1+o\left(1\right)\right)/2}\to 0$

as $n\to \infty$ by Lemma 3. Letting $N\mathrm{,}q$ be as before, set

$\gamma =\frac{n}{2N}-q=\left(\frac{1}{2\left(1-{\delta }_n/2\right)}-{\left(1-p_n\right)}^{n{\delta }_n/2}\right)\left(1+o\left(1\right)\right),$

so that $\left(q+\gamma \right)N=n/2$, and $\gamma =\frac{1}{2}\left(1+o\left(1\right)\right)$. Using Hoeffding’s inequality in Lemma 1 with $q\mathrm{,}N\mathrm{,}\gamma$, we obtain that

$\begin{array}{c}P\left[X_n\ge n/2\right]=P\left[X_n\ge \left(q+\gamma \right)N\right]\\ \le \exp \left(-2{\gamma }^{2}N\right)\\ =\exp \left(-2{\left(\frac{1}{2}\right)}^{2}N\left(1+o\left(1\right)\right)\right)\\ =\exp \left(-\frac{n}{2}\left(1-\frac{{\delta }_n}{2}\right)\left(1+o\left(1\right)\right)\right)\\ =\exp \left(-\frac{n}{2}\left(1+o\left(1\right)\right)\right).\end{array}$

By the union bound, the probability that there exists any such S among the subsets of V of size $k=\lceil {\delta }_n\lfloor \frac{n}{2}\rfloor \rceil$ is at most

$\left(\begin{array}{c}n\\ k\end{array}\right)\exp \left(-\frac{n}{2}\left(1+o\left(1\right)\right)\right)\mathrm{.}$

Since $k=n^{1-s}\left(1+o\left(1\right)\right)/2$, by Lemma 2, we have the estimate

$\begin{array}{c}\log \left(\begin{array}{c}n\\ k\end{array}\right)=\left(1+o\left(1\right)\right)k\log \frac{n}{k}\\ =\left(1+o\left(1\right)\right)\frac{n^{1-s}}{2}\log 2n^s\\ =\Theta \left(n^{1-s}\log n\right),\end{array}$

so that $\left(\begin{array}{c}n\\ k\end{array}\right)=\exp \left(\Theta \left(n^{1-s}\log n\right)\right)$. Thus, the union bound probability that there exists any such S is at most

$\begin{array}{c}\left(\begin{array}{c}n\\ k\end{array}\right)\exp \left(-\frac{n}{2}\left(1+o\left(1\right)\right)\right)=\exp \left(\Theta \left(n^{1-s}\log n\right)\exp \left(-\frac{n}{2}\left(1+o\left(1\right)\right)\right)\right)\\ =\exp \left(\Theta \left(n^{1-s}\log n-\frac{n}{2}\right)\right)\\ \to 0\end{array}$

as $n\to \infty$, since the $-\frac{n}{2}$ term dominates the $\Theta \left(n^{1-s}\log n\right)$ term.

We conclude that

$P\left[\text{MINVB}\left(G_n\right)\le \lfloor \frac{n}{2}\rfloor \left(1-{\delta }^{\prime }\right)\right]\le P\left[\text{MINVB}\left(G_n\right)\le \lfloor \frac{n}{2}\rfloor \left(1-{\delta }_n\right)\right]\le ϵ$

for all ${\delta }^{\prime }\mathrm{,}ϵ$ with n sufficiently large. As $P\left[\text{MAXVB}\left(G_n\right)\le \lfloor \frac{n}{2}\rfloor \right]=1$, since we chose ${\delta }^{\prime }$ to satisfy $\frac{1}{1-{\delta }^{\prime }}<1+\delta$, we conclude that

$\begin{array}{l}P\left[\text{GAPVB}\left(G_n\right)\le 1+\delta \right]\\ \ge P\left[\text{MAXVB}\left(G_n\right)\le \lfloor \frac{n}{2}\rfloor \wedge \text{MINVB}\left(G_n\right)\ge \lfloor \frac{n}{2}\rfloor \left(1-{\delta }^{\prime }\right)\right]\\ =P\left[\text{MINVB}\left(G_n\right)\ge \lfloor \frac{n}{2}\rfloor \left(1-{\delta }^{\prime }\right)\right]\\ \ge 1-ϵ\end{array}$

for large enough n, as desired.

4.2. Directed Graph Problems

We now show that the analogous versions of the above problems for undirected graphs hold for directed graphs. Fortunately, no new techniques are required and the desired results for directed graphs follow immediately from our work for undirected graphs.

For the theorems that follow, let ${\left\{G_n\right\}}_{n=1}^{\infty }$ be a sequence of random directed acyclic graphs such that for each $n=1,2,\cdots$, $G_n$ is independently sampled from a $D\left(n\mathrm{,}{p}_n\right)$ Erdös-Renyi distribution with edge probability $p_n$. Similar to before, the following theorems show that for each of the directed arrangement problems GAPDCW, GAPDEB, GAPDVS, and GAPDVB that the ratio of the maximum value to the minimum value of the corresponding objective function over all arrangements of $G_n$ is asymptotically close to 1 with high probability, subject to appropriate sparsity conditions.

Theorem 5. Let $p_n$ satisfy $p_n=\Omega \left(n^{-c}\right),c<1/2$. Then for all $ϵ>0,\delta >0$ there exists an N such that for all $n\ge N$,

$P\left[\text{GAPDCW}\left(G_n\right)<1+\delta \right]>1-ϵ.$

Theorem 6. Let $p_n$ satisfy $p_n=\Omega \left(n^{-c}\right),c<1/2$. Then for all $ϵ>0,\delta >0$ there exists an N such that for all $n\ge N$,

$P\left[\text{GAPDEB}\left(G_n\right)<1+\delta \right]>1-ϵ.$

Theorem 7. Let $p_n$ satisfy $p_n=\Omega \left(n^{-c}\right),c<1$. Then for all $ϵ>0,\delta >0$ there exists an N such that for all $n\ge N$,

$P\left[\text{GAPDVS}\left(G_n\right)<1+\delta \right]>1-ϵ.$

Theorem 8. Let $p_n$ satisfy $p_n=\Omega \left(n^{-c}\right),c<1$. Then for all $ϵ>0,\delta >0$ there exists an N such that for all $n\ge N$,

$P\left[\text{GAPDVB}\left(G_n\right)<1+\delta \right]>1-ϵ.$

We illustrate the proof for Theorem 5; the proofs of Theorems 6, 7, 8 will follow verbatim.

Proof of 5. For $G_n$ a directed acyclic graph sampled from $D\left(n\mathrm{,}{p}_n\right)$, let

$\text{MAXCW}\left(G_n\right)\mathrm{,}\text{MINCW}\left(G_n\right)\mathrm{,}\text{GAPCW}(Gn)$

denote the quantities MAXCW, MINCW, GAPCW for the undirected graph corresponding to $G_n$ ; that is, $G_n$ with every directed edge replaced with an undirected edge. Recall that $\text{MAXCW}\left(G_n\right)$ is the maximum of $\text{CW}\left(G_n\mathrm{,}\varphi \right)$ over all permutations $\varphi$ of the vertex set V of $G_n$, whereas $\text{MAXDCW}\left(G_n\right)$ is the maximum of $\text{CW}\left(G_n\mathrm{,}\varphi \right)$ over all topological sorts $\varphi$ of $G_n$. Since the set of topological sorts is a subset of the set of permutations, we conclude that

$\text{MAXDCW}\left(G_n\right)\le \text{MAXCW}\left(G_n\right)\mathrm{.}$

Similarly, we deduce that

$\text{MINDCW}\left(G_n\right)\ge \text{MINCW}\left(G_n\right)\mathrm{,}$

so that

$\text{GAPDCW}\left(G_n\right)=\frac{\text{MAXDCW}\left(G_n\right)}{\text{MINDCW}\left(G_n\right)}\le \frac{\text{MAXCW}\left(G_n\right)}{\text{MINCW}\left(G_n\right)}=\text{GAPCW}\left(G_n\right).$

Note that this holds for all directed acyclic graphs $G_n$ drawn from $D\left(n\mathrm{,}{p}_n\right)$.

In order to derive a gap convergence statement for GAPDCW from the convergence result for GAPCW, we need to relate the distributions $D\left(n\mathrm{,}{p}_n\right)$ and $G\left(n\mathrm{,}{p}_n\right)$. Let $\varphi$ be the map from the underlying set of $G\left(n\mathrm{,}{p}_n\right)$ to the underlying set of $D\left(n\mathrm{,}{p}_n\right)$ which takes an undirected graph $G_n$ on the vertex set $\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ to the corresponding directed graph with the oriented edge $\left(i\mathrm{,}j\right)$ if $i<j$ and $\left\{i\mathrm{,}j\right\}$ is an edge of $G_n$. By the definition of $D\left(n\mathrm{,}{p}_n\right)$ we have that $\varphi$ is a bijection between the underlying sets of $G\left(n\mathrm{,}{p}_n\right)$ and $D\left(n\mathrm{,}{p}_n\right)$, with inverse just given by replacing each directed edge with the corresponding undirected edge. Moreover, by the definition of $D\left(n\mathrm{,}{p}_n\right)$ we have that $\varphi$ preserves probabilities between $G\left(n\mathrm{,}{p}_n\right)$ and $D\left(n\mathrm{,}{p}_n\right)$, so that $\varphi$ is an isomorphism between the probability distributions $G\left(n\mathrm{,}{p}_n\right)$ and $D\left(n\mathrm{,}{p}_n\right)$.

Thus, let $p_n\mathrm{,}ϵ\mathrm{,}\delta$ be as in the statement of Theorem 5. By Theorem 1, there exists an N such that for all $n\ge N$,

$P\left[\text{GAPCW}\left(G_n\right)<1+\delta \right]>1-ϵ,$

where $G_n$ is sampled from $G\left(n\mathrm{,}{p}_n\right)$. By the isomorphism between $D\left(n\mathrm{,}{p}_n\right)$ and $G\left(n\mathrm{,}{p}_n\right)$, we have that the same statement holds if $G_n$ is instead sampled from $D\left(n\mathrm{,}{p}_n\right)$ and $\text{GAPCW}\left(G_n\right)$ is defined as previously by taking the underlying undirected graph. Since

$\text{GAPDCW}\left(G_n\right)\le \text{GAPCW}(Gn)$

for all $G_n$ sampled from $D\left(n\mathrm{,}{p}_n\right)$, we conclude that

$P\left[\text{GAPDCW}\left(G_n\right)<1+\delta \right]\ge P\left[\text{GAPCW}\left(G_n\right)<1+\delta \right]>1-ϵ$

for all $n\ge N$, where $G_n$ is sampled from $D\left(n\mathrm{,}{p}_n\right)$. This proves Theorem 5.

The same observation that the set of topological sorts of a directed graph is a subset of the set of permutations of the vertices implies that the quantities GAPDEB, GAPDVS, GAPDVB are bounded above by the corresponding undirected quantities as in the above proof. Thus, Theorems 6, 7, 8 follow precisely from the corresponding undirected versions, Theorems 2, 3, 4, as desired.

5. Concluding Remarks

In this paper, we have shown that many graph layout problems of interest can be approximated arbitrarily close to the optimal with high probability for large random graphs with appropriate sparsity conditions. We note that there is still room for improvement with our results. The previous factor of 2 approximations in [7] held for edge probabilities $p_n=\Omega \left(n^{-1}\right)$, whereas our results for the layout problems on edges (that is, minimum cut linear arrangement, edge bisection, and directed versions) only hold for $p_n=\Omega \left(n^{-c}\right)$ for $c<1/2$. Thus, we pose the following:

Question: Can the factor of 1 approximation results for MINCW, MINEB, be proven for random graphs with $p_n=\Omega \left(n^{-1}\right)$, or more generally $p_n=\Omega \left(f\left(n\right)\right)$ for $f\left(n\right)=o\left(n^{-1/2}\right)$ ? If not, can one determine the barrier between $p_n=\Omega \left(n^{-1/2}\right)$ and $p_n=\Omega \left(n^{-1}\right)$ where the factor of 1 approximation no longer holds and must be replaced by a factor of 2?

Both outcomes to the above question would be interesting, but we would find it more surprising if there were such a “sparsity barrier” between factor of 1 and factor of 2 approximations. Moreover, the results in [7] do not experience the same tradeoff between sparsity and speed of convergence that our results do, a seeming consequence of the strength of their “mixing graph” framework. Here by “speed of convergence”, we refer to how quickly $\delta$ shrinks in our statements of the form “ $\text{GAP}\left(G_n\right)\le 1+\delta$ with probability $1-ϵ$ ”, where $\text{GAP}\left(G_n\right)$ is a stand-in for GAPCW, GAPVS, ..., etc. In [9], they are able to take $\delta =O\left(n^{-1}\right)$ independent of $p_n$, whereas we are only typically able to take $\delta =O\left(n^{c-l}\right)$ where $p_n=O\left(n^{-c}\right)$ and $c<l<1/2$. Thus, we ask:

Question: Can the factor of 1 approximation results for MINCW, MINVS, MINEB, MINVB be proven with $\delta =O\left(n^{-1}\right)$ with $\delta$ as above, or at least for a $\delta$ which does not depend on the asymptotics for $p_n$ ?

Our asymptotics for $ϵ$ as above do technically depend on $p_n$, but regardless of $p_n$ our asymptotics for $ϵ$ are still competitive with the $ϵ=2^{-\Omega \left(n\right)}$ bound in [7], in contrast to the situation for $\delta$. For a possible solution of the above questions, we note that some of the key results about mixing graphs used in [7] call upon the Hoeffding inequality, which was our primary probabilistic tool in this paper. Hence, it would be interesting to see if the techniques of this paper and those of mixing graphs could be unified somehow to give our improved constant of approximation but retain the better sparsity and convergence conditions of [7].

Acknowledgements

The authors would like to thank Emmanuel Ruiz and Ashkan Moatamed for conversations on research involving graph layout problems. Additionally, the research in this paper was made possible by the support of the Fields Institute through its 2017 Fields Undergraduate Summer Research Program.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Díaz, J., Petit, J. and Serna, M. (2002) A Survey of Graph Layout Problems. ACM Computing Surveys, 34, 313-356. https://doi.org/10.1145/568522.568523
[2]	Lengauer, T. (1981) Black-White Pebbles and Graph Separation. Acta Informatica, 16, 465-475. https://doi.org/10.1007/BF00264496
[3]	Gavril, F. (2011) Some NP-Complete Problems on Graphs. 2011 45th Annual Conference on Information Sciences and Systems, Baltimore, MD, 23-25 March 2011.
[4]	Cheung, K., Girardet, P., Moatamed, A. and Ruiz, E. (2018) On a Directed Layout Problem. Manuscript in Preparation.
[5]	Brandes, U. and Fleischer, D. (2009) Vertex Bisection Is Hard, too. Journal of Graph Algorithms and Applications, 13, 119-131. https://doi.org/10.7155/jgaa.00179
[6]	Garey, M.R. and Johnson, D.S. (1979) Computers and Intractibility: A Guide to the Theory of NP Completeness. Freeman and Co., New York.
[7]	Díaz, J., Petit, J., Trevisan, L. and Serna, M. (2001) Approximating Layout Problems on Random Graphs. Discrete Mathematics, 235, 245-253. https://doi.org/10.1016/S0012-365X(00)00278-8
[8]	Gilbert, E.N. (1959) Random Graphs. The Annals of Mathematical Statistics, 30, 1141-1144.
[9]	Barak, A.B. and Erdös, P. (1984) On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph. SIAM Journal on Algebraic Discrete Methods, 5, 508-514.
[10]	Hoeffding, W. (1963) Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58, 13-30. https://doi.org/10.1080/01621459.1963.10500830