CONGEST 割模拟与四色四环下界

形式陈述

CONGEST模型把输入图同时作为通信网络：同步轮中，每条边每个方向每轮最多传 $B$ bits，有限本地计算免费。节点先按旧状态发送，再接收并更新；网络可靠、无故障，拓扑固定。标准CONGEST取 $B=\Theta(\log N)$ ，其中 $N$ 是顶点数。

本页完整证明一个指定任务的带宽下界。输入是连通简单无向图，每个节点另有一个来自 $\{1,\ldots,6\}$ 的颜色标签；指定节点 $h_R$ 必须判断是否存在按颜色顺序

1\;\longrightarrow\;2\;\longrightarrow\;3\;\longrightarrow\;4\;\longrightarrow\;1

构成的简单四环。这里颜色是输入标签，不需要算法寻找染色；任务也不接受其他颜色顺序的环。算法对每个固定输入的成功概率至少为 $2/3$ ，运行轮数对输入和随机币都有硬上限 $T$ 。节点初始知道自己的ID、颜色、各关联端口、邻居ID、共同规模 $N$ 以及自己是否为指定输出节点；不预知全图。

我们将构造直径 $D\le3$ 的图族，证明对整数 $B\ge1$ ，

\boxed{T=\Omega(N/B).}

特别地，标准消息长度下 $T=\Omega(N/\log N)$ 。这是带指定颜色顺序的四环检测下界；以下构造不支持把结论里的颜色条件删除。

固定割模拟的一般接口

设二方输入 $(x,y)$ 决定图 $G_{x,y}$ ，顶点始终按公开规则分成 $V_L\dot\cup V_R$ 。若左侧内部边与左侧节点的初始状态只依赖 $x$ ，右侧只依赖 $y$ ，跨割边集合 $C$ 固定且公开，且 Bob 能由右侧输出恢复目标函数 $f(x,y)$ ，则一个最坏 $T$ 轮的网络算法产生公共币二方协议，满足

R^{\mathrm{pub}}_{1/3}(f) \le 2|C|(B+1)T.

下面连同变长消息、同轮顺序和随机性一起证明此式。固定割模拟是标准通信下界归约方法。[1, §2.2] 本页的四色图是用于展开账本的具体构造，不把它归称为资料[1]中研究其他图任务的原构造。

直觉

Alice可把自己一侧所有节点放在同一台本地计算机里模拟，Bob也一样。割内的消息只是在各自本地内存之间移动，不消耗二方通信；唯有跨割消息必须真正发给对方。

因此，一轮网络算法能帮助二方传递的信息受割边条数和每边位数限制。困难输入有 $k^2$ 个位置，构造却只给出 $O(k)$ 条跨割边。若算法用太少轮解决图任务，两方就能用太少通信解决任意输入的DISJ。

网络直径很小不会消除这个限制。两个hub使任意顶点间最多隔三跳，但短路径上的每条边仍只有有限带宽。传播距离与跨割总容量是不同的资源。

一个共同的矩阵位置形成颜色1、2、3、4的四环，两侧hub保证整个图连通；输入相关边留在各自一侧，割上只有固定匹配及hub连边 — 同一个输入坐标跨过固定割

图中只画一个共同位置 $(i,j)$ 的四个普通顶点及两个hub，其余下标的顶点和匹配省略。图下的边数和容量公式针对完整图族。

例子与边界

用两个矩阵构造整个网络

取整数 $k\ge2$ 。Alice持有矩阵 $X\in\{0,1\}^{k\times k}$ ，Bob持有 $Y\in\{0,1\}^{k\times k}$ ，分别视为长度 $k^2$ 的位串。顶点及颜色如下：

所属侧	顶点	颜色	数量
Alice	$A_1,\ldots,A_k$	1	$k$
Alice	$B_1,\ldots,B_k$	2	$k$
Alice	$h_L$	5	1
Bob	$B'_1,\ldots,B'_k$	3	$k$
Bob	$A'_1,\ldots,A'_k$	4	$k$
Bob	$h_R$	6	1

