<p>Given a DAG <span class="math-container">$G = (V, E)$</span>, let <span class="math-container">$T \subseteq V$</span> be a set of nodes of <span class="math-container">$V$</span> that is computed via the following process. Assuming the nodes of <span class="math-container">$G$</span> are sorted in topological order, <span class="math-container">$v_1, \dots, v_n$</span>. We process the nodes in this topological order. Suppose we are processing vertex <span class="math-container">$v_i$</span> in the order. Let <span class="math-container">$r(v_i)$</span> be the set of ancestors of <span class="math-container">$v_i$</span>. We add <span class="math-container">$v_i$</span> and all ancestors of <span class="math-container">$v_i$</span> into <span class="math-container">$T$</span> if and only if the number of ancestors of <span class="math-container">$v_i$</span> (including <span class="math-container">$v_i$</span> itself) that are not in <span class="math-container">$T$</span> is at least <span class="math-container">$\frac{|r(v_i)| + 1}{f}$</span> where <span class="math-container">$f$</span> is some constant <span class="math-container">$f &gt; 1$</span> provided as part of the input. If a vertex is added to <span class="math-container">$T$</span>, then all its ancestors are also added into <span class="math-container">$T$</span>. Any algorithm that computes <span class="math-container">$T$</span> must satisfy the following invariant: any vertex <span class="math-container">$v_i$</span> added into <span class="math-container">$T$</span> must have at least <span class="math-container">$\frac{|r(v_i)| + 1}{f}$</span> of its ancestors (including itself) not in <span class="math-container">$T$</span> when it was added, and any vertex <span class="math-container">$v_i$</span> not added into <span class="math-container">$T$</span> must have <span class="math-container">$&lt; \frac{|r(v_i)| + 1}{f}$</span> of its ancestors (including itself) not in <span class="math-container">$T$</span>.</p>
<p><strong>Problem:</strong> Provide an algorithm that runs in <span class="math-container">$\tilde{O}(m + n)$</span> time (meaning ignoring polylogarithmic factors) that provides a valid set <span class="math-container">$T$</span> given an input graph <span class="math-container">$G = (V, E)$</span> and the processing order of the vertices is the toposort order. Approximation (meaning constant error on the <span class="math-container">$\frac{r(v_i)+1}{f}$</span> condition) and Las Vegas algorithms are welcome also. You may preprocess the graph but the preprocessing time must also be <span class="math-container">$\tilde{O}(m + n)$</span>.</p>
<p><strong>Trivial Solution in More Time</strong> We can do this trivially in <span class="math-container">$O(nm)$</span> time. For each <span class="math-container">$v_i$</span>, we find via BFS its set of ancestors and check whether each one is in <span class="math-container">$T$</span>. From this we can compute the exact fraction that is not in <span class="math-container">$T$</span> and either put <span class="math-container">$v_i$</span> and <span class="math-container">$r(v_i)$</span> in <span class="math-container">$T$</span> or not.</p>
<p><strong>Example Problem:</strong> Suppose you have the following trivial DAG (below) and <span class="math-container">$f= 2$</span>.</p>
<blockquote>
<p>a -&gt; b -&gt; c</p>
</blockquote>
<p>Then, <span class="math-container">$T = \{a, b\}$</span>. <span class="math-container">$a$</span> is processed first and <span class="math-container">$T = \emptyset$</span> at first so <span class="math-container">$a$</span> is added into <span class="math-container">$T$</span>. Then, <span class="math-container">$b$</span> is processed after <span class="math-container">$a$</span> and is added to <span class="math-container">$T$</span> since <span class="math-container">$1/2$</span> of the vertices in <span class="math-container">$\{a, b\}$</span> are not in <span class="math-container">$T$</span>. Finally, <span class="math-container">$c$</span> is processed and not added to <span class="math-container">$T$</span> since it has at most <span class="math-container">$1/3$</span> of the vertices in <span class="math-container">$\{a, b, c\}$</span> are not in <span class="math-container">$T$</span>. Note that in this example, a trivial <span class="math-container">$O(n)$</span> algorithm for any line is to keep a counter <span class="math-container">$c$</span> of the <em>index</em> of the last element added to <span class="math-container">$T$</span> (since adding the element at <span class="math-container">$c$</span> also means adding all its ancestors) and add the <span class="math-container">$i$</span>-th element of the line to <span class="math-container">$T$</span> if <span class="math-container">$\frac{i-c}{i} \geq \frac{1}{f}$</span>. However, this problem is much less trivial for general graphs.</p>
<p>Has anyone seen a problem similar to this in the literature or algorithms which solve similar problems?</p>

