Lemma 1. $\frac{\sum_{i=1}^{n} p_i}{n}$ can be made arbitrarily large with sufficiently large $n$, where $p_i$ is the $i^\text{th}$ prime. Proof. Let $m$ be an arbitrary positive real. Pick a large prime $p_{k+1} > 2m$. Then if $n > 2k$, we have $\frac{\sum_{i=1}^{n} p_i}{n} \geq \frac{\sum_{i=k+1}^{n} 2m}{n} \geq \frac{2m(n-k)}{n} \geq \frac{2m(n-\frac{n}{2})}{n} = m$. So for all $n > 2k$, $\frac{\sum_{i=1}^{n} p_i}{n} \geq m$. -- end lemma 1 -- Lemma 2. Let $n$ be a positive integer and let $a_1, \ldots, a_k$ be positive integers such that $\sum_{i=1}^k a_i \leq n$. Then for any constant $c > 1$, $\operatorname{lcm} a_i < c^n$ for large enough $n$. Proof. We may assume that the $a_i$ are distinct powers of primes. This is because if an $a_i$ is a product of two or more primes, we can replace it with several $a'_i$ equal to its prime power factors. This decreases the sum while preserving the LCM. Then, if we have several powers of the same prime, we can delete all but the largest, which also decreases the sum while preserving the LCM. Now, we just need to bound $\prod_{i=1}^{n} a_i$ given that $\sum a_i \leq n$. Suppose that $\sum_{i=1}^s p_i \leq n < \sum_{i+1}^{s+1} p_i$. Then the sum of any $s+1$ prime powers (in fact, any $s+1$ primes) will exceed $n$, so $k \leq s$. By Jensen, $\frac{\sum \ln a_i}{k} \leq \ln \frac{\sum a_i}{k} \leq \ln \frac{n}{k}$, so $\prod a_i \leq \left( \frac{n}{k} \right)^k$. Now, we want to prove that $\left( \frac{n}{k} \right)^k$ grows less than exponentially. In fact for any constant $c$, we have $\left( \frac{n}{k} \right)^k \leq c^n \Leftrightarrow \left( \frac{n}{k} \right)^\frac{k}{n} \leq c \Leftrightarrow \frac{\ln x}{x} \leq \ln c$ where $x = \frac{n}{k} \geq \frac{n}{s} \geq \frac{\sum_{i=1}^s a_i}{s}$. Then the first lemma gives us that $x$ can be made arbitrarily large, and obviously $\frac{\ln x}{x}$ can be made arbitrarily close to $0$ with large $x$. -- end lemma 2 -- The (significantly loosened) bound we need at the very end is $\ell^2(n^2+2n+2) \leq 1.0001^n$; we can pick $c = \sqrt{1.00001}$ and pick $n$ such that $\left(\frac{1.0001}{1.00001}\right)^n \geq n^2+2n+2$ so this bound will suffice. Now we can finally return to the problem. Build a subset $C$ of $V(G)$ as follows: as long as a cycle completely in $V(G) \setminus C$ exists, add the vertices of that cycle to $C$. So after we're done, the graph induced by $V(G) \setminus C$ will contain no cycles. Let the lengths of the cycles which we built $C$ with be $a_1, a_2, \ldots, a_k$. Let their LCM be $\ell$. Since these cycles are all disjoint, we have $\sum_{i=1}^k a_i = |C| \leq n$. Now note that, for any vertex in $C$, there is a closed (probably vertex-repeating) path of length $\ell$ from itself to itself (just take the cycle with which we added this vertex to $C$ enough times), so $v \in (N^+)^\ell(\{v\})$, and in fact for $T \subseteq C$, $T \subseteq (N^+)^\ell(T)$. So let $X$ be a given subset of $V(G)$, and let $S_j$ denote $(N^+)^{j}(X)$, with $S_0 := S$. Consider the sequence $T_i := S_i \cap C$. For every $i \in \mathbb{N}_0$, we have $T_i \subseteq T_{i+\ell} \subseteq T_{i+2\ell} \subseteq \ldots$. Since each of these sets is a subset of $V(G)$, their sizes are at most $n$. Now we consider, for some $i \in \mathbb{N}_0$, the value of $|T_{i\ell}| + |T_{i\ell + 1}| + \cdots + |T_{i\ell+\ell-1}|$. This is at least $0$, at most $n\ell$, and increasing in $i$, so among the first $(n\ell+1)(n+1)+1$ terms, at least $n+2$ consecutive ones are equal. Then all of the $T_i \subseteq T_{i+\ell}$ relations in this interval will have equality hold: that is, for some $q \leq (n(n+1)\ell-1)\ell$, we have $T_{i} = T_{i+\ell}$ for $q \leq i < q+(n+1)\ell$. We now claim that \[ S_{q+n\ell+\ell-1} = S_{q+(n+1)\ell+\ell-1} \] from which, since $S_{j+1}$ depends only on $S_j$, it will follow that every term after and including $S_{q+(n+1)\ell+\ell-1}$ will already have appeared previously in the sequence $\{S_j\}$, so the sequence will have at most $q+(n+2)\ell - 2 \leq (n(n+1)\ell-1)\ell + (n+2)\ell - 2 < (n(n+1)+n+2)\ell^2$ distinct terms. In fact suppose we have some vertex $v_{q+n\ell+\ell-1}$ that appears in one of $S_{q+n\ell+\ell-1}$ and $S_{q+(n+1)\ell+\ell-1}$ but not the other. This difference must be traceable to a difference in the previous sets. By reverse induction, we find the existence of at least one vertex $v_i$ in one of $S_{i}$ and $S_{i+\ell}$ but not the other, such that there is an edge from $v_i$ to $v_{i+1}$. But for $q \leq i < q+(n+1)\ell$, since $T_i = T_{i+\ell}$, none of the $v_i$ for these $i$ can be in $C$, so all are in $V(G) \setminus C$. Also, there are at least $n+1$ values of $i$ in this interval, so for some $i, j$ with $q \leq i < j < q+(n+1)\ell$, we have $v_i = v_j$. But $v_i, v_{i+1}, \ldots, v_j$ is a closed path from that vertex to itself with vertices entirely in $V(G) \setminus C$, a contradiction. Therefore, we have less than $(n^2+2n+2)\ell^2$ different terms in $\{S_i\}$, which is less than $1.0001^n$ for sufficiently large $n$.