总顶点数 $N=4k+2$ 与输入值无关。固定边有三类：每个 $A_i$ 连 $A'_i$ ，每个 $B_j$ 连 $B'_j$ ，另有 $h_Lh_R$ ；此外，每个hub连接己侧的全部 $2k$ 个普通顶点。只有下面两类边随私有输入变化：

A_iB_j\in E\iff X_{ij}=1,\qquad A'_iB'_j\in E\iff Y_{ij}=1.

图没有重边或自环。hub星形和hub桥已经保证连通：同侧普通顶点经hub至多两跳，异侧经两个hub至多三跳，故始终 $D\le3$ 。跨割边恰为

C=\{A_iA'_i:1\le i\le k\} \cup\{B_jB'_j:1\le j\le k\}\cup\{h_Lh_R\}, \qquad |C|=2k+1.

所有输入相关边都在割内。固定唯一ID可用顶点名的公开编号，端口按邻居ID排序；关联边、度数和邻居ID只依赖本侧输入及公开割。因此Alice、Bob分别能初始化自己模拟的全部节点，无须先交换矩阵。模拟者知道图族的公开构造规则，不表示节点初始知道另一侧矩阵或完整图。

四环为何恰好对应一个共同的1

任意目标环都能按颜色写成

A_i-B_j-B'_q-A'_p-A_i.

颜色2到3的固定匹配迫使 $q=j$ ；颜色4到1的固定匹配迫使 $p=i$ 。剩下两条边恰好要求 $X_{ij}=1$ 与 $Y_{ij}=1$ 。反过来，若某个位置同时为1，这四个不同颜色的顶点就组成所需简单四环。因此

\mathrm{FourColorCycle}(G_{X,Y})=1 \iff \exists(i,j):X_{ij}Y_{ij}=1 \iff \operatorname{DISJ}_{k^2}(X,Y)=0.

hub颜色为5和6，不可能进入目标环。矩阵可取任意值，包括全零或全一；固定hub骨架在所有情况下都保持连通，不需另加削弱输入族的承诺。

十顶点实例与颜色边界

令 $k=2$ ，取

X=\begin{pmatrix}1&0\\1&0\end{pmatrix},\qquad Y^{(0)}=\begin{pmatrix}0&1\\0&1\end{pmatrix},\qquad Y^{(1)}=\begin{pmatrix}0&1\\1&1\end{pmatrix}.

对 $Y^{(0)}$ ，两个矩阵没有共同1，故目标四环不存在。把Bob一侧的 $A'_2B'_1$ 加入，就得到 $Y^{(1)}$ ，此时唯一共同位置 $(2,1)$ 给出环

A_2-B_1-B'_1-A'_2-A_2.

两图都为10顶点、5条割边、直径至多3。固定骨架有13条边；前图总边数 $13+2+2=17$ ，后图为18。Alice侧的初始信息在两次输入间完全相同，改变只发生在Bob侧。

即使 $X=Y=0$ ，网络也含普通无色四环 $h_L-A_1-A'_1-h_R-h_L$ 。若忽略颜色，两类输入都可能得到“有环”，归约的等价关系立即失效。同样，输入边 $A_iB_j$ 与hub可形成三角形，但它不是本任务所检测的结构。

推论与应用

一轮怎样被两方精确模拟

Alice保存 $V_L$ 全部节点状态，Bob保存 $V_R$ 全部状态。初态可由各自输入独立生成。归纳假设第 $r-1$ 轮末保存的状态与原算法相同。模拟第 $r$ 轮时：

双方先分别依据己侧各节点旧状态，计算并缓存本轮全部待发消息，包括割内和跨割消息。
按公开割边及方向的固定顺序，交换跨割消息；割内消息直接存入本地对应收件箱。
跨割消息齐备后，各自把全部消息交付给模拟节点，再执行本轮更新。

即使在二方协议中Bob较晚发送，也不能利用刚收到的Alice消息改写本轮已缓存的待发内容。这样没有把同步“先发送、后接收”偷换成同轮的即时多跳交互。归纳保证每轮状态与原网络算法一致。

静默和变长消息占多少位

假设单方向一次发送可以是长度 $0,\ldots,B$ 的任意二进制串，也允许单独的静默符号 $\bot$ 。全部可能符号的数量为

1+\sum_{\ell=0}^B2^\ell=2^{B+1}.

