How to find all "nearly roots"?

Let $G=(V,E)$ a directed graph. We define $v \in V$ to be "nearly root" of there's a path from $v$ to at least $|V|/2$ vertices. How do you find the set of all "nearly roots" in linear time?

What we've tried is to build the strongly connected graph $G_{scc}$ obtained from $G$ and then to do a topological sort. Now we went backwards and for each $U\in G_{scc}$ we count how many vertices it can reach by scanning all outgoing edges and summing up all vertices reachable from it's successors. This seems wrong since we may count vertices more than once.

• "Linear" in what? Do you want an algorithm that runs in time $O(|\,V\,|)$, or $O(|\,E\,|)$, or would you accept one that ran in $O(|\,V\,|+|\,E\,|)$? Feb 14 '14 at 2:17
• @RickDecker Linear means O(V+E) Feb 14 '14 at 3:39
• Is this supposed to be on a word RAM? $\:$ (Although it seems unlikely that there's a way to achieve that time bound on a standard RAM, although I don't see how to prove that there is no such way either.) $\hspace{.37 in}$
– user12859
Feb 14 '14 at 3:52
• @Shmoopy You can count vertices more than once and still have a linear time algorithm! What is the precise running time of your algorithm? Feb 24 '14 at 9:18
• @PålGD The time is linear. The problem is that it's not correct. If you're counting vertices more than once it means that if , for example, there's only one vertex reachable from v, then we may mistakenly say that there are three vertices reachable from v. Feb 24 '14 at 9:20

The following algorithm will solve your problem

Strategy

1. Derive an annotated DAG from $G$. Contract cycles in $G$ to single nodes while traversing the implied spanning tree of a DFS, creating a graph $G'$,
2. Conduct a BFS on $G'$ with reversed edge orientations, identifying and marking nearly roots.

Details

1. Perform a DFS on $G$. It's used as a tool to identify and contract cycles while keeping tabs on the number of contracted nodes.

For cycle contraction it suffices to detect backward edges ( mark/unmark nodes when entering a node for the first time / leaving it for the last time ). Each time a backward edge $(w, v)$ has been detected, all nodes on the current DFS path $p = v \stackrel{*}{\rightarrow} w$ are coalesced into a new node $v'$, edges from nodes on $p$ are retained. These modifications can be done in situ

( $V_{i} := (V_{i-1} \ \{ x \in V_{i-1} | x \in p \}) \cup \{ v' \}$
, $E_{i} := (E_{i-1} \ \{ (x,y) \in E_{i-1} | x \in p \}) \cup \{ (v',y) \in V_{i}^2 | y \notin p \})$

for the $i$-th contraction, starting with $(V_0, E_0) := (E, V)$). Mark each node in $V_{i}$ with an attribute represents containing the number of nodes from $V$ it represents (i.e. initialising this attribute with $1$ and adding the cycle length subtracted by $1$ for each contraction). in case of contracted nodes also record the represented nodes by adding it to a stack attribute.

2. The resulting graph $G'$ is cycle-free (in particular: irreflexive). Next perform a BFS on $G'$ with all edges reversed. Propagate an attribute reachable: $V \rightarrow \mathbb{N}$ along the way which locally computes as $\text{reachable}(v) := (\text{represents}(v) - 1) + \sum_{w \in pred(v)\subset V'} \text{reachable}(w)$ with pred denoting the set of predecessors and reachable being initialised to $0$ for all maximal elements in $G'$. for all nodes $v \in G'$ with $\text{reachable}(v) \geq |V|/2$, mark all represented nodes from the original graph $G$ as nearly roots.

Complexity

1. Complexity of this operation is $O(E)$, as each edge is traversed at max 2 times in the course of the DFS and the contraction while the bookkeeping operations are $O(V)$ in total.
2. Complexity of this operation is $O(E)$, as each edge in $G'$ is traversed once during the BFS and $|E'| \leq |E|$. Updating reachable is $O(V')$ while marking the nodes from $G$ as nearly roots costs at most $O(V)$.