[1]} now defines a vertex partition \((V_A, V_B)\)  of \(G_{x, y}\) , where \(V_A = A_1 \cup A_2 \cup \lbrace t_{A_1}^i, f_{A_1}^i, u_{A_1}^i \mid 1 \le i \le \log _2 k\rbrace  \cup \lbrace t_{A_2}^i, f_{A_2}^i, u_{A_2}^i \mid 1 \le i \le \log _2 k\rbrace \)  and \(V_B\)  is the set of remaining vertices.
Basically, the vertices in left half of fig:Bachrach-MDS-lb-graph are assigned to \(V_A\)  and those in the right half are assigned to \(V_B\) .
Now consider two players Alice and Bob and suppose \(V_A\)  (and incident edges) are provided to Alice and \(V_B\)  and incident edges are provided
to Bob. Bachrach et al. [1]} show that the construction of \(G_{x, y}\)  is such that \(G_{x, y}\)  has a dominating set of size at most \(4\log _2 k + 2\)  iff
\(DISJ_{k^{2}}(x,y) = \mathrm {false}\)  for the bit vectors \(x\)  and \(y\) . Since the two-party communication complexity of set disjointness for bit vectors of size \(k^2\)  is
\(\Omega (k^2)\) , Alice and Bob need to communicate \(\Omega (k^2)\)  bits to determine if \(G_{x, y}\)  has a dominating set of size at most \(4\log _2 k + 2\) .
The number of edges in the cut between Alice and Bob is \(O(\log k)\) , implying that if our goal was to determine if \(G_{x, y}\)  has a
dominating set of size at most \(4\log _2 k + 2\)  in the \(\mathsf {CONGEST}\)  model, then \(\Omega (k^2)\)  bits would have to flow over \(O(\log k)\)  edges,
leading to a \(\tilde{\Omega }(k^2)\)  lower bound on the number of rounds.
