Theoretical Computer Science

find the most similar topological ordering of a dag


Given a permutation $L$ of the $n$ vertices of the directed acyclic graph $G=(V,E)$.

Question: is it NP-hard to find the topological order of the $G$ that is the most similar to the given permutation $L$?

(The most similar is that the least number of elements' positions are changed.)

Note: the topological order means the $n$ elements should be placed according to the constraints in $G$.




Solution

It is NP-hard. The reduction is from $CLIQUE$, so suppose we are given an undirected graph $H$ on $n$ vertices and $m$ edges, with a parameter $k$, and our task is to decide whether $\omega(H)\ge k$. We will need some sufficiently large numbers $M\gg N \gg n$, where we need about $N=n^2$ and $M=n^3$.

The graph $G$ will have two disjoint parts. The first part will have $M+M^2$ vertices such that there is an arc from each of the $M$ vertices to each of the $M^2$ vertices. In the order $L$ the $M^2$ vertices will have position $M+1$ to $M^2+M$. Since $M$ is huge, this implies that any optimal solution starts with the $M$ vertices, followed by the $M^2$ vertices. From the $M$ vertices, some can be in good position. As we can put these arbitrarily, we can easily determine this optimum; denote it by $X$.

The second part of $G$ will encode $H$. For every vertex of $H$, $G$ will have $N$ vertices. In $L$ each of these will take one of the first $M$ positions. Because of our earlier observations, none of these can keep their original position in an optimal solution, so we should place them to make other vertices 'happy'. For every edge of $H$, $G$ will have exactly one vertex, with $2N$ arcs going into it, one from each copy corresponding to one of its end-vertices. In $L$ each of these will have position $M^2+M+kN+1$ to $M^2+M+kN+m$. Since after the first part of $G$, we have only $kN$ places left before these positions, and $N\gg n$, this means that at most as many of these $m$ vertices can be in position, as many edges can be spanned by $k$ vertices.

To summarize, we can have $M^2+X+\binom k2$ vertices of $G$ in the same position as in $L$ if and only if $\omega(H)\ge k$.

ps. Notice that $G$ has only two levels, i.e., its longest (directed) path has length one.





Comments (2)

  • +0 – I'm very sorry, due to my limited understanding, I did not fully understand your answer. For example, what does $kN$ mean, and the sentences "none of these can keep their original position in an optimal solution", and 'G will have exactly one vertex, with $2N$ arcs going into it, one from each copy corresponding to one of its end-vertices.' If you can spare your precious time to explain further, I will be very grateful to you. — Sep 02, 2020 at 13:51  
  • +0 – In the description $k\cdot N$ is just a number. The $k$ comes directly from the clique instance and the $N=n^2$ where $n$ is the number of vertices in the clique instance. 'None of these can keep their original position' is true because the first $M$ positions of the solutions must be occupied by the $M$ vertices of the "first part of the graph $G$". These $M$ vertices are in $L$ somewhere later but in the solution they must come before their $M^2$ many outneighbors which also belong to the first part of the graph $G$. — Oct 19, 2020 at 21:08