Recitation 9

Recitation notes for the week of October 22, 2025.

HW 5, Question 1

The HW 5 webpage has the detailed description of the problem. Here, we just give a summary:

Overview of the problem

We want to compute the intersection of $n$ sets in a distributed manner. We are given a graph $G=(V,E)$, where each node $u\in V$ gets a set $S_u\subseteq [M]$. In particular, the set is represented as a binary array $A_u$. There is a pre-designated special node $t$, which, at the end of the protocol, must compute the intersection of all the $n$ sets. In this problem, we do not care about the runtime but the total cost of communication (where sending one bit over an edge $e\in E$ incurs a cost of $c_e$).

We will talk about the problem in terms of examples.

Example 1

In this case, $G$ is the following graph:

In the above graph, an MST is shown with the green edges.

The input sets are defined as follows (note $n=3$ and $M=5$): \[S_u=\{1,2,5\},\] \[S_v=\{2,4\},\] \[S_t=\{2,3,5\}.\] The corresponding array representation will be \[A_u =[1,1,0,0,1],\] \[A_v =[0,1,0,1,0],\] \[A_t =[0,1,1,0,1],\]

Note that at the end, $t$ needs to know \[\{1,2,5\} \cap \{2,4\} \cap \{2,3,5\} =\{2\}\] or equivalently, \[B~~ =[0,1,0,0,0].\]

Here is a simple protocol: $u$ and $v$ send their input $A_u$ and $A_v$ to the node $t$ (on the edges $(u,t)$ and $(v,t)$) respectively. At that point $t$ has all the three sets and can compute the output $B$ without any further communication.

Note

Communication cost of the above protocol is $1\cdot 5 +1\cdot 5 =2\cdot 5=10$.

Example 2

In this case $G$ is the following graph:

In the above graph, an MST is shown with the green edges.

Consider the case when all the input sets are exactly the same as in Example 1. Thus, node $t$ needs to output $\{2\}$ (or equivalently $[0,1,0,0,0]$ as before). Further, the same protocol outlined in Example 1 works as is in this case.

Note

Communication cost of the protocol from Example 1 is now $1\cdot 5 +2\cdot 5 =3\cdot 5=15$.

Example 3

In this case, $G$ is the following graph:

In the above graph, an MST is shown with the green edges.

Consider the case when all the input sets $S_t,S_u,S_v$ are exactly the same as in Example 1. But we have another set now \[S_w=\{3,4,5\} \text{ or equivalently } A_w=[0,0,1,1,1].\] Thus, node $t$ needs to output $\emptyset$ (or equivalently $[0,0,0,0,0]$).

Here is the natural generalization of protocol for Example 1 for this case. As in the protocol for Example 1, $u$ and $v$ send their inputs to $t$. Now, in addition $w$ sends its input $A_w$ to $t$ via the edge $(w,t)$.

Note

Communication cost of the above protocol is $1\cdot 5 +2\cdot 5 +10\cdot 5 =13\cdot 5=65$.

Some important clarifications on what the algorithm can do and what it cannot do

Part (a)

We start by recalling the problem statement of part (a):

The problem

You will argue part (b) for two special cases of $G$:

  1. Show that when $G$ is a complete graph on $n$ vertices (i.e. $G=([n],E)$ where $E=\{(i,j)|i<j\in [n]\}$) and $c_e=1$ for every $e\in E$, there is a protocol whose worst-case communication cost over all inputs over the universe $[M]$ is $O(n\cdot M)$.
  2. Show that when $G$ is a star graph on $n$ vertices with $t$ as its center (i.e. $G=([n],E)$ where $E=\{(t,j)|j\neq t\in [n]\}$) and $c_e=1$ for every $e\in E$, there is a protocol whose worst-case communication cost over all inputs over the universe $[M]$ is $O(n\cdot M)$.

Note

