# Finding nodes with enough unique ancestors

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?

• 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. cstheory.stackexchange.com/questions/553/…. 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$. Nov 5 '20 at 14:15
• 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$? Nov 5 '20 at 17:11
• Oh I missed the part about adding $v_i$'s ancestors as well. And I agree it seems challenging, either way. Nov 6 '20 at 1:03