# Multiple-sources dominator trees: compact representation and fast algorithm?

I recently learnt about the concept of dominator trees and was fascinated by it.

I was wondering how the problem extends to computing dominators from multiple sources, or even from all vertices in the graph as sources: can all-sources dominators be represented more compactly than in O(n^2) space and computed more efficiently than running the classic dominator tree algorithm from every vertex?

I tried searching for keywords like "multiple sources dominators" etc, but only found about "multiple-vertex dominators", which are a different thing (dominating sets of size > 1)

Does any of this become simpler if the graph is acyclic? (in fact, I work at Google and I think it'd be fun to apply this to the huge dependency graph of Google's build targets)

• I like this question! Intuitively there should be quite a lot of sharing, at least for the dag case. I have, however, a perhaps stupid question: Why would it help to know the dominators of a target in a build system? – Radu GRIGore May 9 '13 at 13:51

I think it's really hard to do that. First of all, for one source dominator tree, there are several dominator points for a vertex. If we want to use "Lengauer-Tarjan algorithm", we can't avoid using tree structure. But how can we save a tree with less than $o(n)$ space? It means that for $n$ source dominator tree, we have to use at least $o(n^2)$ space unless we create a new structure which can represent dominator's information more effective.
• What does "at least $o(n^2)$" mean? $o(-)$ gives upper bounds so, in effect, you're saying "at least less than $n^2$". – David Richerby Apr 9 '14 at 18:09