Source-linked AI summary
Adding a referee to an interconnection network: What can(not) be computed in one round
Florent Becker, Martín Matamala, Nicolas Nisse, Ivan Rapaport, Karol Suchan, Ioan Todinca
TL;DR
The paper asks which network properties a referee can compute from one round of small messages based on local neighborhood information. It analyzes this frugal referee model, showing that bounded-degeneracy graphs can be reconstructed while several basic properties of arbitrary graphs cannot be decided.
Problem
The paper asks which network-topology properties can be computed when each node contributes only a small amount of local information to a referee.
Source: §1 · p. 2Method
The paper studies one-round protocols in which nodes send O(log n)-bit messages based on their neighborhoods and a referee computes from the messages.
Source: §1 · p. 2Results
The referee can reconstruct graphs of bounded degeneracy, but no one-round protocol decides whether an arbitrary graph contains a square or triangle or has diameter at most 3.
Source: §1.1 · p. 2Takeaways & Limitations
The results establish that this model can recover bounded-degeneracy topologies yet cannot decide several basic properties of arbitrary graphs.
Source: §1.1 · p. 2, §4 · p. 12Whether a one-round frugal protocol can decide connectivity remains open, as does whether allowing more rounds enables additional decisions.
Source: §1.1 · p. 2, §4 · p. 12
Abstract
from arXiv · showhide
In this paper we ask which properties of a distributed network can be computed from a little amount of local information provided by its nodes. The distributed model we consider is a restriction of the classical CONGEST (distributed) model and it is close to the simultaneous messages (communication complexity) model defined by Babai, Kimmel and Lokam. More precisely, each of these n nodes -which only knows its own ID and the IDs of its neighbors- is allowed to send a message of O(log n) bits to some central entity, called the referee. Is it possible for the referee to decide some basic structural properties of the network topology G? We show that simple questions like, "does G contain a square?", "does G contain a triangle?" or "Is the diameter of G at most 3? cannot be solved in general. On the other hand, the referee can decode the messages in order to have full knowledge of G when G belongs to many graph classes such as planar graphs, bounded treewidth graphs and, more generally, bounded degeneracy graphs. We leave open questions related to the connectivity of arbitrary graphs.
1 Introduction
The paper studies what a referee can compute from one round of small messages sent by nodes with local neighborhood knowledge. It proposes this model, establishes both reconstruction and decision limits, and identifies open questions.
1.3 Related Work
- The paper situates its model alongside CONGEST and frugal computation, and contrasts it with LOCAL, which permits unbounded messages to focus on locality.Prior work cited in the introduction shows frugal evaluation of first-order logic on planar or bounded-degree networks.Source: §1 · pp. 1–2
1.1 Our results
- For every fixed k, a one-round protocol can reconstruct graphs of degeneracy k or report that their degeneracy exceeds k, covering forests, planar graphs, and bounded-treewidth graphs.The paper notes that forests have degeneracy 1, planar graphs have degeneracy 5, and degeneracy is bounded above by treewidth.Source: §1.1 · p. 2
- No one-round protocol can decide whether an arbitrary graph contains a square or triangle, or compute whether its diameter is at most 3.Source: §1.1 · p. 2
- Whether one-round protocols can decide connectivity, and whether more rounds enable additional decisions, remain open questions.Source: §1.1 · p. 2
1.2 The model
- The model gives each node one O(log n)-bit message to a referee, which uses the n messages to solve a problem without knowing the network topology.Nodes know their own identifiers and neighbors’ identifiers; the referee knows the network size.Source: §1 · p. 2, §1.2 · p. 3
2 Hard local properties
The section proves that one-round frugal protocols cannot decide whether an arbitrary graph contains a square or triangle, or has diameter at most 3. Its reductions turn such tests into graph reconstruction, which exceeds the information available in one round.
2 Hard local properties
- Any graph family reconstructible by a one-round frugal protocol has at most 2^O(n log n) graphs on n vertices.This counting bound underlies the impossibility arguments: the reductions construct families larger than the bound.Source: §2 · pp. 4–5
2.1 Finding a square in one round is hard
- A one-round frugal protocol cannot detect square subgraphs or induced squares in arbitrary graphs.A square detector would enable reconstruction of square-free graphs, whose count, 2^Theta(n^1.5), exceeds the 2^O(n log n) bound for reconstructible graph families.Source: §2 · p. 4, §2.1 · p. 5
2.2 Computing diameter in one round is hard
- A one-round frugal protocol cannot decide whether an arbitrary graph has diameter at most 3.The reduction encodes each tested edge as the diameter of an auxiliary graph, so such a protocol would reconstruct arbitrary graphs.Source: §2.2 · p. 6
2.3 Finding a triangle in one round is hard
- A one-round frugal protocol cannot detect triangles in arbitrary graphs.The reduction uses triangle tests to reconstruct bipartite graphs by testing whether each vertex pair is an edge.Source: §2.3 · pp. 6, 8
- The reductions preserve frugality with message sizes k(2n) for square detection and 3k(n + 3) for long-distance detection.The paper also states that the resulting protocols' local time complexities are polynomially bounded in those of the original protocols.Source: §2.3 · p. 8
3 Reconstruction of graphs of bounded degeneracy
The section presents a one-round frugal protocol that reconstructs graphs of bounded degeneracy, with the referee discovering an elimination order from local messages.
3.1 Case of forests (k = 1)
- For forests, each vertex sends its ID, degree, and the sum of neighbor IDs; the referee repeatedly prunes a leaf to reconstruct the forest or detect a cycle.A leaf’s neighbor ID can be recovered from the sum, allowing the referee to update that neighbor’s information as it removes the leaf.Source: §3.1 · p. 9
3.2 Generalization for any k ≥1
- For degeneracy at most k, each vertex sends its ID, degree, and the first k power sums of neighbor IDs, enabling iterative removal of vertices of degree at most k.Vertices know k, but the elimination order is discovered during the referee’s calculations rather than known in advance.Source: §3.2 · pp. 9–10
3.3 Neighborhood encoding
- Neighborhood encoding multiplies a vertex’s neighborhood incidence vector by A(k, n), producing a message of O(k^2 log n) bits computable in O(n) local time.The message also includes the vertex ID and degree.Source: §3.3 · p. 10
3.4 Neighborhood decoding
- A uniqueness result lets the referee recover a neighborhood from its encoded vector; iterative decoding then reconstructs bounded-degeneracy graphs in one round.The protocol can also recognize graphs of degeneracy at most k, and bounded-degeneracy classes include planar graphs, bounded-treewidth graphs, and H-minor-free graphs.Source: §3.4 · pp. 11–12
- A preprocessing table can map encoded vectors to neighborhoods, supporting O(log n) neighborhood lookup and O(n^2) graph reconstruction time.The table is built by enumerating k-subsets and storing their encoded vectors.Source: §3.4 · p. 11
4 Conclusion and open questions
The paper contrasts one-round reconstruction of bounded-degeneracy graphs with the inability to decide several simple properties of arbitrary graphs. Connectivity remains open, alongside questions about bipartiteness and protocols with more rounds.
4 Conclusion and open questions
- One-round protocols can reconstruct bounded-degeneracy topologies, yet cannot decide whether an arbitrary graph contains a triangle or has diameter at most three.The hardness results cover both local properties, such as triangles, and global properties, such as diameter.Source: §4 · p. 12
- Whether a one-round frugal protocol can decide connectivity remains open; the paper’s fixed-partition hardness technique does not apply to this problem.When vertices within each of k parts can communicate, connectivity can be decided using O(k log n) bits per node.Source: §4 · p. 12
- A one-round frugal protocol for bipartiteness would imply one for connectivity on bipartite graphs.The authors also identify deciding more properties by allowing more rounds as an open question.Source: §4 · p. 12
- The authors propose studying complete problems for complexity classes defined by limits on local and global computation.They describe their reduction technique as a promising tool for this research.Source: §4 · p. 12