The Complexity of Landmark Hub Labeling

Kurzanzeige
dc.contributor.authorCoste, Louann
dc.contributor.authorLi, Ruoying
dc.contributor.authorStorandt, Sabine
dc.contributor.authorTöpfer, Tobias
dc.date.accessioned2025-08-20T12:55:27Z
dc.date.available2025-08-20T12:55:27Z
dc.date.issued2025
dc.description.abstractTo speed up the computation of shortest path distances between pairs of query nodes in a weighted graph, it is common to precompute a distance oracle. One of the most successful of these oracles is Hub Labeling (HL). Its good practical performance spurred research on the complexity of different HL variants, their structural properties, and suitable construction algorithms. Landmark Hub Labeling (LHL) is a generalization of HL. It enables the construction of distance oracles with similar query time but smaller space consumption than HL, which is an important aspect for practical usability. However, the complexity of LHL has not been thoroughly investigated so far. In this paper, we provide a complete picture of the complexity landscape of different LHL variants. Surprisingly, the only known HL variant for which a minimum-size oracle can be computed in polynomial time (namely ranked hierarchical HL) turns out to be NP-hard when generalized to LHL. We complement our hardness results with suitable approximation algorithms for all studied LHL variants based on novel structural insights.
dc.description.versionpublisheddeu
dc.identifier.doi10.1007/978-3-031-92935-9_4
dc.identifier.urihttps://kops.uni-konstanz.de/handle/123456789/74320
dc.language.isoeng
dc.subjectHub Labeling
dc.subjectShortest Path
dc.subjectNP-Hardness
dc.subject.ddc004
dc.titleThe Complexity of Landmark Hub Labelingeng
dc.typeINPROCEEDINGS
dspace.entity.typePublication
kops.citation.bibtex
@inproceedings{Coste2025Compl-74320,
  title={The Complexity of Landmark Hub Labeling},
  year={2025},
  doi={10.1007/978-3-031-92935-9_4},
  number={15680},
  isbn={978-3-031-92934-2},
  issn={0302-9743},
  address={Cham},
  publisher={Springer},
  series={Lecture Notes in Computer Science (LNCS)},
  booktitle={Algorithms and Complexity : 14th International Conference, CIAC 2025, Rome, Italy, June 10–12, 2025, Proceedings, Part II},
  pages={52--68},
  editor={Finocchi, Irene and Georgiadis, Loukas},
  author={Coste, Louann and Li, Ruoying and Storandt, Sabine and Töpfer, Tobias}
}
kops.citation.iso690COSTE, Louann, Ruoying LI, Sabine STORANDT, Tobias TÖPFER, 2025. The Complexity of Landmark Hub Labeling. 14th International Conference on Algorithms and Complexity : CIAC 2025. Rome, Italy, 10. Juni 2025 - 12. Juni 2025. In: FINOCCHI, Irene, Hrsg., Loukas GEORGIADIS, Hrsg.. Algorithms and Complexity : 14th International Conference, CIAC 2025, Rome, Italy, June 10–12, 2025, Proceedings, Part II. Cham: Springer, 2025, S. 52-68. Lecture Notes in Computer Science (LNCS). 15680. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-031-92934-2. Verfügbar unter: doi: 10.1007/978-3-031-92935-9_4deu
kops.citation.iso690COSTE, Louann, Ruoying LI, Sabine STORANDT, Tobias TÖPFER, 2025. The Complexity of Landmark Hub Labeling. 14th International Conference on Algorithms and Complexity : CIAC 2025. Rome, Italy, Jun 10, 2025 - Jun 12, 2025. In: FINOCCHI, Irene, ed., Loukas GEORGIADIS, ed.. Algorithms and Complexity : 14th International Conference, CIAC 2025, Rome, Italy, June 10–12, 2025, Proceedings, Part II. Cham: Springer, 2025, pp. 52-68. Lecture Notes in Computer Science (LNCS). 15680. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-031-92934-2. Available under: doi: 10.1007/978-3-031-92935-9_4eng
kops.citation.rdf
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/74320">
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Töpfer, Tobias</dc:creator>
    <dc:creator>Coste, Louann</dc:creator>
    <dc:contributor>Li, Ruoying</dc:contributor>
    <dcterms:abstract>To speed up the computation of shortest path distances between pairs of query nodes in a weighted graph, it is common to precompute a distance oracle. One of the most successful of these oracles is Hub Labeling (HL). Its good practical performance spurred research on the complexity of different HL variants, their structural properties, and suitable construction algorithms. Landmark Hub Labeling (LHL) is a generalization of HL. It enables the construction of distance oracles with similar query time but smaller space consumption than HL, which is an important aspect for practical usability. However, the complexity of LHL has not been thoroughly investigated so far. In this paper, we provide a complete picture of the complexity landscape of different LHL variants. Surprisingly, the only known HL variant for which a minimum-size oracle can be computed in polynomial time (namely ranked hierarchical HL) turns out to be NP-hard when generalized to LHL. We complement our hardness results with suitable approximation algorithms for all studied LHL variants based on novel structural insights.</dcterms:abstract>
    <dcterms:issued>2025</dcterms:issued>
    <dcterms:title>The Complexity of Landmark Hub Labeling</dcterms:title>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:language>eng</dc:language>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2025-08-20T12:55:27Z</dc:date>
    <dc:creator>Li, Ruoying</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2025-08-20T12:55:27Z</dcterms:available>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/74320"/>
    <dc:creator>Storandt, Sabine</dc:creator>
    <dc:contributor>Töpfer, Tobias</dc:contributor>
    <dc:contributor>Coste, Louann</dc:contributor>
  </rdf:Description>
