Mathialagan, Surya ;
Vassilevska Williams, Virginia ;
Xu, Yinzhan
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and FineGrained Lower Bounds
Abstract
The APLCA problem asks, given an nnode directed acyclic graph (DAG), to compute for every pair of vertices u and v in the DAG a lowest common ancestor (LCA) of u and v if one exists, i.e. a node that is an ancestor of both u and v but no proper descendent of it is their common ancestor. Recently [Grandoni et al. SODA'21] obtained the first subn^{2.5} time algorithm for APLCA running in O(n^{2.447}) time. Meanwhile, the only known conditional lower bound for APLCA is that the problem requires n^{ωo(1)} time where ω is the matrix multiplication exponent.
In this paper we study several interesting variants of APLCA, providing both algorithms and finegrained lower bounds for them. The lower bounds we obtain are the first conditional lower bounds for LCA problems higher than n^{ωo(1)}. Some of our results include:
 In any DAG, we can detect all vertex pairs that have at most two LCAs and list all of their LCAs in O(n^ω) time. This algorithm extends a result of [Kowaluk and Lingas ESA'07] which showed an Õ(n^ω) time algorithm that detects all pairs with a unique LCA in a DAG and outputs their corresponding LCAs.
 Listing 7 LCAs per vertex pair in DAGs requires n^{3o(1)} time under the popular assumption that 3uniform 5hyperclique detection requires n^{5o(1)} time. This is surprising since essentially cubic time is sufficient to list all LCAs (if ω = 2).
 Counting the number of LCAs for every vertex pair in a DAG requires n^{3o(1)} time under the Strong Exponential Time Hypothesis, and n^{ω(1,2,1)o(1)} time under the 4Clique hypothesis. This shows that the algorithm of [Echkardt, Mühling and Nowak ESA'07] for listing all LCAs for every pair of vertices is likely optimal.
 Given a DAG and a vertex w_{u,v} for every vertex pair u,v, verifying whether all w_{u,v} are valid LCAs requires n^{2.5o(1)} time assuming 3uniform 4hyperclique requires n^{4o(1)} time. This defies the common intuition that verification is easier than computation since returning some LCA per vertex pair can be solved in O(n^{2.447}) time.
BibTeX  Entry
@InProceedings{mathialagan_et_al:LIPIcs.ICALP.2022.94,
author = {Mathialagan, Surya and Vassilevska Williams, Virginia and Xu, Yinzhan},
title = {{Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and FineGrained Lower Bounds}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {94:194:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16435},
URN = {urn:nbn:de:0030drops164359},
doi = {10.4230/LIPIcs.ICALP.2022.94},
annote = {Keywords: AllPairs Lowest Common Ancestor, FineGrained Complexity}
}
28.06.2022
Keywords: 

AllPairs Lowest Common Ancestor, FineGrained Complexity 
Seminar: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Issue date: 

2022 
Date of publication: 

28.06.2022 