English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Let $G=(V,E)$ be an $n$-vertex directed acyclic graph (DAG). A lowest commonancestor (LCA) of two vertices $u$ and $v$ is a common ancestor $w$ of $u$ and$v$ such that no descendant of $w$ has the same property. In this paper, weconsider the problem of computing an LCA, if any, for all pairs of vertices ina DAG. The fastest known algorithms for this problem exploit fast matrixmultiplication subroutines and have running times ranging from $O(n^{2.687})$[Bender et al.~SODA'01] down to $O(n^{2.615})$ [Kowaluk and Lingas~ICALP'05]and $O(n^{2.569})$ [Czumaj et al.~TCS'07]. Somewhat surprisingly, all thosebounds would still be $\Omega(n^{2.5})$ even if matrix multiplication could besolved optimally (i.e., $\omega=2$). This appears to be an inherent barrier forall the currently known approaches, which raises the natural question onwhether one could break through the $O(n^{2.5})$ barrier for this problem.  In this paper, we answer this question affirmatively: in particular, wepresent an $\tilde O(n^{2.447})$ ($\tilde O(n^{7/3})$ for $\omega=2$) algorithmfor finding an LCA for all pairs of vertices in a DAG, which represents thefirst improvement on the running times for this problem in the last 13 years. Akey tool in our approach is a fast algorithm to partition the vertex set of thetransitive closure of $G$ into a collection of $O(\ell)$ chains and $O(n/\ell)$antichains, for a given parameter $\ell$. As usual, a chain is a path while anantichain is an independent set. We then find, for all pairs of vertices, a\emph{candidate} LCA among the chain and antichain vertices, separately. Thefirst set is obtained via a reduction to min-max matrix multiplication. Thecomputation of the second set can be reduced to Boolean matrix multiplicationsimilarly to previous results on this problem. We finally combine the twosolutions together in a careful (non-obvious) manner.

All-Pairs LCA in DAGs: Breaking through the $O(n^{2.5})$ barrier