# Efficient topological sorting of the cartesian product of DAGs

Let us consider n directed acyclic graphs $$(G_i)_{1\leq i \leq n}$$ and G their cartesian product (with the induced edges) : G is still a DAG. Let us suppose that each vertex has a value, defined as the sum of the values of its children and that this value is known only for the leaves.

The problem is the efficient computation of the values for the vertices in $$\prod_{1 \leq i \leq n} H_i$$ for $$H_i \subset G_i$$ for every i.

My first idea would be, since G is a DAG:

1) to define the edges of the induced graph $$(\prod_{1 \leq i \leq n} H_i) \cup L$$ (L being the set of the leaves), thus giving the latter set a DAG structure

2) to apply topological ordering on this DAG and then recursively compute the missing values.

The first step is quite costly, as I have to find the induced edges for every node in H (complexity is at most quadratic in the number of induced edges).

The second step is not as costly, but still have a quadratic complexity (at most) due to the computation.

Most of all, this does not look very efficient, as this solution does not take advantage of the cartesian product!

How could I improve my current solution?