# LCL Problem in the black-white formalism

我们首先考虑一类问题，被称为 "locally checkable labeling" (LCL) 问题。
我们考虑一种它的特殊形式，即 LCL problem in the black-white formalism。

考虑一个二分图$G=(V,E)$，其中$V=W\cup B$ 是二分图的两个部分，第一部分被称为 White nodes，第二部分是 Black nodes。

那么一个 LCL problem in the black-white formlism 是一个 tuple $\Pi=(\Sigma_{in},\Sigma_{out},\mathcal{C}_w,\mathcal{C}_b)$，其中

• $\Sigma_{in},\Sigma_{out}$ 是两个 finite sets，包含了 labels；
• $\mathcal{C}_w,\mathcal{C}_b$ 是两个 sets of multisets，其中每个 multisets 中的元素都是来自于$\Sigma_{in}\times \Sigma_{out}$。

其中$\mathcal{C}_w,\mathcal{C}_b$ 理解为某种 constraints，即合法的 labeling 方式。形式化地，给定一个把所有 edge 都 labeling 的 assignment$i:E\to \Sigma_{in}$ 作为 input，一个 assignment $o:E\to \Sigma_{out}$ 被称为是一个 solution to $\Pi$ 如果它满足 while and black constraints，即：

• 对于每个 white node $w\in W$，假设$e_1,...,e_{d_w}$ 是与$w$ 相连的 edges，那么

$$\{ (i(e_1),o(e_1)),...,(i(e_{d_w}),o(e_{d_w})) \} \in \mathcal{C}_w;$$

• 对于每个 black node $b\in B$，假设$e_1,...,e_{d_b}$ 是与$b$ 相连的 edges，那么

$$\{ (i(e_1),o(e_1)),...,(i(e_{d_b}),o(e_{d_b})) \} \in \mathcal{C}_b.$$

# Port-numbering model

一个 port-numbered network 被形式化地定义为一个 triple $N=(V,P,p)$，其中

• $V$ 是 nodes 的集合；
• $P$ 是 ports 的集合，每个 port $x\in P$ 是一个 pair $(v,i)\in V\times\mathbb{N}_{>0}$。我们称 port $(v,i)$ 是 node $v$ 的第$i$ 个 port；
• $p:P\to P$ 是一个函数 specifying connections between ports，满足$p(p(x))=x$。