Consider $(V, E)$ be a DAG, and $p_1, \dots, p_n$ be its topological sorting (i.e. such permutation $p$ of $V$ that $\forall(x, y) \in E.\ p^{-1}(x) < p^{-1}(y)$). Let's call the goodness of $p$ a number of positions $i$ such that $p_i + 1 = p_{i+1}$ (the number of consecutive numbers which are also consecutive in $p$).

The problem itself: find a topological sorting with maximal goodness. Or, as a decision version: is there one with goodness at leask $k$?

The problem is clearly in NP, but I couldn't find out whether it is NP-hard or polynomially solvable. I could apply no type of a dynamic programming or flows or any other competitive programming technique. The problem itself looks like being NPC, reminding of this, for instance, but at a glance I didn't manage to reduct anything classical to it.

I googled for some related articles, but the best results I found were on NP-hardness of crossing number and optimal linear arrangement, which are somewhat related but do not help.

I wonder if this problem is classical or has some trivial solution which just eludes my mind.

  • $\begingroup$ Are you assuming that the vertex $V$ is made of consecutive integers, i.e., $V = \{1, \ldots, n\}$ for some $n \in \mathbb{N}$? $\endgroup$ – a3nm May 11 '18 at 12:35
  • $\begingroup$ @a3nm Yes, exactly. (Whoah, it was two years ago. I still do not know the solution, though.) $\endgroup$ – Ivan Smirnov May 11 '18 at 12:45
  • $\begingroup$ Thanks for clarifying. I thought a bit about the question and I have no idea... it's a very annoying problem. ;) I hope someone finds the answer. $\endgroup$ – a3nm May 12 '18 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.