How local constraints influence network diameter and applications to LCL generalizations

Laurent Feuilloley; Nicolas Bousquet; Th\'eo Pierron

How local constraints influence network diameter and applications to LCL generalizations

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2409.01305 v1 pith:7EUT7CYE submitted 2024-09-02 cs.DC

Nicolas Bousquet , Laurent Feuilloley , Théo Pierron This is my paper · ORCID

classification cs.DC

keywords degreediameteremphgraphsinfluencelocalnetworkresults

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

read the original abstract

In this paper, we investigate how local rules enforced at every node can influence the topology of a network. More precisely, we establish several results on the diameter of trees as a function of the number of nodes, as listed below. These results have important consequences on the landscape of locally checkable labelings (LCL) on \emph{unbounded} degree graphs, a case in which our lack of knowledge is in striking contrast with that of \emph{bounded degree graphs}, that has been intensively studied recently. [See paper for full abstract.]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

New Complexity Classes in Locally Checkable Labeling for Local Computation Algorithms
cs.DC 2026-07 accept novelty 7.0 of 10

Stacking of Rosenbaum–Suomela base LCLs yields LCLs of randomized VOLUME/LCA probe complexity Θ(log^k n) and ˜Θ(n^{p/q}) on bounded-degree graphs and trees.

Pith tools