Random directed acyclic graph (Barak-Erdös): find "upstream" vertices

Question

The problem

Consider a set of $N$ vertices $V=\{v_1,v_2,...,v_N\}$. We define a random directed acyclic graph by the set of edges $E$ as follows: for every $i<j$, $e_{ij}:=(v_i\rightarrow v_j) \in E$ with probability $p$, independent of other edges.

We are looking for an algorithm to determine the "maximal" or "upstream" vertices; that is, output the set $$V_{\max}=\{v_i\mid \forall j, e_{ij} \notin E\}$$

Assume that the indexing (used in problem statement for convenience) is not accessible to the algorithm (i.e., given $v_i$ and $v_j$, there is no direct way to know whether $i<j$ or $j<i$ without looking at the edges).

We consider two possible conditions:

1. the set of all edges is fed as an input to the algorithm; looping over all edges is a $O(|E|)$ operation, testing a if a given edge exist is $O(1)$
2. the set of all edges is not known; an oracle can tell us whether a given edge exists in $O(1)$ (we want to minimize the number of such queries) but looping over all edges is $O(N^2)$ (requires to query every possible edge).

The graphs in question are called "stochastic ordered graphs" or "Barak-Erdös graphs" in the literature (after the authors of the 1984 paper On the maximal number of strongly independent vertices in a random acyclic directed graph.). I searched Google-Scholar a bit, but I found mostly math papers interested in percolation theory / longest path problems etc. rather than the maximal subsets, and nothing in the way of construction algorithms (although this is not my field at all, and I might have missed obvious stuff).

Already known

A previous question (Finding maximal elements of a partially ordered set) roughly approximates condition 2 (edges are not necessarily a preorder because of a lack of transitivity, but adding edges to make the graph transitive does not change $V_{\max}$). The following findings are applicable:

• a simple algorithm in $O(N^2)$ exists to solve both conditions
• there are graphs where no algorithm can do better than this: for instance, for $p=0$ (the graph has no edge) in condition 2, all $O(N^2)$ possible edges must be queried (to differentiate this case from the one where a single, unqueried edge exists).
• there are cases where a quicker runtime is possible: for instance, for $p=1$ (every possible edge exists), any (sane) algorithm is linear in either condition (every edge query will eliminate one vertex from consideration, leaving only $v_1$ after $O(N)$ operations).

The interesting case is $0<p<1$, and the question is whether there is any reasonable expectation to find an algorithm that is sub-quadratic on average.

Obviously, if $|V_{\max}|=O(N^2)$, then any algorithm must be in $O(N^2)$ runtime (since it must at least output $V_{\max}$). However, this never happens for $p>0$. The abstract of the 1984 Barak-Erdös paper states (I cannot access the full text) that the cardinal of the largest strongly independent subset grows as $O(\sqrt{\log N})$. Therefore, the cardinal $V_{\max}$ grows at most at $O(\sqrt{\log N})$, though possibly less, and I could not outright refute the existence of a subquadratic algorithm. ($V_{\max}$ is not necessarily the largest strongly independent subset. For instance, consider the graph with vertices $1,2,3$ and edges $1\rightarrow 2, 1\rightarrow 3$; then $V_{\max}=\{1\}$ has cardinal 1 but $\{2,3\}$ is a strongly independent subset with cardinal 2.)

Some speculation

Given that $|E|\approx p\frac{N^2}{2}=O(N^2)$, it seems to me that conditions 1 and 2 are equivalent: any looping over the edges will immediately incur a quadratic cost, therefore any sub-quadratic algorithm needs to not look at a majority of the edges.

The worst-cases exhibited by hand are usually "sparse" graphs (few edges, many vertices in $V_{\max}$), and the best case are "full" (many edges, few vertices in $V_{\max}$) graphs, so I guess there is a better chance to find such an algorithm for high $p$. The Barak-Erdös result gives me some hope the typical case for any $p>0$ resembles more the "full" case than the "sparse" case.

