论文标题
列表，验证和计数DAG中最低的共同祖先：算法和细粒的下限
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds
论文作者
论文摘要
AP-LCA问题要求给定$ n $ node的定向无环图（DAG），以计算每对顶点$ u $和$ v $在dag中，如果有一个，则为$ u $和$ v $的最低祖先（lca），如果存在。在本文中，我们研究了几种有趣的AP-LCA变体，为它们提供了算法和细粒的下限。我们获得的下限是LCA问题的第一个条件下限，高于$ n^{ω-o（1）} $，其中$ω$是矩阵乘法指数。我们的一些结果包括： - 在任何DAG中，我们都可以检测所有具有两个LCA的顶点对，并在$ O（N^ω）$时间中列出其所有LCA。该算法扩展了[kowaluk和lingas esa'07]的结果，该结果显示了$ \ tilde {o}（n^ω）$ time算法，该算法在DAG中检测所有具有独特的LCA并输出其相应的LCAS。 - 列表$ 7 $ lcas每个顶点dag中的lcas需要$ n^{3-o（1）} $时间，这是在流行的假设下，即3-均匀的5-hyperclique检测需要$ n^{5-o（1）} $时间。这是令人惊讶的，因为本质上是立方时间足以列出所有LCA（如果$ω= 2 $）。 - 计算DAG中每个顶点对的LCA数量需要$ n^{3-o（1）} $时间在强的指数时间假设下，以及$ n^{ω（1,2,1）-o（1）-o（1）-o（1）} $ time在$ 4 $ clique-clique-clique假设下。这表明[Echkardt，Mühling和Nowak Esa'07]的算法用于列出每对顶点的所有LCA，这可能是最佳的。 - 给出了每个顶点$ u，v $的DAG和一个顶点$ W_ {U，V} $，验证是否有效lcas是否需要$ n^{2.5-o（1）} $ time均需$ n^{2.5-o（1）} $ time，假设3-均匀的4-Hyperclique需要4-Hyperclique，则需要$ N-Hyperclique需要$ n^^{4- o（1）$（1）$（1）} $。这无见常见的直觉，即验证比计算更容易，因为可以在$ o（n^{2.447}）$ time中解决每个顶点对的LCA [Grandoni等。苏打21]。
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$ if one exists. In this paper we study several interesting variants of AP-LCA, providing both algorithms and fine-grained lower bounds for them. The lower bounds we obtain are the first conditional lower bounds for LCA problems higher than $n^{ω-o(1)}$, where $ω$ is the matrix multiplication exponent. 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 $\tilde{O}(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^{3-o(1)}$ time under the popular assumption that 3-uniform 5-hyperclique detection requires $n^{5-o(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^{3-o(1)}$ time under the Strong Exponential Time Hypothesis, and $n^{ω(1,2,1)-o(1)}$ time under the $4$-Clique 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.5-o(1)}$ time assuming 3-uniform 4-hyperclique requires $n^{4 - o(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 [Grandoni et al. SODA'21].
