Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds

Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu

The AP-LCA problem asks, given an $n$-node 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$…