本問題は，\(\mathbb{F}_2^N\) 上の方程式を解く問題に帰着することで解くことができます．以降，すべての演算は \(\mathbb{F}_2\) 上で考えます．

いくつかの記号を定義します．

• \(A\)：与えられるグラフの隣接行列．
• \(d_v\)：頂点 \(v\) の次数．
• \(D\)：\(d_v\) を対角成分に持つ行列．すなわち \(D = \mathrm{diag}(d_1, d_2, \ldots, d_N)\)．
• \(d\)：\(N\) 次元ベクトル \((d_1, d_2, \ldots, d_N)^{\top}\)．
• \(N(v)\)：頂点 \(v\) に隣接する頂点の集合．

また，\(x = (x_1, x_2, \ldots, x_N)^{\top}\in \mathbb{F}_2^N\) を \(x_v = 0 \iff v \in X\) と定めることで頂点集合の分割 \((X, Y)\) と同一視します．

\(S =\) ??...? のとき

\(x \in \mathbb{F}_2^N\) が条件を満たす分割であることと，\(x\) が \(\mathbb{F}_2^N\) 上の方程式

\[ (A + D + I)x = d+\bm{1} \]

を満たすことは同値です．ただし \(I\) は \(N\) 次単位行列，\(\bm{1}\) は全成分が \(1\) の \(N\) 次元ベクトルです．実際，\((A + D + I)x = y = (y_1, y_2, \ldots, y_N)^{\top}\) とおくと

\[ \begin{aligned} y_v &= \sum_{u\in N(v)}x_u + (d_v + 1)x_v \\ &= |N(v)\cap Y| + (d_v + 1)x_v \end{aligned} \]

が成り立ち，\(d_v = |N(v)\cap X| + | N(v)\cap Y|\) に注意すると \(x_v = 0, 1\) どちらの場合も \(y_v = d_v + 1\) となることが確認できます．

したがって，この方程式を解けば \(x\) が求まります．

\(S\) が一般のとき

\(e_v \in \mathbb{F}_2^N\) を，第 \(v\) 成分だけが \(1\) であるような \(N\) 次元ベクトルとします．

\(S_v = \) X のとき \(e_v^{\top}x = 0\) が成り立ちます．また，\(S_v = \) Y のとき \(e_v^{\top}x = 1\) が成り立ちます．これらを方程式の制約に追加したうえで方程式を解けば \(x\) が求まります．

結局，高々 \(2N\) 個の制約を持つ方程式の解を求めることができればこの問題を解くことができます．これは掃き出し法を用いて \(\mathrm{O}(N^3)\) で行うことができます．

余談

\(S = \) ??...? のとき，必ず解が存在します．余力のある方は証明してみましょう．