We would like to point out two things:

  1. Since for both the complete graph and star graph above, we have $MST(G)=n-1$, the bound of $O(n\cdot M)$ in both sub-parts is indeed $O(MST(G)\cdot n)$ for the special case of $G$.
  2. Note that your protocols for part (a) above can use the special structure of the complete graph while your algorithm for part (b) should work for any network topology $G$.

Algorithm Idea Part 1

Every $u\in V\setminus\{t\}$ sends all of its $A_u$ to t via the edge $(u,t)$. Then t computes the final output (since it has $Au$ for every $u∈V$). Note that when this is specialized to $n=3$, this algorithm/protocol reduces to the ones stated in Example 1. Note that $t$ has $A_u$ and $A_v$ from from the nodes $u$ and $v$ and then all $t$ has to do is loop every entry in $A_u, A_v$ and $A_t$ to construct the required output $B$.

Algorithm Detail Part 1

Even though this is not needed for your HW submission, we write down the details, so that it helpful for part (b).

                                    //This code is run at each node u in V

                                    if u!= t:
                                        Send Au to t via the edge (u,t)
                                        return #At this point this node does not do anything else and basically terminates
                                    else: # The rest of the code is just for t

                                        B = At

                                        while t has not received an array from all u!=t:
                                            t receives array C from u #This is triggered when node t receives C=Au from u

                                            for i = 1 to M:
                                                B[i] = B[i] and C[i]

                                        #At this point has received arrays from all other nodes u
                                        return B #This is the final output

Bounding Communication cost

The only communication happens in line 4 of the algorithm above. Further, this communication leads to sending $M$ bits from every vertex $u\neq t$ to $t$, incurs cost $1\cdot M=M$ (this is where we use the fact that $c_e=1$ for every $e$). Since there are $n-1$ vertices $u\neq t$, we have that the overall communication cost of $(n-1)\cdot M$, which is $O(nM)$, as desired.

Hint for part 2

The algorithm needed for part 2 (Star Case) is very similar to the algorithm used for part 1.

Part (b)

The problem you need to solve

Design an algorithm whose worst-case communication cost over all inputs over the universe $[M]$ is $O(MST(G)\cdot M)$, where $MST(G)$ is the cost of an MST on $G$ (i.e. it is the sum of costs of all edges in the MST). Note that the algorithm gets both $G$ (along with its edge costs) and the arrays $A_u$ for every $u\in V$ as input. Note that the algorithm is only provided $G$ as input-- if it needs to know something about the graph $G$, then it needs to compute it by itself. You should assume that $G$ is connected.

We do not have to add beyond what we said in part (a) except:

Some clarifications

Some clarifications on what the algorithm can and cannot do:

  • Your algorithm can use the knowledge of $G$ to build a protocol: i.e. the sequence of bits that should be exchanged over any edge (and when to send those bits) but it has to work for any connected $G$. Note that this means you can do whatever pre-processing you want on $G$: no restriction on time complexity.
  • Once the protocol is built, the rest of the computation happens in a distributed manner. In other words any point of time and any node $u$, what bit(s) $u$ sends over an edge $(u,v)\in E$ depends only on $A_u$ and all the bits that $u$ has received till this point of time. (Again, how to compute the bits to be sent over is determined by the protocol.)
  • At the end of the run of the protocol, the node $t$ has to output the final answer $B$ only based on $A_t$ and all the bits it has received from its neighbors over the entire run of the protocol.

HW 5, Question 2

The problem you need to solve

In this problem, we will consider the special case of MST where there are only two possible edge costs. In particular, the input to the problem is an undirected connected graph $G=(V,E)$ where every edge cost satisfies $c_e\in \{5,10\}$ (i.e. the edge costs are either $5$ or $10$ and no other value). Present an $O(m+n)$ time algorithm to compute an MST of such graphs.

Note

The above run time is better than any known MST algorithm for the general cost case. Thus, your algorithm really needs to exploit the fact that there are only two edge costs.

Part (a)

The problem you need to solve

