On rearrangeable multirate three-stage Clos networks

参考文献：Dou, W., & Yao, E. (2007). On rearrangeable multirate three-stage Clos networks. Theoretical computer science, 372(1), 103-107.

问题描述

本文研究Clos network的rearrangeability性质的相关问题，与

Yihan Chen (2022). On multirate rearrangeable Clos networks.

和

Yihan Chen (2022). Improved bounds on nonclocking 3-stage Clos networks.

中描述的问题类似，但有细微差别：在上两篇博文中，$n$表示的是使得$$\sum\limits_{e\in \delta(v)}w(e)\leq n, \forall v\in V$$成立的最小正整数。而在本篇博文中$$n=\min\{m\in \mathbb{Z}|\forall v\in V(G),\text{与}v\text{关联的边的权可以被打包进}m\text{个容量为}1\text{的bin中}\}$$

这个问题转化为图论语言如下：

记号

• 考虑带权二部图$G=(V,E)$, 设$G$的两部分别为$\mathcal{I}$、$\mathcal{J}$（其中$|\mathcal{I}|=|\mathcal{J}|=r$）。

• 对任意的$e\in E$, 它的权为$w(e)\in [0,1]$.

• $\delta(v)$为顶点$v$的邻居集。

• $n=\min\{m\in \mathbb{Z}|\forall v\in V(G),\text{与}v\text{关联的边的权可以被打包进}m\text{个容量为}1\text{的bin中}\}$

• $\mathcal{B}_r^n$为满足

  $$\sum\limits_{e\in \delta(v)}w(e)\leq n, \forall v\in V$$的所有二部图$G=(V,E), V=\mathcal{I}\cup \mathcal{J}$（$|\mathcal{I}|=|\mathcal{J}|=r$）构成的集合。

问题

Problem. 求最小的正整数$c$使得$\forall G \in \mathcal{B}_r^n,$ 存在$G$的$c$-边染色使得$\forall v\in V$, $G$中与$v$关联的相同颜色的边的权和不超过$1$.

结果

记所需要的最少颜色数为$m(n,r)$, Chung和Ross在1991年猜想$m(n,r)\leq 2n-1$. 本文证明了

Theorem 2.9. $m(n, r) ≤ \min\{\lfloor \frac{7n}{4}+\frac{5r}{8}+\frac{15}{8}\rfloor,\lfloor \frac{7n}{4}+\frac{r+1}{2}+\frac{1}{4}\min\{n,r\}\rfloor\}$

证明

对顶点$I\in \mathcal{I}$和$J\in \mathcal{J},$ 我们记$I,J$之间的重边构成的集合为$R(I,J),$ 将$R(I,J)$中的边按照权重从大到小的顺序贪婪地进行分组$R(I,J)=R_1(I, J)\cup R_2(I, J)\cup . . . \cup R_l (I, J)$其中$R_i(I,J)$中的边的权重之和不超过$1,$ $i=1,2,\dots,l.$

我们有如下观察：

Lemma 2.1. $\forall I\in \mathcal{I}, J\in \mathcal{J}$和$1\leq i\leq l-1,$ 我们有$W_i(I,J)> \frac{1}{2}.$

Lemma 2.2. $\forall I\in \mathcal{I}, J\in \mathcal{J}$和$1\leq i\leq l-1,$ $W_i(I,J)$的大小为下列两种情况之一：

• $W_i(I,J)> \frac{2}{3}.$
• 若$W_i(I,J)\leq \frac{2}{3},$ 则$R_i(I,J)$中只有一条边并且这条边的权重大于$\frac{1}{2}.$

Proof. 设$W_i(I,J)$不满足第一种情况，即$W_i(I,J)\leq \frac{2}{3},$ 设$R_i(I,J)$中的边为$r_{i_1},\dots,r_{i_t},$ 则$w(r_k)\leq w(r_{i_t})\leq \frac{W_i(I,J)}{t}\leq \frac{2}{3t}.$ 假设$t\geq 2,$ 则$w(r_k)\leq \frac{1}{3},$ 从而$r_k$可以加入到$R_i(I,J)$中，矛盾。

