23
$\begingroup$

Given is a dag. You want to label each node by how many nodes are reachable from it. $O(V(V+E))$ is a trivial upper bound; $\Omega(V+E)$ is a lower bound (I think). Is there a better algorithm? Is there reason to believe the lower bound can be improved (related: what exactly is known about lower bounds for transitive closure)?

Motivation: I had to do this a couple of times while representing fol formulas as dags.

Edit: Please note that simply doing $c_x=1+\sum_{x\to y}c_y$ counts paths, not reachable nodes. (I added this because apparently many people thought this simple solution would work by the votes I saw on a now-deleted answer.) In fact, this problem appears precisely when you want to do something interesting with 'shared' parts, nodes reachable by more than one path. Also, I say dag, because if they are solved, then solving digraphs is easy.

Improve this question
$\endgroup$
2
  • $\begingroup$ This appears to be a special case (setting all weights to one) of cstheory.stackexchange.com/questions/736/… $\endgroup$
    – Suresh Venkat
    Aug 29, 2010 at 20:28
  • $\begingroup$ @Suresh: Whether arbitrary weights make the problem harder seems to me like another interesting question. $\endgroup$
    – Radu GRIGore
    Aug 31, 2010 at 8:31

3 Answers 3

Reset to default
10
$\begingroup$

The transitive closure of a directed graph with $m$ edges and $n$ vertices can be computed slightly faster than $O(mn)$ time, but not by much. An $O(n^2 + mn/\log n)$ time algorithm is mentioned in a footnote of Chan's 2005 WADS paper on APSP (journal version in Algorithmica 2008). A slight improvement to $O(n^2 + mn \log(n^2/m)/\log^2 n)$ can be found in the ICALP'08 paper "A New Combinatorial Approach for Sparse Graph Problems " by Blelloch, Vassilevska and Williams. That being said, I don't know whether counting descendents is easier than actually finding them

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ Also, look at Edith Cohen's paper "Size-Estimation Framework with Applications to Transitive Closure and Reachability". It gives a randomized algorithm which estimates the number of descendents efficiently. $\endgroup$
    – virgi
    Sep 9, 2010 at 0:05
  • $\begingroup$ Note that this results apply to all directed graph, not just DAGs. $\endgroup$
    – tonfa
    Sep 20, 2010 at 8:30
  • $\begingroup$ Yes. The result also applies to the weighted version mentioned in cstheory.stackexchange.com/questions/736/… $\endgroup$
    – virgi
    Sep 22, 2010 at 15:10
7
$\begingroup$

I think you can use matrix multiplication to compute the transitive closure of the DAG, and then use the number of out-neighbors as the desired counts. I'm no expert on the literature but I think you can compute the transitive closure in the same time as matrix multiplication, i.e. $n^{\omega}$ time: http://www.computer.org/portal/web/csdl/doi/10.1109/ACSSC.1995.540810 .

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, that's interesting! I should add that dags representing symbolic formulas tend to be sparse, so I'm a bit more interested in this case. $\endgroup$
    – Radu GRIGore
    Aug 26, 2010 at 16:52
1
$\begingroup$

Maybe not useful in your context, but you can get an approximation using Synopsis Diffusion (http://www.cs.cmu.edu/~sknath/sd.htm). I think that makes it O(V+E). Simulating synopsis diffusion on a uniprocessor looks to me to be O(V+E), (you need to do a topological sort first, which is also O(V+E)).

Improve this answer
$\endgroup$

Your Answer

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

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