Is there a faster algorithm for my graph problem?

Question

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?

Answer 1

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.

Answer 2

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
  add v' to S
  N(v') := 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|)$.

---

Then, for general graphs, I'm not sure how to proceed. I'm trying to see if computing it as a fixpoint can work. Maybe using the quotient graph could also work.