<p>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) &lt; p^{-1}(y)$). Let's call the <em>goodness</em> 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$).</p>

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

<p>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 <a href="https://cstheory.stackexchange.com/questions/19073/complexity-of-topological-sort-with-constrained-positions">this</a>, for instance, but at a glance I didn't manage to reduct anything classical to it.</p>

<p>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.</p>

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

CC BY-SA 4.0
2018-05-11T12:35:10.623Z
Are you assuming that the vertex $V$ is made of consecutive integers, i.e., $V = \{1, \ldots, n\}$ for some $n \in \mathbb{N}$?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2018-05-11T12:45:25.793Z
@a3nm Yes, exactly. (Whoah, it was two years ago. I still do not know the solution, though.)
Ivan Smirnov
CC BY-SA 4.0
2018-05-12T17:35:46.823Z
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.
Antoine Amarilli 'a3nm'
<cc.complexity-theory><np-hardness><directed-acyclic-graph><partial-order><topological-sorting>
NP-completeness of a specific topological sorting problem
Ivan Smirnov
# NP-completeness of a specific topological sorting problem

(Asked by: username_0 on 2016-09-26)

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](https://cstheory.stackexchange.com/questions/19073/complexity-of-topological-sort-with-constrained-positions), 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.

**Tags:** cc.complexity-theory, np-hardness, directed-acyclic-graph, partial-order, topological-sorting
> **Comments:**
> **username_1**: Are you assuming that the vertex $V$ is made of consecutive integers, i.e., $V = \{1, \ldots, n\}$ for some $n \in \mathbb{N}$?  
> **username_0**: @a3nm Yes, exactly. (Whoah, it was two years ago. I still do not know the solution, though.)  
> **username_1**: 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.  

---

## 0 answers