Answer 1

This answer draws heavily from D.W.'s, which got the ball rolling.

The algorithm

live_set := V
survival_scores := 0 for every vertex

repeat N_repetitions times:
    v := random vertex from live_set among those with the lowest survival score
    w := random vertex from live_set

    if v->w exists:
        remove w from live_set
        increase v's survival_score by 1
    elseif w->v exists:
        remove v from live_set

output live_set

It is slightly modified from D.W.'s answer. The survival scores ensure that every vertex is tested approximately as many times. I expect it would improve the algorithm in practice, though it is mostly for the sake of fixing a rough edge in the proof of correction. Generating v "among those with the lowest survival_score" is not trivially an $O(1)$ operation, but can be made so using a bucket queue.

(Another improvement would be to remember which pairs of edges were already tested and avoid them, but doing so might be tricky.)

The algorithm has a runtime $O(N^{1+\alpha})\log N$ to output a set of no more than $O(N^{1-\alpha})$ elements, which includes $V_{max}$ and possibly some false positives (there are never any false negatives). See below for the choice of N_repetitions that ensures those conditions are met.

Proof of correction

Define $g=N_{repetitions}/N$ (number of operations normalized by the number of elements). The algorithm guarantees that every element of the input set is picked at least $g$ times for v (because in the worst-case scenario where no vertex is eliminated, survival score is spread equally among all vertices).

Consider a fraction $f$ of elements with the smallest indices (i.e. the most upstream elements: $v_1, v_2, ... v_{fN}$), which we will call the head $H$. For each iteration, the probability that one of those is selected as w is $f$ (at least; in practice, they are less likely to be eliminated than other vertices during comparisons). For now, we will accept that the output may incorrectly output elements from the head even if they are not maximal (see fine-tuning section below); we define the algorithm to be $\epsilon$ correct if, with probability at least $1-\epsilon$, its output contains every element from the maximal set and contains no non-maximal, non-head element.

Let $v\notin H$ be a given vertex that is not in the head. On average, $v$ will be selected together with an element $h\in H$ $f\times g$ times. In each such selection, there is a chance $p$ that $v$ will be eliminated; hence, in addition to chances to be eliminated in a "duel" against a non-head element, the probability of detection is:

$$P(detected)\geq 1-(1-p)^{fg}$$

More precisely, we are looking for the probability that $v$ escapes detection if it is non-maximal; by Bayes’s formula: $$P(detected|non-maximal)=P(non-maximal|detected)\times \frac{P(detected)}{P(non-maximal)}=\frac{P(detected)}{P(non-maximal)}\geq P(detected)$$

and therefore $P(not-detected|non-maximal) \leq q:=(1-p)^{fg}$

Thus, the probability that at least one non-maximal, non-head vertex fails to be detected by the algorithm is bounded by

$$P(algo\, fails)=1-(1-q)^{(1-f)N}\leq 1-(1-q)^{N}$$

Let us pick $q=\epsilon/N$. Then as $N$ grows large, the upper bound becomes $$P(algo\, fails) \leq 1-(1-\frac{\epsilon}{N})^{N}\approx 1-e^{-\epsilon} \approx \epsilon$$

Thus, we can ensure that the algorithm has a probability $\epsilon$ (or lower) to output any non-maximal, non-head vertex, by choosing $f$ and $g$ such that: $$ (1-p)^{fg} \leq \epsilon/N \iff fg \geq \frac{\log(N) - \log(\epsilon)}{\log(1/(1-p))} $$

Fine-tuning the parameters

We have to juggle between three constraints:

• we need $fg$ to be large to ensure $\epsilon$-correctness
• we need $f$ to be small to ensure that few non-maximal, head elements are returned
• we need $g$ to be small to have a small runtime

D.V.'s choice ($f$ and $g$ fixed with respect to $N$) does not match the second condition (the output set may contain $O(N)$ false positives). But we can change that!

