Proving there is a leader without naming it Article Swipe
Local certification is a mechanism for certifying to the nodes of a network that a certain property holds. In this framework, nodes are assigned labels, called certificates, which are supposed to prove that the property holds. The nodes then communicate with their neighbors to verify the correctness of these certificates. Certifying that there is a unique leader in a network is one of the most classical problems in this setting. It is well-known that this can be done using certificates that encode node identifiers and distances in the graph. These require $O(\log n)$ and $O(\log D)$ bits respectively, where $n$ is the number of nodes and $D$ is the diameter. A matching lower bound is known in cycle graphs (where $n$ and $D$ are equal up to multiplicative constants). A recent line of work has shown that network structure greatly influences local certification. For example, certifying that a network does not contain triangles takes $Θ(n)$ bits in general graphs, but only $O(\log n)$ bits in graphs of bounded treewidth. This observation raises the question: Is it possible to achieve sublogarithmic leader certification in graph classes that do not contain cycle graphs? And since in that case we cannot write identifiers in a certificate, do we actually need identifiers at all in such topologies? [We answer these questions with results on small diameter graphs, chordal graphs, grids, and dense graphs. See full abstract in the paper.]
Related Topics
Concepts
No concepts available.
Metadata
- Type
- preprint
- Landing Page
- http://arxiv.org/abs/2511.15491
- https://arxiv.org/pdf/2511.15491
- OA Status
- green
- OpenAlex ID
- https://openalex.org/W4416763390
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4416763390Canonical identifier for this work in OpenAlex
- Title
-
Proving there is a leader without naming itWork title
- Type
-
preprintOpenAlex work type
- Publication year
-
2025Year of publication
- Publication date
-
2025-11-19Full publication date if available
- Authors
-
Laurent Feuilloley, Josef SedláčekList of authors in order
- Landing page
-
https://arxiv.org/abs/2511.15491Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2511.15491Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2511.15491Direct OA link when available
- Cited by
-
0Total citation count in OpenAlex
Full payload
| id | https://openalex.org/W4416763390 |
|---|---|
| doi | |
| ids.openalex | https://openalex.org/W4416763390 |
| fwci | |
| type | preprint |
| title | Proving there is a leader without naming it |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| language | |
| locations[0].id | pmh:oai:arXiv.org:2511.15491 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2511.15491 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2511.15491 |
| indexed_in | arxiv |
| authorships[0].author.id | https://openalex.org/A5080881555 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-3994-0898 |
| authorships[0].author.display_name | Laurent Feuilloley |
| authorships[0].countries | FR |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I1294671590 |
| authorships[0].affiliations[0].raw_affiliation_string | CNRS - Centre National de la Recherche Scientifique (France) |
| authorships[0].affiliations[1].institution_ids | https://openalex.org/I4210137744 |
| authorships[0].affiliations[1].raw_affiliation_string | GOAL - Graphes, AlgOrithmes et AppLications (France) |
| authorships[0].affiliations[2].institution_ids | https://openalex.org/I4210155607 |
| authorships[0].affiliations[2].raw_affiliation_string | LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information (Bâtiment Blaise Pascal - 20, avenue Albert Einstein - 69621 Villeurbanne cedex - France) |
| authorships[0].institutions[0].id | https://openalex.org/I1294671590 |
| authorships[0].institutions[0].ror | https://ror.org/02feahw73 |
| authorships[0].institutions[0].type | government |
| authorships[0].institutions[0].lineage | https://openalex.org/I1294671590 |
| authorships[0].institutions[0].country_code | FR |
| authorships[0].institutions[0].display_name | Centre National de la Recherche Scientifique |
| authorships[0].institutions[1].id | https://openalex.org/I4210137744 |
| authorships[0].institutions[1].ror | https://ror.org/03eqm6y13 |
| authorships[0].institutions[1].type | facility |
| authorships[0].institutions[1].lineage | https://openalex.org/I106785703, https://openalex.org/I1294671590, https://openalex.org/I1326498283, https://openalex.org/I2738703131, https://openalex.org/I4210137744, https://openalex.org/I4210139971, https://openalex.org/I4210150872, https://openalex.org/I899635006, https://openalex.org/I899635006 |
| authorships[0].institutions[1].country_code | FR |
| authorships[0].institutions[1].display_name | LabEx PERSYVAL-Lab |
| authorships[0].institutions[2].id | https://openalex.org/I4210155607 |
| authorships[0].institutions[2].ror | https://ror.org/04dv4he91 |
| authorships[0].institutions[2].type | facility |
| authorships[0].institutions[2].lineage | https://openalex.org/I100532134, https://openalex.org/I112936343, https://openalex.org/I1294671590, https://openalex.org/I188626449, https://openalex.org/I203339264, https://openalex.org/I4210155607, https://openalex.org/I48430043 |
| authorships[0].institutions[2].country_code | FR |
| authorships[0].institutions[2].display_name | Laboratoire d'Informatique en Images et Systèmes d'Information |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Laurent Feuilloley |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | CNRS - Centre National de la Recherche Scientifique (France), GOAL - Graphes, AlgOrithmes et AppLications (France), LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information (Bâtiment Blaise Pascal - 20, avenue Albert Einstein - 69621 Villeurbanne cedex - France) |
| authorships[1].author.id | https://openalex.org/A5021903373 |
| authorships[1].author.orcid | https://orcid.org/0009-0001-7429-2937 |
| authorships[1].author.display_name | Josef Sedláček |
| authorships[1].countries | CZ |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I44504214 |
| authorships[1].affiliations[0].raw_affiliation_string | CTU - Czech Technical University in Prague (České vysoké učení technické v Praze Zikova 1903/4 166 36 Praha 6 Česká republika - République tchèque) |
| authorships[1].institutions[0].id | https://openalex.org/I44504214 |
| authorships[1].institutions[0].ror | https://ror.org/03kqpb082 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I44504214 |
| authorships[1].institutions[0].country_code | CZ |
| authorships[1].institutions[0].display_name | Czech Technical University in Prague |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Josef Erik Sedláček |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | CTU - Czech Technical University in Prague (České vysoké učení technické v Praze Zikova 1903/4 166 36 Praha 6 Česká republika - République tchèque) |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2511.15491 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-11-23T00:00:00 |
| display_name | Proving there is a leader without naming it |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-29T10:17:25.366124 |
| primary_topic | |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | pmh:oai:arXiv.org:2511.15491 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2511.15491 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2511.15491 |
| primary_location.id | pmh:oai:arXiv.org:2511.15491 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2511.15491 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2511.15491 |
| publication_date | 2025-11-19 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.A | 110, 129 |
| abstract_inverted_index.a | 3, 11, 14, 54, 58, 147, 201 |
| abstract_inverted_index.In | 18 |
| abstract_inverted_index.Is | 174 |
| abstract_inverted_index.It | 70 |
| abstract_inverted_index.at | 208 |
| abstract_inverted_index.be | 76 |
| abstract_inverted_index.do | 186, 203 |
| abstract_inverted_index.in | 57, 67, 86, 116, 156, 164, 182, 193, 200, 210, 232 |
| abstract_inverted_index.is | 2, 53, 60, 71, 100, 107, 114 |
| abstract_inverted_index.it | 175 |
| abstract_inverted_index.of | 10, 47, 62, 103, 132, 166 |
| abstract_inverted_index.on | 219 |
| abstract_inverted_index.to | 7, 30, 43, 126, 177 |
| abstract_inverted_index.up | 125 |
| abstract_inverted_index.we | 196, 204 |
| abstract_inverted_index.$D$ | 106, 122 |
| abstract_inverted_index.$n$ | 99, 120 |
| abstract_inverted_index.And | 191 |
| abstract_inverted_index.D)$ | 95 |
| abstract_inverted_index.For | 143 |
| abstract_inverted_index.See | 229 |
| abstract_inverted_index.The | 36 |
| abstract_inverted_index.[We | 213 |
| abstract_inverted_index.all | 209 |
| abstract_inverted_index.and | 84, 93, 105, 121, 226 |
| abstract_inverted_index.are | 22, 28, 123 |
| abstract_inverted_index.but | 159 |
| abstract_inverted_index.can | 75 |
| abstract_inverted_index.for | 5 |
| abstract_inverted_index.has | 134 |
| abstract_inverted_index.n)$ | 92, 162 |
| abstract_inverted_index.not | 150, 187 |
| abstract_inverted_index.one | 61 |
| abstract_inverted_index.the | 8, 33, 45, 63, 87, 101, 108, 172, 233 |
| abstract_inverted_index.This | 169 |
| abstract_inverted_index.bits | 96, 155, 163 |
| abstract_inverted_index.case | 195 |
| abstract_inverted_index.does | 149 |
| abstract_inverted_index.done | 77 |
| abstract_inverted_index.full | 230 |
| abstract_inverted_index.line | 131 |
| abstract_inverted_index.most | 64 |
| abstract_inverted_index.need | 206 |
| abstract_inverted_index.node | 82 |
| abstract_inverted_index.only | 160 |
| abstract_inverted_index.such | 211 |
| abstract_inverted_index.that | 13, 32, 51, 73, 80, 136, 146, 185, 194 |
| abstract_inverted_index.then | 38 |
| abstract_inverted_index.this | 19, 68, 74 |
| abstract_inverted_index.with | 40, 217 |
| abstract_inverted_index.work | 133 |
| abstract_inverted_index.Local | 0 |
| abstract_inverted_index.These | 89 |
| abstract_inverted_index.bound | 113 |
| abstract_inverted_index.cycle | 117, 189 |
| abstract_inverted_index.dense | 227 |
| abstract_inverted_index.equal | 124 |
| abstract_inverted_index.graph | 183 |
| abstract_inverted_index.known | 115 |
| abstract_inverted_index.local | 141 |
| abstract_inverted_index.lower | 112 |
| abstract_inverted_index.nodes | 9, 21, 37, 104 |
| abstract_inverted_index.prove | 31 |
| abstract_inverted_index.shown | 135 |
| abstract_inverted_index.since | 192 |
| abstract_inverted_index.small | 220 |
| abstract_inverted_index.takes | 153 |
| abstract_inverted_index.their | 41 |
| abstract_inverted_index.there | 52 |
| abstract_inverted_index.these | 48, 215 |
| abstract_inverted_index.using | 78 |
| abstract_inverted_index.where | 98 |
| abstract_inverted_index.which | 27 |
| abstract_inverted_index.write | 198 |
| abstract_inverted_index.(where | 119 |
| abstract_inverted_index.answer | 214 |
| abstract_inverted_index.called | 25 |
| abstract_inverted_index.cannot | 197 |
| abstract_inverted_index.encode | 81 |
| abstract_inverted_index.graph. | 88 |
| abstract_inverted_index.graphs | 118, 165 |
| abstract_inverted_index.grids, | 225 |
| abstract_inverted_index.holds. | 17, 35 |
| abstract_inverted_index.leader | 56, 180 |
| abstract_inverted_index.number | 102 |
| abstract_inverted_index.raises | 171 |
| abstract_inverted_index.recent | 130 |
| abstract_inverted_index.unique | 55 |
| abstract_inverted_index.verify | 44 |
| abstract_inverted_index.$O(\log | 91, 94, 161 |
| abstract_inverted_index.$Θ(n)$ | 154 |
| abstract_inverted_index.achieve | 178 |
| abstract_inverted_index.bounded | 167 |
| abstract_inverted_index.certain | 15 |
| abstract_inverted_index.chordal | 223 |
| abstract_inverted_index.classes | 184 |
| abstract_inverted_index.contain | 151, 188 |
| abstract_inverted_index.general | 157 |
| abstract_inverted_index.graphs, | 158, 222, 224 |
| abstract_inverted_index.graphs. | 228 |
| abstract_inverted_index.graphs? | 190 |
| abstract_inverted_index.greatly | 139 |
| abstract_inverted_index.labels, | 24 |
| abstract_inverted_index.network | 12, 59, 137, 148 |
| abstract_inverted_index.paper.] | 234 |
| abstract_inverted_index.require | 90 |
| abstract_inverted_index.results | 218 |
| abstract_inverted_index.abstract | 231 |
| abstract_inverted_index.actually | 205 |
| abstract_inverted_index.assigned | 23 |
| abstract_inverted_index.diameter | 221 |
| abstract_inverted_index.example, | 144 |
| abstract_inverted_index.matching | 111 |
| abstract_inverted_index.possible | 176 |
| abstract_inverted_index.problems | 66 |
| abstract_inverted_index.property | 16, 34 |
| abstract_inverted_index.setting. | 69 |
| abstract_inverted_index.supposed | 29 |
| abstract_inverted_index.classical | 65 |
| abstract_inverted_index.diameter. | 109 |
| abstract_inverted_index.distances | 85 |
| abstract_inverted_index.mechanism | 4 |
| abstract_inverted_index.neighbors | 42 |
| abstract_inverted_index.question: | 173 |
| abstract_inverted_index.questions | 216 |
| abstract_inverted_index.structure | 138 |
| abstract_inverted_index.triangles | 152 |
| abstract_inverted_index.Certifying | 50 |
| abstract_inverted_index.certifying | 6, 145 |
| abstract_inverted_index.framework, | 20 |
| abstract_inverted_index.influences | 140 |
| abstract_inverted_index.treewidth. | 168 |
| abstract_inverted_index.well-known | 72 |
| abstract_inverted_index.communicate | 39 |
| abstract_inverted_index.constants). | 128 |
| abstract_inverted_index.correctness | 46 |
| abstract_inverted_index.identifiers | 83, 199, 207 |
| abstract_inverted_index.observation | 170 |
| abstract_inverted_index.topologies? | 212 |
| abstract_inverted_index.certificate, | 202 |
| abstract_inverted_index.certificates | 79 |
| abstract_inverted_index.certificates, | 26 |
| abstract_inverted_index.certificates. | 49 |
| abstract_inverted_index.certification | 1, 181 |
| abstract_inverted_index.respectively, | 97 |
| abstract_inverted_index.certification. | 142 |
| abstract_inverted_index.multiplicative | 127 |
| abstract_inverted_index.sublogarithmic | 179 |
| cited_by_percentile_year | |
| countries_distinct_count | 2 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile |