Theoretical Analyses

Upper Bounds on the Multicommodity Flow Bounds

In order to support the statement that the VarMC and MVarMC instances deliver better bounds than the known 1-1-MC instance, we have examined the maximal possible bound of graph bisection problems with these instances, if an infeasible partition of the graph with a relative small CutSize exists. It is obvious that the lower bounds basing on Multicommodity Flows have a problem if there exists e.g. a partition into two partitions with sizes ${\frac{n}{4}}$ and ${\frac{3}{4}}$n with a CutSize of one. This single edge forms a bottleneck for the flows an the congestion will be quite large. But we will see that the three different instances can react differently upon such a situation:

Theorem 4  
We have a Graph Partitioning problem with graph G, node weights g, edge weights f and parameters p = 2, M = ${\frac{N}{2}}$. Using the 1-1-MC instance for each partition V = V₁ $\cup$ V₂ with N_i = $\sum_{v\in V_{i}}^{}$g(v) we get a maximal lower bound of

Bound $$\leq$$ $${\frac{N^{2}}{4N_{1}N_{2}}}$$CutSize(V₁, V₂).

In contrast to the simple 1-1-MC instance the VarMC instance can react on a bottleneck such that the flow across these bottleneck is smaller:

Theorem 5  
We have a Graph Partitioning problem with graph G, node weights g, edge weights f and parameters p = 2, M = ${\frac{N}{2}}$. Using the VarMC instance for each partition V = V₁ $\cup$ V₂ with N_i = $\sum_{v\in V_{i}}^{}$g(v) we get a maximal lower bound of

Bound $$\leq$$ $${\frac{N}{2\cdot \min \{N_{1},N_{2}\}}}$$CutSize(V₁, V₂).

These upper bounds show that the VarMC instance can react better onto the given graph. The difference is the bigger the smaller min{N₁, N₂} is. Examining the MVarMC instance with a graph of a known infeasible partition no upper bound can be shown at all since the MVarMC instance has the freedom to send nothing across a specific infeasible partition.

Butterfly and Beneš Network

In this section we show that the new VarMC bound and MVarMC bound techniques can also be used for theoretical analyses of lower bounds on the Graph Partitioning problem and can give improved lower bounds compared with the known 1-1-MC. Here we consider the butterfly network without wraparound which has been studied extensively. The butterfly network of dimension d has a simple bisection with CutSize = 2^d. In [1] it has been shown that the bisection width is 2($\sqrt{2}$ - 1)2^d + o(2^d) $\approx$ 0.83 ^. 2^d . Here we will show that the known 1-1-MC can prove an asymptotic lower bound of ${\frac{1}{2}}$2^d while the VarMC can prove an asymptotic lower bound of ${\frac{2}{3}}$2^d.

Lemma 3  
Solving a Multicommodity Flow instance with a butterfly of dimension d with (d + 1)2^d vertices. All vertices of level l sends one commodity to every other vertex of the graph. We use Load (k, l ) as the sum of flows over all edges of level k. We define X_{d, k} : = d + k + 2 - 2(k + 1)2^{k - d} and Y_{d, k} : = 2d - k + 1 - (d - k)2^-k. Then

Load (k, l )= 2^{2d .} $$\left\{\vphantom{ \begin{array}{ll} X_{d,k} & \textrm{if }k\geq l\\ Y_{d,k} & \textrm{else} \end{array}}\right.$$$$\begin{array}{ll} X_{d,k} & \textrm{if }k\geq l\\ Y_{d,k} & \textrm{else} \end{array}$$

if the flow is realized using only shortest paths and cannot be improved by any other realization.

Using the above Lemma we can show the following Theorems:

Theorem 6  
The 1-1-MC instance delivers a lower bound on the graph bisection problem of a butterfly network with dimension d without wraparound edges of (${\frac{1}{2}}$ + o(1))2^d.

Theorem 7  
The VarMC instance delivers a lower bound on the graph bisection problem of a butterfly network with dimension d without wraparound edges of (${\frac{2}{3}}$ + o(1))2^d.

The butterfly network is an example of a quite regular network where the VarMC instance gives a better lower bound on the bisection problem with equally sized partitions than the known 1-1-MC. Furthermore, it is remarkable that the above analysis can be adapted to the Beneš network, a kind of back-to-back butterfly. The Beneš network has a similar simple bisection with CutSize = 2^{d + 1}. To our knowledge the asymptotically exact bisection width is unknown. Using the 1-1-MC we get a lower bound of ${\frac{1}{2}}$2^{d + 1} while the VarMC instance where only the two most outside levels of vertices and the most inside level of vertices send commodities delivers a lower bound of ${\frac{2}{3}}$2^{d + 1}.