Mobility Matters
Home›Mobile agents on graphs›Computing with agents›Triangle and butterfly counting by agents

Triangle and butterfly counting by agents

\(n\) agents in an anonymous graph must count small subgraphs (triangles; butterflies in bipartite graphs) at every node.

Problem statement and measurescollapse
1011011011011011011011011011011011011011011011011011011011011011011011011110110111101101111101101111101101111101101111111112233Start: dispersed; IDs written in 2 bitsPass 1, block 1: 2, 3 visit; record IDsPass 1, block 2: 1, 3 visit; record IDsPass 2, block 1: 2, 3 visit; compare listsPass 2, block 2: 1, 3 visit; compare listsFinal: (1 + 1) / 2 = 1 triangle at every node
Triangle counting Chand et al. 2026 on a triangle: after dispersing (one agent per node), electing a leader and learning \(\Delta\) (not shown), the agents write their IDs in 2 bits and follow the ID-bit schedule: in block \(i\) (of \(2\Delta = 4\) rounds) agents whose \(i\)-th bit is 1 visit each neighbour and come back, one edge per round, while the others wait at home. In the first pass a visit to a waiting neighbour records both IDs (green edges); in the second pass, round by round with the same walks, the two ends of each edge count the IDs on both lists (blue numbers). Each agent adds its edges' counts and halves the sum: the number of triangles at its node.

\(n\) agents with distinct identifiers (IDs) are placed on the nodes of an anonymous port-labelled graph with \(n\) nodes, \(m\) edges and maximum degree \(\Delta\). The start is rooted (all agents on one node), dispersed (one agent on each node) or arbitrary. Agents compute only by moving and by talking with agents on the same node. The agents must compute, at every node, the number of triangles (or butterflies) it belongs to: every agent (or node) learns its part of the output. Time is in synchronous rounds; memory in bits per agent.

