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)

  • $\begingroup$ 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? $\endgroup$ May 9, 2013 at 13:51

1 Answer 1


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.

For a dag, I remember there is a another algorithm to find whether two vertices share the same dominator for one source. Maybe it will help, you may search uva12671 for more information. (Actually, I am thinking a developing problem about this recently.)

Finally, I am also fascinated by it. If anybody has a new idea, please contact me anytime.

  • $\begingroup$ What does "at least $o(n^2)$" mean? $o(-)$ gives upper bounds so, in effect, you're saying "at least less than $n^2$". $\endgroup$ Apr 9, 2014 at 18:09
  • $\begingroup$ I'm sorry.It's my fault.I used this from careless .I mean that in the worst case ,we have to use n^2 space. $\endgroup$
    – Darcy
    Apr 10, 2014 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.