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.
The following algorithm will solve your problem

Strategy

The task is decomposed into 2 subtasks:


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'$, 
Conduct a BFS on $G'$ with reversed edge orientations, identifying and marking nearly roots.


Details


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. 
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


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.
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)$.