I'm working on a tool that can analyze sizes of individual functions in a compiled binary. For each one it calculates how much space would be saved if the function was removed.
However, the current algorithm is quadratic in the number of functions and as such is quite slow. Is there a better one? The problem formulation follows.
Let $G=(V, E)$ be a directed graph with labeling $f\colon V\to\mathbb{N}$, and $R\subseteq V$ be a set of root vertices. Here, $V$ represents the functions in the binary. The graph edges represent the dependencies between the functions: $(u, v)\in E$ iff $u$ references $v$, thus forcing $v$ to be present in the binary. $f$ assigns to each function its size in bytes. Functions in $R$ (the main function in the executable or the set of exported functions in an .so) are the functions we want in the binary, the rest of them were pulled in directly or indirectly from $R$.
For a set of vertices $U\subseteq V$ and edges $F\subseteq E$, we define $r(U, F)$ as the set of vertices reachable from $U$ along the edged from $F$.
$$r(U, F)=\{v\in V\mid \exists r\in U. (r, v)\in F^*\}$$
We guarantee that $r(R, E)=V$, that is all vertices are reachable from $R$ in the original graph (not that it helps).
We define $s(U) = \sum_{u\in U} f(u)$ as the total size of all functions from $U$.
For each $u\in V$, let $E_u\subseteq E$ be the restriction of $E$ in which all edges adjacent to $u$ are removed. Then $r(R\setminus\{u\}, E_u)$ is the set of functions that will be present in the binary if we remove $u$. Note that other functions besides $u$ may disappear as they will no longer be reachable from $R$.
Our goal is to compute for each $u\in V$ the size of the binary after removing $u$, i.e. to compute $g\colon V\rightarrow\mathbb{N}$ at all points, where
$$g(u)=s(r(R\setminus\{u\}, E_u))$$
I can easily compute $g(u)$ in $O(|V|+|E|)$ with a simple depth-first-search. Computing the entire $g$ thus yields $O(|V|(|V| + |E|))$. Is there a faster algorithm?