0
$\begingroup$

I have learnt to solve topological ordering using $in-degree$ method where we have to take the vertices having in-degree $0$ at an instance and arrange them in that order.

For example consider this question asked in Graduate Aptitude Test in Engineering more commonly known as $GATE$ the entrance exam for $IIT$ $M.Tech$ in India. The question goes like this,

Find the number of topological ordering possible for the given graph-->

enter image description here

Here we can see that in-degree of A is 0 so we take $A$ as the stating vertex, then we have 2 options either $B$ or $C$, and so on.... The number of possible topological ordering in this case is $6$ as explained below

enter image description here

This method works well for these examples where the number of in-degree 0 vertices is less at a time, but how to solve problems where there are many number of 0 in-degree vertices as the one given below

enter image description here

I think combinatorics will come into picture in such cases, but I am unable to apply it properly. Any help will be highly appreciated.

$\endgroup$
1
$\begingroup$

Unfortunately, there is no "fast" way to count them generally as this problem is #P-Complete. This means that it is basically as hard as every counting version of NP-problems, and is likely not solvable in polynomial time.

For small examples such as this one you can come up with some ad-hoc counting technique however. In this case would try listing all permutations of E,F,G and see how many choices I have for the rest if I insert them in some order. Like this:

  • EFG: 1+2+4+6 = 13 (1 choice for A, then 2 for B, 4 for C, 6 for D)
  • EGF: 1+2+4+5 = 12 (in A,B,C,D order)
  • FEG: 1+2+4+5 = 12 (in B,C,A,D order)
  • FGE: 1+2+4+6 = 13 (in B,C,D,A order)
  • GEF: 1+2+4+5 = 12 (in D,C,A,B order)
  • GFE: 1+2+4+5 = 12 (in D,C,B,A order)

So in total 4*12 + 2*13 = 74 topological orderings (with some non-negligeable probability that I miscounted somewhere).

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