Abstract
We revisit the Heaviest Induced Ancestors (HIA) problem that was introduced by Gagie, Gawrychowski, and Nekrich [CCCG 2013] and has a number of applications in string algorithms. Let T₁ and T₂ be two rooted trees whose nodes have weights that are increasing in all roottoleaf paths, and labels on the leaves, such that no two leaves of a tree have the same label. A pair of nodes (u, v) ∈ T₁ × T₂ is induced if and only if there is a label shared by leafdescendants of u and v. In an HIA query, given nodes x ∈ T₁ and y ∈ T₂, the goal is to find an induced pair of nodes (u, v) of the maximum total weight such that u is an ancestor of x and v is an ancestor of y.
Let n be the upper bound on the sizes of the two trees. It is known that no data structure of size ?̃(n) can answer HIA queries in o(log n / log log n) time [Charalampopoulos, Gawrychowski, Pokorski; ICALP 2020]. This (unconditional) lower bound is a polyloglog n factor away from the query time of the fastest ?̃(n)size data structure known to date for the HIA problem [Abedin, Hooshmand, Ganguly, Thankachan; Algorithmica 2022]. In this work, we resolve the querytime complexity of the HIA problem for the nearlinear space regime by presenting a data structure that can be built in ?̃(n) time and answers HIA queries in ?(log n/log log n) time. As a direct corollary, we obtain an ?̃(n)size data structure that maintains the LCS of a static string and a dynamic string, both of length at most n, in time optimal for this space regime.
The main ingredients of our approach are fractional cascading and the utilization of an ?(log n/ log log n)depth tree decomposition. The latter allows us to break through the Ω(log n) barrier faced by previous works, due to the depth of the considered heavypath decompositions.
BibTeX  Entry
@InProceedings{charalampopoulos_et_al:LIPIcs.CPM.2023.8,
author = {Charalampopoulos, Panagiotis and Dudek, Bart{\l}omiej and Gawrychowski, Pawe{\l} and Pokorski, Karol},
title = {{Optimal NearLinear Space Heaviest Induced Ancestors}},
booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)},
pages = {8:18:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772761},
ISSN = {18688969},
year = {2023},
volume = {259},
editor = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17962},
URN = {urn:nbn:de:0030drops179624},
doi = {10.4230/LIPIcs.CPM.2023.8},
annote = {Keywords: data structures, string algorithms, fractional cascading}
}
Keywords: 

data structures, string algorithms, fractional cascading 
Collection: 

34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023) 
Issue Date: 

2023 
Date of publication: 

21.06.2023 