math_explorer wrote: Now, let the lengths of the resulting closed paths be $a_1, a_2, \ldots, a_k$. Let their LCM be $\ell$. We have $\sum_{i=1}^k a_i = |C| \leq n$. What if one of the cycles (say the $i^{th}$) has fewer than $a_i$ vertices?

Oops, thanks for pointing that out. Never mind about merging cycles, I changed my proof to use only disjoint ones. Post edited.

Here's a proof (by Linus, the problem proposer, and me) that $g(n)\le f(n)\le g(n)+n^2-n-1$ for all $n>1$, where $g(n)$ denotes Landau's function. For convenience, we use $N(S)$ instead of $N^+(S)$ to represent the out-neighborhood of $S$. Let $D$ denote the set of vertices belonging to at least one (directed) cycle, and partition it into strongly connected components $D_1,D_2,\ldots,D_t$ for some $t\ge1$. Also set $d_i=|D_i|$ for $i\in[t]$, and let $D'=V(G)\setminus D$ be the set of vertices not part of any cycle. Now define the sequences $\{C_i\}_{i\ge0}$, $\{C'_i\}_{i\ge0}$ by $C_0=X\cap D$, $C'_0=X\cap D'$, and for $i\ge1$, \begin{align*} C_i &= N(C'_{i-1})\cap D, \\ C'_i &= N(C'_{i-1})\cap D'. \end{align*}In particular, $C'_i\subseteq N(C'_{i-1})$ when $i\ge1$. Lemma 1: $C'_i=\emptyset$ for all $i\ge |D'|$. Proof: If some vertex $v$ lies in $C'_i\cap C'_j\subseteq D'$ for some $0\le i<j$, then $v\in N^{j-i}(v)$, contradicting the fact that $v\in D'$. Then by pigeonhole, there exists $k\le |D'|$ such that $C'_k=\emptyset$, whence $C'_i=\emptyset$ for $i\ge k$.$\blacksquare$ Lemma 2: $N^M(X) = N(C'_{M-1})\bigcup\left(\bigcup_{m=0}^{M-1}N^{M-m}(C_m)\right)$ for every $M\ge1$. Proof: We proceed by induction, where the base case $M=1$ is obvious ($C_0,C'_0$ partition $X$). Now assuming the result for $M-1$ (where $M>1$), we have \begin{align*} N^M(X) &= N(N^{M-1}(X)) \\ &= N(N(C'_{M-2}))\bigcup\left(\bigcup_{m=0}^{M-2}N^{M-m}(C_m)\right) \\ &= N(C'_{M-1})\bigcup\left(\bigcup_{m=0}^{M-1}N^{M-m}(C_m)\right), \end{align*}where we use the fact that $C_{M-1},C'_{M-1}$ partition $N(C'_{M-2})$.$\blacksquare$ Corollary: $N^M(X) = \bigcup_{m=0}^{|D'|}N^{M-m}(C_m)$ for every $M\ge 1+|D'|$. Proof: Combining lemmas 1 and 2, we see that \[N^{1+|D'|}(X) = \bigcup_{m=0}^{|D'|}N^{1+|D'|-m}(C_m),\]so for $M\ge 1+|D'|$ we have \begin{align*} N^M(X) &= N^{M-1-|D'|}(N^{1+|D'|}(X)) \\ &= \bigcup_{m=0}^{|D'|}N^{M-m}(C_m), \end{align*}as desired.$\blacksquare$ Lemma 3: If $v\in G$ is a vertex in component $D_i$ ($1\le i\le t$), then the sequence $\{N^j(v)\}_{j\ge d_i(n-1)}$ is purely periodic and its minimal period $\ell_v\le d_i$ divides the length of every cycle $c$ passing through $v$ (by definition, $c$ can only pass through vertices in $D_i$). Proof: Let $C(v)=\{c_1,c_2,\ldots\}$ denote the set of cycles passing through $v$ (suppose $1\le |c_1|\le |c_2|\le\cdots$), where repeated vertices and edges are allowed. For $r\ge1$, let $g_r=\gcd(|c_1|,\ldots,|c_r|)$ and $g=\lim_{r\to\infty}g_r$ (any nonincreasing sequence of positive integers must have a limit). By minimality, $c_1$ must be simple (for convenience, we include $1$-cycles and $2$-cycles in this definition), so $|c_1|\le d_i$. Since $v\in N^{|c_1|}(v)$, we have \[v=N^0(v)\subseteq N^{|c_1|}(v)\subseteq\cdots\subseteq N^{|c_1|(n-1)}(v)\subseteq N^{|c_1|n}(v).\]But $|N^j(v)|\le n$ for all $j\ge0$, so by pigeonhole there exists $k\in[0,n-1]$ such that \begin{align*} |N^{|c_1|k}(v)| &=|N^{|c_1|(k+1)}(v)| \\ N^{|c_1|k}(v) &=N^{|c_1|(k+1)}(v) \\ N^j(v) &=N^{j+|c_1|}(v)\forall{j\ge |c_1|(n-1)}. \end{align*}(Similarly, for fixed $l\ge1$, $N^j(v)=N^{j+|c_l|}(v)$ for sufficiently large $j$.) Now take $s$ such that $g=g_s$; by Bézout's identity on $|c_1|,\ldots,|c_s|$, there exists $l_0$ such that $N^l(v)=N^{l+g}(v)$ for all $l\ge l_0$. But by repeatedly using the fact that $N^j(v)=N^{j+d}(v)$ for all $j\ge d_i(n-1)$, we see (by "translating down") that in fact $N^j(v)=N^{j+g}(v)$ for all $j\ge d_i(n-1)$. Thus $g$ (which clearly divides all relevant cycle lengths) is a period of $\{N^j(v)\}_{j\ge d_i(n-1)}$, so the minimal period $\ell_v$ must divide $g$, as desired.$\blacksquare$ Corollary: For fixed $i\in[t]$, there exists a positive integer $\ell(i)\le d_i$ such that $\ell(i)=\ell_v$ for every vertex $v\in D_i$. Proof: Assume for the sake of contradiction that $\ell_u\ne \ell_v$ for two distinct vertices $u,v\in D_i$, and consider a cycle of length $d$ (which, by lemma 3, must be divisible by both $\ell_u$ and $\ell_v$) passing through $u,v$. Then there must exist an integer $k\in(0,d)$ such that $u\in N^k(v)$ and $v\in N^{d-k}(u)$, so for sufficiently large $j$ we have \[N^{j+d}(u)=N^j(u)\subseteq N^{j+k}(v)\subseteq N^{(j+k)+(d-k)}(u),\]whence $N^j(u)=N^{j+k}(v)$. But then $\{N^j(u)\}_{j\ge d_i(n-1)}$ and $\{N^j(v)\}_{j\ge d_i(n-1)}$ (which are both purely periodic) must have the same (eventual, and thus "actual") minimal period, contradicting the minimality of $\max(\ell_u,\ell_v)$.$\blacksquare$ In accordance with the corollary of lemma 3, let $L=\operatorname{lcm}_{1\le i\le t}\ell(i)$ and $R=\sum_{i=1}^{t}\ell(i)$. By the corollaries of lemmas 2 and 3 (observe that $C_m\subseteq D$ for every $m\ge0$), we get \[N^M(X) = N^{M+L}(X)\]for all $M\ge 1+|D'|+\max_{1\le i\le t}d_i(n-1)-1$, whence there are at most (suppose WLOG that $d_1\le d_2\le\cdots\le d_t$) \begin{align*} (n-d_t+d_t(n-1))+L-1 &\le n+n(n-2)+g(R)-1 \\ &= n^2-n-1+g(R)\le n^2-n-1+g(n) \end{align*}distinct members of $\{N^{k}(X)\}_{k=1}^{\infty}$. On the other hand, by the definition of Landau's function, we can directly get a lower bound of $f(n)\ge g(n)$ by taking $G$ to be the union of disjoint cycles and placing exactly one vertex from each cycle into $X$. Comment: If Landau's function is constant on arbitrarily long strings of integers, finding the exact bound for all sufficiently large $n$ may get annoying. However, with more careful analysis we may be able to tighten these bounds on $f(n)$ a bit. Edit: Apparently it is.

Oh wow, that's an awesome proof. For the record, I was only able to get a bound around $ng(n)$; Victor here did all the rest. (And I was scared at first that the pdf you linked would be about this exact problem, ha.)