How to find all topological sortings of a special DAG in O(N^2)

Question

I came across the following question in a hackerrank competition, which is based on topological sorting of a DAG.

https://www.hackerrank.com/contests/hourrank-29/challenges/birthday-assignment/forum

Problem description:

Nikita has a family tree $T$ consisting of $N$ members number from $1$ to $N$. Each of the $N-1$ edges in the tree represents a directed relationship. Basically if there is an edge from member $A$ to $B$, it means $B$ was born before $A$. Now, Nikita knows that these $N$ members were born in last $M$ days and only $1$ person was born on a single day, She is interested in calculating the number of ways to assign birthdays to each of the $N$ family members.

Since the required answer can be quite large, print it modulo $10^9+7$.

Editorial:

By now, you might have got the problem is all about finding the number of topological sortings in the randomly directed tree $T$.

Let randomly root the tree $T$ at any node say $1$. Lets calculate a $dp(i, j)$ denoting the number of topological sorts of subtree rooted at $i^{th}$ node such that $i^{th}$ node is placed at position. Assume that there are $X$ outgoing edges to the children from and $Y$ incoming edges. Note that all the $X$ children has to be placed on the left and all the $Y$ children has to be placed on the right side of $i^{th}$ in a valid topological sort.

Now lets calculate another $dp(i, j)$ for those $X$ nodes. Similiarly, we will do for $Y$ nodes. Here $dp(i, j)$ denotes the number of ways of filling $j$ spaces using topological sorts of subtrees rooted at $X_1, X_2, \cdots X_i$ such that $X_1, X_2, \cdots X_i$ is placed in $j$ spaces. Note that to compute this $dp$, we can use the $DP$ already calculated at these children nodes.

$$dp(i, j) = \sum_{1 \le k \le |S_i|} \left( nCr(j, k) \times dp(i-1, j-k) \times \sum_{1\le l \le k} DP(i, l) \right)$$

Note that this $\sum_{1\le l \le k} DP(i, l)$ is just a prefix sum and can be precomputed.

Now, for $X$ nodes basically you have computed $dp_j$, number of filling up $j$ spaces using subtrees of $X$ nodes such that $X_1, X_2, \cdots X_x$ is included. Lets call this $dp$ as $left[]$ and similary call the $dp$ for $Y$ nodes as $right[]$.

$$DP(i, j) = \sum_{1\le k < j} nCr(j-1, k) \times {left}_k \times nCr(a, b) \times {right}_{a-b}$$

Where $a = SZ_i - j$, $b = SZ_x - k$ and $SZ_i$ denotes the size of subtree rooted at $i^{th}$ node & $SZ_x$ denotes the sum of sizes of all subtrees rooted at all those $X$ nodes.

In the editorial section, it is claimed that the time complexity of the solution is $O(N^2)$. However, the problem is actually about finding all the topological sortings of a DAG, which to my knowledge is a NP-hard problem.

I believe that the added constraint that the number of edges is equal to $N-1$ simplifies the solution, and I couldn't think of any other possibility.

Could anyone kindly validate the solution?

Answer 1

First, the problem is about counting, not finding, all the topological sorts (though it is still hard for general DAGs). Second, the constraint that the graph is a tree makes this problem much simpler.

Consider a node $n$ with $k$ children $n_1,\ldots,n_k$. Suppose the subtrees rooted by $n_1,\ldots,n_k$ are respectively $T_1,\ldots,T_k$, the sizes of $T_1,\ldots,T_k$ are respectively $s_1,\ldots,s_k$, and the numbers of topological sorts of the members in $T_1,\ldots,T_k$ are respectively $c_1,\ldots,c_k$, then the number of topological sorts of the members in the tree rooted by $n$ is

$$\frac{(n_1+\cdots+n_k)!}{n_1!n_2!\cdots n_k!}c_1c_2\cdots c_k.$$

Using the formula above, you can compute the number of topological sorts of the members in each subtree from bottom to top. This results in an $O(N^2)$ algorithm.

Answer 2

The provided editorial is so hard to read. My solution is similar (or not?) to the provided one, but easier to understand.

Let $dp(u, i)$ be the number of topological sorts of subtree rooted at node $u$ such that node $u$ is placed at $i$-th position. The definition of $X$ and $Y$ are the same as the definition provided above.

Note that all the $X$ nodes has to be placed on the left and all the $Y$ nodes has to be placed on the right side of $u$ in a valid topological sort. Let's iterate through all the $X$ nodes; let the current one be $v$. We will try to merge the current topological sort with the topological sort of subtree rooted at $v$.

Denote $j$ as the position of $v$ in the topological sort we want to merge with. Let's fix some value $p$ - the position of $u$ after the current topological sort be merged. Now we have a inequation:

$$ S_u + S_v - p - (S_u - i) \ge S_v - i + 1 $$

$$ i + j \ge p + 1 $$

We also have $p \ge i$ and $j \le S_v$. Substituting this in the above inequation, we get:

$$ i + S_v \ge i + j \ge p + 1 \ge i + 1 $$

Note that $i - 1$ elements of the current topological sort are placed before $p$-th position, and $S_u - i$ elements of the current one are placed after $p$-th position. So we have the formula:

$$ dp(u, p) = dp(u, i) \cdot dp(v, j) \cdot \binom{p - 1}{i - 1} \cdot \binom{S_u + S_v - p}{S_u - i} $$

Since there are no "$j$" in the binomial part, we use prefix sum / suffix sum to get sum of $dp(v, j)$ over all $j$ such that $p + 1 - i \le j \le S_v$.

The same calculation can be done for all the $Y$ nodes. The answer of the problem is $\sum_{i=1}^{n} dp(1, i)$. The total time complexity is $O(n^2)$.