YouKn0wWho's blog

By YouKn0wWho, 5 years ago, In English

I have three versions of this problem

Version 1
Version 2
Version 3
  • Vote: I like it
  • +96
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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<j$$$ and also there is an edge in $$$D$$$ between every $$$a_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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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

»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it

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).

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The first version can be solved in $$$O(2^n \cdot poly(n))$$$. The answer is $$$\frac{chromatic\ polynomial(-1)}{2^m}$$$.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$.