# Find connected components in a graph of computer network with parallel pairwise tests

I have N nodes, a node might have an undirected edge to other nodes, resulting in K connected components (K<=N, K unknown).
I can test if a given pair is connected. In each step in time, I can run N/2 such tests in parallel (a given node can be tested once per step). Each connected component is a cluster graph (it has no three-vertex induced path). The goal is to find all K components and list of nodes per component.

The actual application is nodes in a computer network, therefore I can run pairwise tests in parallel. I have ~256 nodes. How to approach this? A naive solution of N*(N-1)/2 tests is too costly. Hopefully I could reuse a library algorithm in Python a solution.

For example for detecting the graph below (7 nodes, 3 connected-components (CC)), I might need this set of tests:

Step1 tests: D-A, C-F, E-B
Step2 tests: A-B, C-B, D-E (found CC: A-B-C)
Step3 tests: D-F (Found CC: D)
Step4 tests: E-F (Found CC: E-F)
Done.


• Do you have any way to list the neighbors of an edge or do anything than test if a given pair of nodes are connected? If not, the best you can do is about N steps where in each step you test N/2 pairs, as you'll need to test essentially every possible pair.
– D.W.
Commented Jan 11, 2023 at 9:18
• I can test if a given pair is connected. In each step in time, I can run N/2 such tests (a node can be tested once per step). Commented Jan 11, 2023 at 12:53

The best you can do is about $$N$$ steps.
You can do it in about $$N$$ steps, by just testing $$N/2$$ new pairs in each step, until you've tested all pairs. Then once you have tested all pairs, you can use any standard algorithm to compute connected components (e.g., depth-first search).
You can't do better. In the worst case, you have to inspect essentially every pair of nodes, so you'll need to have inspected about $$N^2/2$$ pairs. (If there is even a single pair $$u,v$$ that you haven't inspected, where there is no other path of length $$>1$$ from $$u$$ to $$v$$, then you can't tell whether $$u,v$$ are in the same component or not without querying the $$u,v$$ pair.) Since you can only inspect $$N/2$$ pairs per step, you'll need at least $$N$$ steps.
• @GiliNachum, yup, that's a critical detail. Sounds worth asking as a separate question. I also recommend stating whether you care about constant factors, and listing the best strategy you know. I expect it'll still take $\ge cN$ steps for some constant $c>0$.