公开固定一个到 $\{0,1\}^{B+1}$ 的双射，每个有向割边每轮占一个固定槽，接收者便能恢复原字符串的长度、内容或静默。若空串和静默等价，所需符号更少，也仍能使用这个预算。“补零再加是否发送bit”未必保留原长度，不能拿它代替上述完整编码。

割内通信不收费，割外每条无向边有两个方向，所以 $T$ 轮的二方通信至多

2|C|(B+1)T=2(2k+1)(B+1)T.

割及槽位次序公开，无须逐条发送边名或轮号。若原算法提前停止，将其已停止状态保持并在后续轮补静默至共同硬上限 $T$ ；最终输出不变。只有期望轮数界时，没有这样的免费固定补齐，需另做截断论证。

随机带、输出方和逐输入错误

在两方公共随机串中，给每个公开节点ID分配一条独立随机带；模拟该节点时只按原算法规则读取对应带。若原算法还使用全局公共随机带，再分配独立一份即可。两方虽然额外看得到这些带，却不利用额外可见性改变模拟规则。对每个固定 $(X,Y)$ ，模拟网络中的随机带联合分布与原算法相同，因此整个状态和输出分布相同。

Bob拥有指定输出节点 $h_R$ 的最终状态，读取它的存在环判定位 $Z$ ，输出 $1-Z$ 即得到DISJ答案。每个固定输入上的成功概率仍至少 $2/3$ ；这里没有先平均输入，也没有假设Alice知道Bob的矩阵。额外公开随机性只使所构造的通信协议更强，而所调用的下界已经允许公共币。

现在应用公共币DISJ线性通信下界：

2(2k+1)(B+1)T \ge R^{\mathrm{pub}}_{1/3}(\operatorname{DISJ}_{k^2}) =\Omega(k^2).

由于 $B\ge1$ 且 $N=4k+2$ ，得到 $T=\Omega(k/B)=\Omega(N/B)$ 。标准带宽 $B=\Theta(\log N)$ 给出 $\Omega(N/\log N)$ ，而图的直径始终至多3。这表明已有BFS式传播距离界不足以描述本任务的困难。

一般顶点数与归约适用范围

前面的图族已有无限多个规模，足以展示渐近下界；若要覆盖每个充分大的 $N$ ，令 $k=\lfloor(N-2)/4\rfloor$ ，将剩余的至多3个顶点全部作为颜色5的公开叶节点连接到Bob侧 $h_R$ 。它们不加入四色环，割边数不变，与任意顶点距离仍至多3，且初态不依赖私有输入。因此同一量级也覆盖中间规模。

本页没有限制本地CPU或内存，因此无法用“节点多算一点”绕过通信账本。换成LOCAL的无界消息后， $B$ 不再受 $O(\log N)$ 限制，轮数下界的这一结论便不能照搬。若节点初始已知全图，指定节点更可直接本地判定；图族的本地输入条件同样不可省略。

归约给出了这个任务的下界，没有证明匹配上界，也没有推出所有直径为3的图任务都困难。其可复用的部分是：独立生成两侧初态、固定且公开的割、可恢复的目标答案，以及保留位数与同步顺序的模拟。

参考资料

[1] Keren Censor-Hillel, Seri Khoury, Ami Paz, “Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model”, DISC, 2017, Article10：§2.2，Definition1与Theorem2及证明，印刷pp.10:5–10:6；§4 Theorem8，p.10:9，讨论由各侧输出恢复通信函数的扩展。本文逐项证明公共币、指定右侧输出及 $B+1$ 位消息编码版本；四色四环构造在本页完整给出。

[2] Alexander A. Razborov, “On the Distributional Complexity of Disjointness,” Theoretical Computer Science106(2), 1992, pp.385–390；随机通信下界的模型和从腐败引理到线性下界的推导见本站对应先修页。

形式陈述 ​

固定割模拟的一般接口 ​

用两个矩阵构造整个网络 ​

四环为何恰好对应一个共同的1 ​

十顶点实例与颜色边界 ​

一轮怎样被两方精确模拟 ​

静默和变长消息占多少位 ​

随机带、输出方和逐输入错误 ​

一般顶点数与归约适用范围 ​

反向链接