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.

$\endgroup$
  • $\begingroup$ This appears to be a special case (setting all weights to one) of cstheory.stackexchange.com/questions/736/… $\endgroup$ – Suresh Venkat Aug 29 '10 at 20:28
  • $\begingroup$ @Suresh: Whether arbitrary weights make the problem harder seems to me like another interesting question. $\endgroup$ – Radu GRIGore Aug 31 '10 at 8:31
9
$\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

$\endgroup$
  • 3
    $\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 '10 at 0:05
  • $\begingroup$ Note that this results apply to all directed graph, not just DAGs. $\endgroup$ – tonfa Sep 20 '10 at 8:30
  • $\begingroup$ Yes. The result also applies to the weighted version mentioned in cstheory.stackexchange.com/questions/736/… $\endgroup$ – virgi Sep 22 '10 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 .

$\endgroup$
  • $\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 '10 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)).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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