Present an $O(m+n)$ time algorithm to compute an MST for the special case where all edge weights $c_e=5$ (i.e. all the edge weights are the same).

Algorithm Idea

The algorithm is fairly obvious once we make the following observation (recall that a spanning tree for a graph $G=(V,E)$ is a sub-graph $T=(V,E')$ (i.e. $E'\subseteq E$) such that $T$ is a tree):

Lemma 1

Let $T$ be any spanning tree of a graph $G$ with all edge weights $5$. Then the cost of $T$ is given by: \[c(T)=5(n-1).\]

As we will argue in the proof idea, the above means that any spanning tree is an MST. So then the algorithm idea is simple: just run BFS algorithm (say the version on Pg. 90 in the textbook)-- while ignoring the edge weights-- and return the computed BFS tree.

Proof Idea

Given Lemma 1 above, the rest of the argument is fairly straightforward. Since every spanning tree has the same cost and since the BFS tree is also a spanning tree (note that BFS tree will be a spanning tree since $G$ is connected), it will have the same cost as an MST (which is also a spanning tree). Hence, a BFS tree is also an MST.

You still need to argue Lemma 1

Note that in your submission (if you are using the recitation notes solution), you have to argue why Lemma 1 is true.

Runtime analysis

The algorithm just runs BFS, which we have seen in class runs in $O(m+n)$ time and hence, our algorithm also runs in $O(m+n)$ time, as desired.

Part (b)

The problem you need to solve

Give an $O(m+n)$ algorithm to compute an MST when all edge weights are in $\{5,10\}$.

Hint

It might be useful to start from the algorithm from part (a) and then try to extend the algorithm to the current two cost scenario. In the solution that I have in mind, the proof of correctness of the algorithm goes via the proof of correctness of Kruskal's algorithm. As usual, there can be more than one way of solving a problem, so feel free to ignore the hint if you have another way to solve the problem.

Boruvka’s Algorithm

This is another algorithm to find the minimum spanning tree for a graph with distinct edge weights (none of the edges have the same value).

Algorithm Idea

The goal of the algorithm is to connect "components" using the shortest edge between components. It begins with all of the vertices considered as separate components and then continues till there is one connected component left (which can be proven is an MST).

Next we present the Algorithm Details, courtesy of Wikipedia .

Algorithm Details


                            //Input: A connected graph G whose edges have distinct weights

                            Initialize a forest T to be a set of one-vertex trees, one for each vertex of the graph.

                            while T has more than one component:
                                for each component C of T:
                                    Let S be an empty set of edges
                                    for each vertex v in C:
                                        Find the cheapest edge from v to a vertex outside of C, and add it to S
                                    Add the cheapest edge in S to T
                                Combine trees connected by edges to form bigger components

                            return T // The set of edges in T forms the MST of G

Note

An edge can be selected twice (by two different components). This is fine.

Example 4

We consider the run of the Algorithm on the following graph:

  1. Initially all the vertices themselves form their own component.
  2. In the first iteration of the while loop, all the red edges are picked and added to T:
    .
  3. In the second iteration of the while loop, all the green edges are picked and added to T:
    .
  4. At this point, we are done.

There are two more examples on the Wikipedia page .

Complexity

Note that the while loop will halve the number of components each time. We start with $n$ components (the number of vertices), so the while loop runs at most $\log{n}$ times. In each iteration of the loop, we look through the edges, taking $O(m)$ time. Thus, overall we have $O(m \log{n} )$ time.

Correctness

Proof Idea

As in class we consider the case when all the edge costs are distinct. Then note that the algorithm in each iteration of the while loop, add the cheapest crossing edge for the cut $(C,V\setminus C)$ for every (non-empty) component $C$. Thus, by the cut property lemma, this is a "safe" choice.

After each addition of an edge, the algorithm creates a forest in the original graph. As, we just argued, this forest does not have any edges that would not be in all MSTs. Finally, the algorithm runs until there is only one component. A forest with one component is a tree.