YouKn0wWho's blog

By YouKn0wWho, 21 month(s) ago,

I have three versions of this problem

Version 1
Version 2
Version 3

• +96

 » 21 month(s) ago, # |   +17 I think the 3rd version can be solved like this: We will count number of DAGs with $n$ vertices and $k$ edges. We will consider the lexicographically minimum topological sort(LMTS) of our DAG. Consider a permutation $a_1,...,a_n$. This permutation is every $D$'s LMTS if $D$'s edges are from $a_i$ to $a_j$ and $i a_{i+1}$.So using these lemmas we can do $dp_{i,j,k}$ as number of permutations of $i$ numbers such that the first element is $j$ and number of $a_x > a_{x+1}$ is $k$. Using these we can easily get the answer.
•  » » 21 month(s) ago, # ^ |   +38 Your criteria on topological sort being minimal is wrong, for example you say that for 312 being minimal only need 3->1 edge, which is wrong
 » 21 month(s) ago, # |   -13 Suggesting a version 1 solution. Let's solve the problem for a connected graph. If it's unconnected, we can solve the problem for all of its components independantly and then just output the union of the probability for all of them via a simple formula p(a or b) = p(a) + p(b) — p(a and b).Since our inital graph is connected and the resulting graph needs to be a DAG, it's gonna have a root. I call a root of such a DAG a node, which doesn't have any edges going in it. We can simply brute the root and orient all the edges from it, no two such orientations will intersect, which makes the implementation even easier. Complexity: O(nm).
•  » » 21 month(s) ago, # ^ |   0 Que?
 » 21 month(s) ago, # |   +1 The first version can be solved in $O(2^n \cdot poly(n))$. The answer is $\frac{chromatic\ polynomial(-1)}{2^m}$.
•  » » 21 month(s) ago, # ^ |   0 Or $1 - above$, probably this is better.
•  » » » 21 month(s) ago, # ^ |   +8
•  » » » » 21 month(s) ago, # ^ |   0 Thanks.
 » 21 month(s) ago, # |   0 The second and the third version might be solved by DP which would count DAGs. I think that we might group the vertices by (for example) the length of the longest path which ends in them and scan them by groups. So, let $DP[n][m][k]$ be the number of graphs with $n$ vertices, $m$ edges such that exactly $k$ of them have at least one longest path (longest in the whole graph) ending in them. To make a transition, we can connect each new vertex with any subset of old $n-k$ vertices and we need to connect it with any non-empty subset of old $k$ vertices. Hard to say if we can reduce the complexity to make it work for $n$ up to $100$.