Pattern - Hub Nodes

If you have a set of items that are all connected to each other (a clique), adding edges between every pair is $O(k^2)$ for $k$ items. Too slow for large cliques.

Instead, create a virtual "hub" node. Connect every item to the hub. Now you have $k$ edges instead of $k^2$. Items in the same clique share the hub as their leader.

This pattern appears when problems have large groups that must be unified.

Space complexity is $O(n)$ for the data structures used.