Consider $f=K.N^{-\alpha}$ for some constant $K$ and $0<\alpha<1$. Then the head contains $fN=O(N^{1-\alpha})$ elements, and therefore the output set may contain $O(N^{1-\alpha})$ elements. On the other hand, to match the $\epsilon$-correctness criterion, we need $g=\frac{\log(N) - \log(\epsilon)}{K \log(1/(1-p))}N^\alpha$, which means $gN=O(N^{1+\alpha} \log N)$ operations.

A simple idea would be to take $\alpha=1/2$. The output set then contains $O(\sqrt{N})$ elements; the false positives can then be eliminated by running the (deterministic) naive algorithm, in $O(N)$ operations. This results in a total cost dominated by the $\alpha=1/2$ run, with $O(N^{3/2} \log N)$ operations.

A more complex idea would be to run the algorithm recursively with a small value of $\alpha$. In that case, the initial run costs less ($O(N^{1+\alpha} \log N)$), but the size of the input set at each step decreases exponentially: $O(N) \rightarrow O(N^{1-\alpha}) \rightarrow O(N^{2\times(1-\alpha)}) \rightarrow O(N^{3\times(1-\alpha)}) \rightarrow \dots$. However, proving that this recursive call is correct is more delicate, or maybe impossible. The proof relies heavily on the fact that every edge in the original input exists with independent probability $p$; however, a single run of the algorithm will eliminate the well-connected vertices, which will likely decrease the effective $p$ of the new graph and possibly invalidate the "independent edges" assumption as well.

Answer 2

I will assume you mean $p$ to be a fixed constant, and you care about the asymptotics as $N \to \infty$. In this case, for each fixed $p$ with $0<p<1$, I believe there is an $\tilde{O}(N)$ time algorithm (though the constant hidden by the big-O notation depends on $p$ and might be large). (However I have a lingering suspicion this might not be what you were looking for.)

It is not too hard to establish that $\mathbb{E}[|V_\max|] = \Theta(1/p)$, and with probability exponentially close to 1, $V_\max \le \Theta(1/p)$.

Let $T = \{v_{N-100Np},\dots,v_{N-1},v_N\}$. I will suggest a filtering algorithm that, with probability exponentially close to 1, outputs a set $S$ of vertices such that $S \subseteq T \cup V_\max$.

It follows that, with probability exponentially close to 1, $|S| \le O(1/p)$. Therefore, we can compare each element $s \in S$ to every vertex $v \in V$, and identify the maximal vertices in this way. This step will take $O(N/p) = O(N)$ steps.

So all that remains is to describe the filtering procedure. It works as follows:

• Repeat $100N/p^2$ times:

  • Randomly pick two non-deleted vertices $v,w$.
  • Compare $v$ to $w$.
  • If there is an edge $v \to w$, delete $v$. If there is an edge $w \to v$, delete $w$.

At the end of this procedure, $S$ is to defined to be the set of vertices that have not been deleted. It is easy to see that this procedure takes $O(N/p^2) = O(N)$ steps. All that remains is to justify its correctness.

Consider any vertex $v \in V \setminus T \setminus V_\max$. Since $v \notin T$, there are at least $100Np$ other vertices that appear after it in the list $v_1,\dots,v_N$. We can expect $v$ will be picked about $100/p^2$ times. Moreover, we can expect it will be picked together with some other vertex $w$ that appears after it about $100/p$ times. Therefore, with probability exponentially close to 1 (i.e., at least $1-(1-p)^{100/p} \approx 1-e^{-100}$), $v$ will be picked together with some other vertex $w$ such that there is an edge $v \to w$. So all vertices in $V \setminus T \setminus V_\max$ will be deleted, with probability exponentially close to 1. It follows that, with probability exponentially close to 1, $S \subseteq T \cup V_\max$.

Please check my reasoning. I haven't checked this carefully. Also, you might need to replace $100$ with $100 \log N$ to make everything go through (e.g., to apply a union bound over all $N$ vertices).