Is there a faster algorithm for my graph problem?

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?

• I wonder if algorithms for dynamic graph reachability would be useful here. They allow to update reachability information as you insert/delete edges, more efficiently than re-computing the reachability information. – D.W. Aug 28 '16 at 23:28

In practice, just as you can calculate g (u) for one particular u quite quickly, you can calculate g (u) for all $u \in V$ in parallel, operating with bit vectors of $|V|$ bits instead of boolean values - this changes the number of operations only be a constant, but by a rather large constant. This is quite useful if you actually want the number of bytes saved for every u.

If you are only interested in one u, then you only want to know for each function: 1. Can it be reached from u? 2. Can it be reached from any function other than u? To decide that, just combine all the other functions in V into one single function which calls everything that any of these functions calls. You don't need to know all the individual call graphs, just what can be reached from any of the functions in V other than u.

Second comment: I thought that you wanted to know how many bytes are saved by removing one function. That took you O (|V| * (|V| + |U|) by calculating all g (u). Which looks quite bad and can be improved if you want to know the answer for one function. If you want to answer the question for all functions, then calculating all g (u) is fine. It still takes O (|V| * (|V| + |U|), but the work can be reused for every function.

That's a very common situation, where solving n problems can be done a lot quicker than n times solving one problem.

• In your first paragraph, that constant is usually 4 or 8, right? I didn't fully get the part with bit vectors, is there some other trick that makes the constat higher? – avakar Aug 29 '16 at 16:07
• I pretty much didn't get you second paragraph at all, can you elaborate? I'm interested in exactly the values of $g(u)$ for every $u\in V$, in other words, I need exactly $|V|$ numbers. – avakar Aug 29 '16 at 16:08
• Just noticed your edit. I might not have formulated the problem clearly. If I want to know how much is saved by removing one particular function, say $u$, which in my formulation is equivalent to computing $g(u)$, I can easily do it in $O(|V| + |E|)$ by computing the total size, then computing reachability on the graph with $u$ removed, and then subtracting. That's fine and I think it's optimal. However, I need to compute the savings for every function; I can trivially do it by computing $g(u)$ with the above algorithm for all $u$, yielding $O(|V|(|V| + |E|))$. I'm looking for a faster way. – avakar Aug 30 '16 at 19:49

For $v\in V$, define the set of necessary vertices for $v$ as

$$N(v)=\{v' \in V : \text{for any path } u_0,\dots, u_n \text{ so that } u_0 \in R\text{ and } u_n = v, \text{ there is an } i \text{ so that }u_i = v'\}$$

The idea here is that $v'\in N(v)$ iff any path from $R$ to $v$ goes through $v'$ iff removing $v'$ makes $v$ unreachable.

Assuming you have computed $N(v)$ for all $v$, then $$g(v)=\sum_{v'\in V}f(v')-\sum_{\substack{v'\in V\\v\not\in N(v')}}f(v')=\sum_{\substack{v'\in V\\v\in N(v')}}f(v')$$

For each v
g[v] := 0
For each v'
For each v in N(v')
g[v] += f(v')


Computing $g$ therefore costs $O(|V|^2)$ at most (but if you look closer, it's $\displaystyle O\left(\sum_{v'\in V}|N(v')|\right)$ which should often be way smaller).

Let's first try to compute $N$ in acyclic graphs:

I'll call $\operatorname{Pred}(v')$ the set of predecessors of $v'$ : $\operatorname{Pred}(v'):=\{v\in V : v \to v'\}$.

Then, I believe that $$N(v')=\{v'\}\cup \left(\bigcap_{v\in \operatorname{Pred}(v')}N(v')\right)$$

For v' in V in topological order
sets = map((x -> N(x)), pred(v'))
smallest_set, remaining_sets := smallest_set(sets)
S := smallest_set
for set in remaining_sets
for v in S
if v not in set
remove v from S

The cost is $O(|V|+|E|)$ for the topological sort, $O(|V|^2)$ to find the smallest set and then $O(|V|^3\log |V|)$ to compute the intersection (but it's also $\displaystyle O(\sum_{v'\in V}d^-(v')k_{v'}\log K_{v'})$ with $k_{v'}$ the size of the smallest necessary set of the predecessors of $v'$ and $K_{v'}$ the size of the biggest, and $d^-(v')=|\operatorname{Pred}(v')|$, and overall this shouldn't be too big because many predecessors implies many sets to intersect which implies small sets). You can therefore compute $N$ in $O(|V|^3\log |V|)$.