What is considered an asymptotic improvement for graph algorithms?
The most permissive definition is as follows.
Suppose that $f(V,E),g(V,E)$ are two running times of graph algorithms solving the same problem.
We say that $f$ is an asymptotic improvement in some regime on $g$ if there exists a sequence $V_n,E_n$ with $V_n \to \infty$ such that
$$
\lim_{n\to\infty} \frac{f(V_n,E_n)}{g(V_n,E_n)} = 0.
$$
Sometimes the regime is not deemed interesting, but that's a more subjective matter.
Note also that the problem already manifests itself for one-variable functions. Consider
$$
f(n) = n^2, \qquad g(n) = \begin{cases} 2^n &amp;\text{if } n = 2^m, \\ n &amp; \text{otherwise}. \end{cases}
$$
Is $f$ an asymptotic improvement over $g$? It is for inputs of a certain length, and is indeed so under our permissive definition above.