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 measuresexpand

\(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.

Progress map

tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Time

Memory

No assumptions

—

Triangle counting + static graph, + undirected, + distinct IDs (eponymous), + local communication, + synchronous

0 open · 1 results

unknown \(O(n\log^2 n + \Delta\log L)\) vs —

unknown \(O(\Delta\log L)\) vs —

Butterfly counting in bipartite graphs + dispersed start, + bipartite

0 open · 1 results

unknown \(O(n\log L + \Delta)\) vs —

unknown \(O(\Delta\log L)\) vs —

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