</rdf:RDF>
kops.conferencefield14th International Conference on Algorithms and Complexity : CIAC 2025, 10. Juni 2025 - 12. Juni 2025, Rome, Italydeu
kops.date.conferenceEnd2025-06-12
kops.date.conferenceStart2025-06-10
kops.flag.knbibliographytrue
kops.location.conferenceRome, Italy
kops.sourcefieldFINOCCHI, Irene, Hrsg., Loukas GEORGIADIS, Hrsg.. <i>Algorithms and Complexity : 14th International Conference, CIAC 2025, Rome, Italy, June 10–12, 2025, Proceedings, Part II</i>. Cham: Springer, 2025, S. 52-68. Lecture Notes in Computer Science (LNCS). 15680. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-031-92934-2. Verfügbar unter: doi: 10.1007/978-3-031-92935-9_4deu
kops.sourcefield.plainFINOCCHI, Irene, Hrsg., Loukas GEORGIADIS, Hrsg.. Algorithms and Complexity : 14th International Conference, CIAC 2025, Rome, Italy, June 10–12, 2025, Proceedings, Part II. Cham: Springer, 2025, S. 52-68. Lecture Notes in Computer Science (LNCS). 15680. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-031-92934-2. Verfügbar unter: doi: 10.1007/978-3-031-92935-9_4deu
kops.sourcefield.plainFINOCCHI, Irene, ed., Loukas GEORGIADIS, ed.. Algorithms and Complexity : 14th International Conference, CIAC 2025, Rome, Italy, June 10–12, 2025, Proceedings, Part II. Cham: Springer, 2025, pp. 52-68. Lecture Notes in Computer Science (LNCS). 15680. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-031-92934-2. Available under: doi: 10.1007/978-3-031-92935-9_4eng
kops.title.conference14th International Conference on Algorithms and Complexity : CIAC 2025
relation.isAuthorOfPublicationd50ece47-4ff0-45bf-9fb8-2fab9fac088d
relation.isAuthorOfPublicationa3ac49b1-8947-4bb2-840c-50a5cb77fdf4
relation.isAuthorOfPublication04efdfc4-a112-4dbc-825d-21b88472bd0c
relation.isAuthorOfPublication.latestForDiscoveryd50ece47-4ff0-45bf-9fb8-2fab9fac088d
source.bibliographicInfo.fromPage52
source.bibliographicInfo.seriesNumber15680
source.bibliographicInfo.toPage68
source.contributor.editorFinocchi, Irene
source.contributor.editorGeorgiadis, Loukas
source.identifier.eissn1611-3349
source.identifier.isbn978-3-031-92934-2
source.identifier.issn0302-9743
source.publisherSpringer
source.publisher.locationCham
source.relation.ispartofseriesLecture Notes in Computer Science (LNCS)
source.titleAlgorithms and Complexity : 14th International Conference, CIAC 2025, Rome, Italy, June 10–12, 2025, Proceedings, Part II

Dateien

Sammlungen

Informatik und Informationswissenschaft: Publikationen