Measures: Time, rounds; Memory, bits per agent.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine \(n\) agents (small mobile computers), one in each room of a building, who want to know how tightly the rooms are connected: for each room, how many pairs of the rooms next to it are also next to each other. The building is a graph: rooms are its nodes and corridors are its edges; there are \(n\) nodes and \(m\) edges, and from here on we say only node and edge. Two nodes joined by an edge are neighbours. The degree of a node is the number of edges at it, and \(\Delta\) is the maximum degree. Nodes have no names, but the edges at a node are numbered \(1, 2, \dots\); these numbers are ports. A triangle is three nodes all joined to each other. Agents have distinct identifiers (IDs) between \(1\) and \(L\), can talk only to agents on the same node, and move in synchronous rounds (in each round: talk, then move along at most one edge). For the basic version the agents start anywhere and know nothing about the graph; at the end the agent on each node \(v\) must know the number of triangles containing \(v\). We count rounds and bits of memory per agent. Like all problems in this family, the work starts by making the agents dispersed (one agent on each node, which becomes the agent's home) and letting neighbouring agents meet, the method explained under leader election by agents.

1AlgorithmLearn your neighbours, then compare lists Triangle counting → Chand et al. 2026
  1. Get organised. The agents disperse (one per node), elect a leader and build a spanning tree, learning \(\Delta\) on the way.
  2. Meet your neighbours. Write IDs with \(\log L\) bits and follow the ID-bit schedule: in block \(i\) (of \(2\Delta\) rounds), agents whose \(i\)-th bit is \(1\) visit their neighbours one by one, and agents whose bit is \(0\) stay at home. Every pair of neighbouring agents meets in some block, and each agent writes down the IDs of all its neighbours.
  3. Compare lists. Repeat the meetings. When the agents on neighbouring nodes \(v\) and \(u\) meet, they count the IDs that appear on both lists: that is the number of triangles that contain the edge \(\{v, u\}\).
  4. Add up. The agent on \(v\) adds these counts over all its neighbours and divides by 2: each triangle \(\{v, u, w\}\) was counted once through \(u\) and once through \(w\).
Why it works and what it costs. Step 2 and step 3 each take \(\log L\) blocks of \(2\Delta\) rounds, i.e. \(O(\Delta\log L)\) rounds, and each agent stores up to \(\Delta\) IDs, i.e. \(O(\Delta\log L)\) bits. Step 1 costs \(O(n\log^2 n)\) rounds, and it dominates the total \(O(n\log^2 n + \Delta\log L)\) Chand et al. 2026. The same counts per edge give truss decomposition and local clustering coefficients. No lower bound is proved.

Why it matters. It shows that once agents are organised, local graph statistics cost only \(O(\Delta\log L)\) rounds, so the bottleneck is getting organised, not counting.

2Lower boundThe total count needs information from both ends of the graph Triangle counting →

Besides the per-node counts, the algorithm also lets the agents learn the total number of triangles. Information moves at most one edge per round, because it travels only inside agents and an agent moves along at most one edge per round. So after \(t\) rounds, what an agent standing on node \(y\) knows depends only on the part of the graph within distance \(t\) of \(y\). Take a long path and, at each end, attach two extra nodes \(a\) and \(b\) to the end node; adding the edge \(\{a, b\}\) closes a triangle. If an agent announces the total after fewer than about \(D/2\) rounds, where \(D\) is the diameter (largest distance between two nodes), one end lies outside what it can know about. Adding or removing the edge \(\{a, b\}\) there changes the true total but not what this agent knows, so in one of the two graphs its answer is wrong.

Why it holds. So computing the total needs \(\Omega(D)\) rounds. This is our own short argument, not a result recorded in the catalogue; the known algorithm needs \(O(n + \Delta\log L)\) rounds for the total after the set-up, and on a path \(D\) is about \(n\), so it is optimal there up to a constant factor. For the per-node counts this argument gives nothing, because they depend only on nearby nodes.

Why it matters. This "information moves one edge per round" argument is the simplest lower-bound tool for agents, and it separates local tasks (per-node counts) from global ones (totals).

3AlgorithmBipartite graphs: one side walks while the other waits Butterfly counting in bipartite graphs → Chand et al. 2025

In a bipartite graph the nodes split into two sides \(V_1\) and \(V_2\) and every edge joins the two sides. A butterfly is a 4-cycle: two nodes \(a, a'\) on one side with two common neighbours on the other.

  1. The agents, starting dispersed (one per node), elect a leader, build a spanning tree and learn which side they are on.
  2. In odd rounds the agents on one side visit their neighbours while the other side waits at home; in even rounds the roles swap. Within \(2\Delta\) rounds every agent knows its neighbours' IDs.
  3. The agent on \(a\) visits its neighbours again and reads their lists, so it learns, for every \(a'\) on its side, the number \(c\) of common neighbours of \(a\) and \(a'\).
  4. Each such pair lies on \(\binom{c}{2}\) butterflies (choose two of the common neighbours); summing over \(a'\) gives the number of butterflies through \(a\).
Why it works and what it costs. Because the two sides take turns, no ID-bit schedule is needed: neighbours meet within \(2\Delta\) rounds rather than \(O(\Delta\log L)\), and the per-node counts take \(O(\Delta)\) rounds. The set-up takes \(O(n\log L)\) rounds, for a total of \(O(n\log L + \Delta)\) rounds with \(O(\Delta\log L)\) bits per agent Chand et al. 2025.

Why it matters. Knowing more structure (here, a 2-colouring of the graph) can remove the \(\log L\) cost of making neighbours meet.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Memory
Triangle counting standard
From an arbitrary placement and without prior knowledge, agents count triangles per node and per edge, which yields truss decomposition, triangle centrality and local clustering coefficients.
unknown \(O(n\log^2 n + \Delta\log L)\) vs —
unknown \(O(\Delta\log L)\) vs —
Butterfly counting in bipartite graphs
In a bipartite graph, agents starting dispersed count butterflies (\(K_{2,2}\)) per node in \(O(n\log L + \Delta)\) rounds.
unknown \(O(n\log L + \Delta)\) vs —
unknown \(O(\Delta\log L)\) vs —

What the community started looking at

Counting problems extend agent-based computing from symmetry breaking to graph analytics: triangle counting and its applications Chand et al. 2026, and butterfly counting in bipartite graphs Chand et al. 2025.

Perspectives

  • From exploration to dispersion, and beyond How collaborative exploration asks how much a team speeds up a search, how dispersion arose as the case k = n under weaker assumptions, what dispersion gives back to exploration, and why dispersing first has become the standard opening move for computing graph structures with agents.

All settings

The assumption tree (2 settings, 1 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Memory); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Identifiers › Communication › Timing › Knowledge › Initial configuration › Topology.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Knowledge

0no knowledge of graph parameters1\(n\) and \(\Delta\) are known

Whether agents know global parameters is inherited from message passing, where nodes typically know \(n\) or an upper bound on it, and possibly \(\Delta\) and \(D\); Kshemkalyani, Kumar, Molla and Sharma set the agent-based model against this and asked for algorithms that rely on no such knowledge, "neither exact nor an upper bound" Kshemkalyani et al. 2024. Knowing \(n\) and \(\Delta\) tells an agent how long to wait: in the arbitrary-start minimal dominating set algorithm of Chand, Molla and Sivasubramaniam every robot waits \(\kappa n\Delta\) rounds before leader election begins Chand et al. 2023, and the introductory maximal independent set algorithm assumes both \(n\) and \(\Delta\) Pattanayak et al. 2024 (as reported by Kaur et al. 2026 and Kshemkalyani et al. 2024). Kshemkalyani et al. state the trade-off: solutions without knowledge "are more resilient to network changes and device faults", but "algorithm design becomes challenging since devices may not know how long to run a procedure to guarantee a solution" Kshemkalyani et al. 2024. Later papers remove the assumption by first dispersing with termination detection and electing a leader, after which a spanning tree lets the agents compute \(\Delta\) and the largest identifier themselves Chand et al. 2026; knowing only that largest identifier \(L\) is a weaker assumption, recorded on results rather than as a level of this axis Chand et al. 2025. For triangle counting, Chand, Das and Molla remove the need to know \(\Delta\) in exactly this way Chand et al. 2026; their butterfly counting still assumes \(L\) Chand et al. 2025.

Formal definitions
0no knowledge
Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
1knows \(n\), \(\Delta\)
Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.