<p>We can reduce Boolean matrix multiplication to this problem by a three level construction, where the edges from the first level to the second level are determined by the first matrix and the edges from the second level to the third level are determined by the second matrix, and we query with <span class="math-container">$V'$</span> equal to the first level.</p>
<p>This reduction for <span class="math-container">$n \times n$</span> matrix produces an instance with <span class="math-container">$|V'| = n$</span>, <span class="math-container">$A = O(n)$</span>, and <span class="math-container">$m = O(n^2)$</span>, so an <span class="math-container">$O(|V'|A + m)$</span> time algorithm would imply an <span class="math-container">$O(n^2)$</span> time algorithm for Boolean matrix multiplication. While I don't think that this has been conjectured to be impossible, it would be a breakthrough result: Best algorithms for Boolean matrix multiplication have the same time complexity as general matrix multiplication, and no &quot;combinatorial&quot; algorithms with <span class="math-container">$O(n^{3-\epsilon})$</span> time complexity are known. (see e.g. the intro of [1] for references).</p>
<p>An algorithm with time complexity <span class="math-container">$O(|V|^\omega \log(|V|))$</span>, where <span class="math-container">$2 \le \omega &lt; 2.373$</span> is the matrix multiplication exponent can be given by computing the transitive closure of the DAG with matrix multiplication.</p>
<p>[1] <a href="https://acris.aalto.fi/ws/portalfiles/portal/40881045/1.9781611975482.31.pdf" rel="nofollow noreferrer">https://acris.aalto.fi/ws/portalfiles/portal/40881045/1.9781611975482.31.pdf</a></p>

CC BY-SA 4.0
2020-12-11T20:18:47.323Z
2020-12-12T09:05:32.570Z
2020-12-12T09:05:32.570Z
Laakeri
<p>Suppose I have a DAG, <span class="math-container">$G = (V, E)$</span> and we know that all nodes in the DAG have at most <span class="math-container">$A$</span> ancestors. Let <span class="math-container">$V' \subseteq V$</span> be a subset of vertices of <span class="math-container">$V$</span>. Is there a way to obtain the set of all ancestors of every vertex in <span class="math-container">$V'$</span> in <span class="math-container">$O(|V'|A + m)$</span> time? In other words, I want sets <span class="math-container">$B_i$</span> consisting of all ancestors of <span class="math-container">$v_i \in V'$</span> for all <span class="math-container">$v_i$</span>.</p>
<p>The trivial algorithm does this in <span class="math-container">$O(|V'|A^2)$</span> time (for very dense graphs) but I would like to do this in <span class="math-container">$O(|V'|A + m)$</span> time or even better <span class="math-container">$O(|V'|A + E(V', B(V')))$</span>. (Here <span class="math-container">$E(V', B(V'))$</span> indicates time proportional to the induced subgraph consisting of <span class="math-container">$V'$</span> and all ancestors of vertices in <span class="math-container">$V'$</span>.)</p>
<p>If we cannot do this, are there any known lower bounds for this runtime?</p>

<ds.algorithms><graph-theory><graph-algorithms><directed-acyclic-graph>
Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs
user1246462
# Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs

(Asked by: username_0 on 2020-12-10)

Suppose I have a DAG, $G = (V, E)$ and we know that all nodes in the DAG have at most $A$ ancestors. Let $V' \subseteq V$ be a subset of vertices of $V$. Is there a way to obtain the set of all ancestors of every vertex in $V'$ in $O(|V'|A + m)$ time? In other words, I want sets $B\_i$ consisting of all ancestors of $v\_i \in V'$ for all $v\_i$.

The trivial algorithm does this in $O(|V'|A^2)$ time (for very dense graphs) but I would like to do this in $O(|V'|A + m)$ time or even better $O(|V'|A + E(V', B(V')))$. (Here $E(V', B(V'))$ indicates time proportional to the induced subgraph consisting of $V'$ and all ancestors of vertices in $V'$.)

If we cannot do this, are there any known lower bounds for this runtime?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, directed-acyclic-graph

---

## 1 answers

### Answer by username_1 on 2020-12-11. Score: 2 | Accepted answer

We can reduce Boolean matrix multiplication to this problem by a three level construction, where the edges from the first level to the second level are determined by the first matrix and the edges from the second level to the third level are determined by the second matrix, and we query with $V'$ equal to the first level.

This reduction for $n \times n$ matrix produces an instance with $|V'| = n$, $A = O(n)$, and $m = O(n^2)$, so an $O(|V'|A + m)$ time algorithm would imply an $O(n^2)$ time algorithm for Boolean matrix multiplication. While I don't think that this has been conjectured to be impossible, it would be a breakthrough result: Best algorithms for Boolean matrix multiplication have the same time complexity as general matrix multiplication, and no "combinatorial" algorithms with $O(n^{3-\epsilon})$ time complexity are known. (see e.g. the intro of [1] for references).

An algorithm with time complexity $O(|V|^\omega \log(|V|))$, where $2 \le \omega < 2.373$ is the matrix multiplication exponent can be given by computing the transitive closure of the DAG with matrix multiplication.

[1] <https://acris.aalto.fi/ws/portalfiles/portal/40881045/1.9781611975482.31.pdf>


---