从而$t=1$, 假设$w(r_{i_1})\leq \frac{1}{2}, $ 则$w(r_k)\leq w(r_{i_1})\leq \frac{1}{2},$ $r_k$还是可以加入到$R_i(I,J)$中，矛盾。

Theorem 2.4. $m(n,r)\leq \lfloor \frac{7n}{4}+\frac{r+1}{2}+\frac{1}{4}\min(n,r)\rfloor.$

Outline of proof. 对任意$I,J,$ 首先我们将每个$R_i(I,J)$合并成一条边，并且令这条边的权重为$W_i(I,J),$ 得到的图记为$G’.$ 接下来给$G’$边染色从而导出$G$的边染色。

对$G’$，我们将权重$> \frac{1}{2}$的边称为Large的，权重$\leq \frac{1}{2}$的边称为Small的。所有Large的边导出的子图记为$L,$ 所有Small的边导出的子图记为$S.$

则$S$的最大度$\leq r$（因为$\forall I,J$只有$R_l(I,J)$可能是Small的。）从而$S$可以被$\lceil \frac{r}{2}\rceil$种颜色染好。

对于$L$, $\forall I\in V(L),$ 设$R(I)$为$L$中与$I$关联的边组成的集合，我们设$R(I)$中有$x$条边的权重$< \frac{2}{3}, $ $y$条边的权重符合Lemma 2.2中的第二种情况，$z$条边的权重不满足前述的两种情况。则我们估计$x+y+z$便可估计出$\Delta(L)$的上界。

由问题条件，我们有三个不等式：

• $y\leq n,$
• $z\leq r,$
• $\frac{1}{2}(y+z)+\frac{2}{3}x\leq n.$

通过这三个不等式，我们便可以解出$x+y+z\leq \lfloor \frac{3n}{2}+\frac{1}{4}\min(2n,n+r)\rfloor.$

从而我们只需要用$\lfloor \frac{3n}{2}+\frac{1}{4}\min(2n,n+r)\rfloor+\lceil \frac{r}{2}\rceil\leq \lfloor \frac{7n}{4}+\frac{r+1}{2}+\frac{1}{4}\min(n,r)\rfloor$种颜色便可把$G$染好，证毕。

Theorem 2.7. $m(n,r)\leq \lfloor \frac{7n}{4}+\frac{5r}{8}+\frac{15}{8}\rfloor.$

Outline of proof. 这个定理的证明跟Theorem 2.4的证明是类似的，唯一的不同是该定理的证明中用了

Lemma 4. Let $G$ be any bipartite graph and suppose $k ≥ 1.$ Then $G$ is the union of $k$ edge-disjoint spanning subgraphs $G_1,…,G_k$ such that $$\lfloor\frac{d_G(v)}{k}\rfloor ≤ d_{G_i}(v) ≤ \lceil\frac{d_G(v)}{k}\rceil\text{ for each }v ∈ G.$$

运用这个引理，作者把$S$分解成了$S_1\cup S_2\cup S_3\cup S_4, $ 再分别考虑了$L’=L\cup S_1$和$S’=S_2\cup S_3\cup S_4$的最大度，以及用Konig theorem得到了它们所需的颜色数，最后加起来得到了定理中的结论。

Remark

这篇文章的定理虽然都是针对$m(n,r)$的，但用同样的方法也能得到关于$M(n,r)$的结果，即只要把证明中的$y\leq n$改为$y\leq 2n.$ 这样我们可以得到$M(n,r)\leq \lfloor 2n+\frac{3r+2}{4}\rfloor,$ 当$n$远大于$r$时，这个界贴近$2n, $ 也较为接近$2n-1.$