CC BY-SA 4.0
2020-11-05T14:15:09.817Z
It would be enough to compute $|r(v_i)|$ and the number of ancestors of $v_i$ in $T$ for each node as you go along. Computing $|r(v_i)|$ for each $v_i$ is discussed at e.g. https://cstheory.stackexchange.com/questions/553/what-bounds-can-be-put-on-counting-reachable-nodes-in-a-dag.   You could use Edith Cohen's linear-time approximation algorithm for that ("Size-Estimation Framework with Applications to Transitive Closure and Reachability"), and _maybe_ (by putting weight-zero on nodes not in $T$?) also estimate ancestors in $T$.
Neal Young
CC BY-SA 4.0
2020-11-05T17:11:29.010Z
So computing the number of ancestors of $v_i$ in $T$ as you go along is not quite trivial in near-linear time (I don't know how). Suppose you have a node $v_i$ that you *did not add* to $T$ when you processed it in the topological order of processing. Then, later, you add $v_j$ (when you reach it during your processing) where $j > i$ to $T$. Suppose $v_i$ is an ancestor of $v_j$. When you add $v_j$, you also add $v_i$ by the problem definition. Then, how do you obtain the right set of ancestors in $T$ for every node later in the processing order? How does one account for $v_i$ is now in $T$?
user1246462
CC BY-SA 4.0
2020-11-06T01:03:31.950Z
Oh I missed the part about adding $v_i$'s ancestors as well.  And I agree it seems challenging, either way.
Neal Young
<ds.algorithms><graph-theory><graph-algorithms><directed-acyclic-graph>
Finding nodes with enough unique ancestors
user1246462
# Finding nodes with enough unique ancestors

(Asked by: username_0 on 2020-11-02)

Given a DAG $G = (V, E)$, let $T \subseteq V$ be a set of nodes of $V$ that is computed via the following process. Assuming the nodes of $G$ are sorted in topological order, $v\_1, \dots, v\_n$. We process the nodes in this topological order. Suppose we are processing vertex $v\_i$ in the order. Let $r(v\_i)$ be the set of ancestors of $v\_i$. We add $v\_i$ and all ancestors of $v\_i$ into $T$ if and only if the number of ancestors of $v\_i$ (including $v\_i$ itself) that are not in $T$ is at least $\frac{|r(v\_i)| + 1}{f}$ where $f$ is some constant $f > 1$ provided as part of the input. If a vertex is added to $T$, then all its ancestors are also added into $T$. Any algorithm that computes $T$ must satisfy the following invariant: any vertex $v\_i$ added into $T$ must have at least $\frac{|r(v\_i)| + 1}{f}$ of its ancestors (including itself) not in $T$ when it was added, and any vertex $v\_i$ not added into $T$ must have $< \frac{|r(v\_i)| + 1}{f}$ of its ancestors (including itself) not in $T$.

**Problem:** Provide an algorithm that runs in $\tilde{O}(m + n)$ time (meaning ignoring polylogarithmic factors) that provides a valid set $T$ given an input graph $G = (V, E)$ and the processing order of the vertices is the toposort order. Approximation (meaning constant error on the $\frac{r(v\_i)+1}{f}$ condition) and Las Vegas algorithms are welcome also. You may preprocess the graph but the preprocessing time must also be $\tilde{O}(m + n)$.

**Trivial Solution in More Time** We can do this trivially in $O(nm)$ time. For each $v\_i$, we find via BFS its set of ancestors and check whether each one is in $T$. From this we can compute the exact fraction that is not in $T$ and either put $v\_i$ and $r(v\_i)$ in $T$ or not.

**Example Problem:** Suppose you have the following trivial DAG (below) and $f= 2$.

> a -> b -> c

Then, $T = \{a, b\}$. $a$ is processed first and $T = \emptyset$ at first so $a$ is added into $T$. Then, $b$ is processed after $a$ and is added to $T$ since $1/2$ of the vertices in $\{a, b\}$ are not in $T$. Finally, $c$ is processed and not added to $T$ since it has at most $1/3$ of the vertices in $\{a, b, c\}$ are not in $T$. Note that in this example, a trivial $O(n)$ algorithm for any line is to keep a counter $c$ of the *index* of the last element added to $T$ (since adding the element at $c$ also means adding all its ancestors) and add the $i$-th element of the line to $T$ if $\frac{i-c}{i} \geq \frac{1}{f}$. However, this problem is much less trivial for general graphs.

Has anyone seen a problem similar to this in the literature or algorithms which solve similar problems?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, directed-acyclic-graph
> **Comments:**
> **username_1**: It would be enough to compute $|r(v_i)|$ and the number of ancestors of $v_i$ in $T$ for each node as you go along. Computing $|r(v_i)|$ for each $v_i$ is discussed at e.g. https://cstheory.stackexchange.com/questions/553/what-bounds-can-be-put-on-counting-reachable-nodes-in-a-dag.   You could use Edith Cohen's linear-time approximation algorithm for that ("Size-Estimation Framework with Applications to Transitive Closure and Reachability"), and _maybe_ (by putting weight-zero on nodes not in $T$?) also estimate ancestors in $T$.  
> **username_0**: So computing the number of ancestors of $v_i$ in $T$ as you go along is not quite trivial in near-linear time (I don't know how). Suppose you have a node $v_i$ that you *did not add* to $T$ when you processed it in the topological order of processing. Then, later, you add $v_j$ (when you reach it during your processing) where $j > i$ to $T$. Suppose $v_i$ is an ancestor of $v_j$. When you add $v_j$, you also add $v_i$ by the problem definition. Then, how do you obtain the right set of ancestors in $T$ for every node later in the processing order? How does one account for $v_i$ is now in $T$?  
> **username_1**: Oh I missed the part about adding $v_i$'s ancestors as well.  And I agree it seems challenging, either way.  

---

## 0 answers

