\[\text{KT-1 CONGEST model: one algorithm using } \tilde{O}(n) \text{ messages, but an exponential number of rounds, solves any graph problem}\]
  1. KKT algorithm builds a spanning tree \(T\) in \(\tilde{O}(n)\) rounds and messages.
  2. Elect a leader on the spanning tree using \(\tilde{O}(n)\) messages. Subsequently, the leader \(u_{*}\) servers as the root of the spanning tree \(T\) and every node knows its distance in \(T\) from \(u_*\) .
  3. Assuming an ID range of size \(n^c\), there are at most \(t=2^{n \choose 2}(n!){n^c \choose n}\) possible \(n\)-node graphs where a subset of \(n\) IDs is chosen and assigned to the nodes by selecting one of the possible \(n!\) permutations. Note: with this ID range of size, we can build this many \(t\) distinct graphs.
  4. Let \(E\) be some arbitrary enumeration of the set of permutations and let \(E_{i}\) refer to the \(i\)-th item in the order stipulated by \(E\). Then do convergecast with the following in \(d\) iterations and \(t\) rounds per iteration, where \(d\) is the maximum distance of a node from the root \(u_{*}\) in \(T\). Note: \(d\) can be known by all nodes in \(O(D)\) additional rounds.
    1. In the 1st iteration, each leaf at distance \(d\) sends exactly 1 bit to its parent in round \(k\) if its local neighborhood corresponds to \(E_k\). Note: In each iteration, there are \(t\) rounds, in each round, we check the respective graph (there are \(t\) such graphs as 3 said). Note that all the graphs topology are known to all nodes in advance. That is, from round 1, we check \(E_{1}\), round 2, check \(E_2\), …, round \(t\), we check \(E_{t}\). When check, the active node checks if its neighborhood is the same as the current graph, if yes, then send 1 bit to its parent. Then the parent will decode the child’s neighborhood by the current graph.
    2. Similarly, in iteration \(i>1\), every node \(u\) at distance \(d-i+1\), sends 1 bit in round \(k'\) such that \(E_{k'}\) corresponds to the subgraph consisting of \(u\)’s neighborhood as well as the topology information received from its children in the previous iterations.
      -Proceeding in this manner ensures that a node can convey its current knowledge of the network topology to its parent by sending only a single bit during one of the rounds in this iteration while remaining silent in all others.
    3. After \(d\) iterations, the entire topological information is received by the root \(u_*\), and this information again corresponds to some \(E_{k''}\).
    4. Subsequently, we use another \(d\) iterations, each consisting of \(t\) rounds, to disseminate \(E_{k''}\) starting from \(u_*\) to all nodes in the network, and this can be down by sending only \(O(n)\) messages in total.
    5. Finally, each node locally computes its output from \(E_{k''}\) according to the solution to problem \(P\).