2026-08-12T01:35:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23247 2025-10-27T10:36:12Z ddc:004 open_access

Incremental Reachability Index Bulteau, Laurent David, Pierre-Yves Horn, Florian Tran-Girard, Euxane Directed acyclic graphs reachability append-only index We study the reachability problem in append-only DAGs: given two nodes u and v, is there a path from u to v? While the problem is linear in general, it can be answered faster by using a precomputed index, which gives a compressed representation of the transitive closure of the graph. Index algorithms are evaluated on three dimensions: the query time that the algorithm needs to answer whether there is a path from one node to another, the memory that the index uses per node, and the indexing time that is required to update the index when a node is added to the graph. In this paper, we combine Jagadish’s static index [Jagadish, 1990] with Felsner’s online chain-decomposition algorithm [Stefan Felsner, 1997] to create an incremental index: data associated with a node is immutable, guaranteeing that queries are answered properly even if new nodes are inserted while the query is processed. Its query time is constant, but its index size is heavily dependent on the graph width, and as such is not competitive with recent indexing algorithms (2-hop, tree-chain, ...). We also propose a version of that incremental algorithm with a much lighter index. In the most compressed version, the query time becomes O(log n). However, constant-time queries can be retained depending on the desired time/memory trade-off. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Laurent Bulteau and Pierre-Yves David and Florian Horn and Euxane Tran-Girard 2025 Is Part Of LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2025.9 urn:nbn:de:0030-drops-232477 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.9 eng https://creativecommons.org/licenses/by/4.0/legalcode