6
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Here are two other posts about NP-hard problems that ask for a topological ordering of a DAG that is optimal by some measure: cstheory.stackexchange.com/questions/31975/…, cstheory.stackexchange.com/questions/36230/…. Maybe these will give some ideas for coming up with an NP-hardness proof. $\endgroup$ – Neal Young Jul 27 '20 at 14:01
  • $\begingroup$ Thanks a lot for your help ! I will study these two issues carefully to see if there is a connection. $\endgroup$ – 2016310588 Jul 28 '20 at 1:12
  • 2
    $\begingroup$ I'm not entirely sure which metric you're using for "most similar". When evaluating a potential ordering $O$, do you (a) try to minimize the number of positions where $O$ is different from $L$, (b) try to minimize the number of swaps needed to get from $O$ to $L$, or (c) something else? Different parts of your question point to either (a) or (b), but they are different metrics, so the answer can depend on which you meant. $\endgroup$ – Mikhail Rudoy Jul 29 '20 at 13:10
  • 4
    $\begingroup$ So just to make sure I have the idea right, here's the problem I think you are asking about: you are given a DAG with $n$ vertices labeled $1$ through $n$; the goal is to rearrange the labels such that under the new labeling scheme, the order implied by the new labels is a topological sort of the DAG and such that the number of vertices keeping their original labels is maximized. Is that right? Thanks! $\endgroup$ – Mikhail Rudoy Jul 29 '20 at 16:11
  • 2
    $\begingroup$ @MikhailRudoy By the way, our purpose is not to find the least number of label exchanges (or, swaps) but to find the least number of vertices whose label has been changed. $\endgroup$ – 2016310588 Jul 30 '20 at 1:37
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – 2016310588 Sep 2 '20 at 13:51
  • $\begingroup$ 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$. $\endgroup$ – Christian Komusiewicz Oct 19 '20 at 21:08
0
$\begingroup$

If I understood you question correctly, this has been studied before, or in the context of partial orders, under the name of nearest neighbor Kendall tau (NNKT) problem for a total and a partial order. Given a DAG $D$ you can find its transitive closure $C$ and define an order where $u < v$ iff $(u,v)$ is an arc of $C$. Similarly, a permutation can be seen as a total order.

Given a partial order $P$ and a total order $T$ of a given set, the objective of NNKT is to find a linear extension of $P$ that has as few inversions as possible in comparison with $T$. This has been shown to be NP-complete by Brandenburg et al [1]. Some related questions were considered more recently in [2]. If these are not exactly the same problem, I hope at least it shed some lite on your question.

[1] Brandenburg, Franz J.; Gleißner, Andreas; Hofmeier, Andreas, Comparing and aggregating partial orders with Kendall tau distances, Discrete Math. Algorithms Appl. 5, No. 2, Article ID 1360003, 25 p. (2013). ZBL1294.06002.

[2] da Silva, Rodrigo Ferreira; Urrutia, Sebastián; dos Santos, Vinícius Fernandes, One-sided weak dominance drawing, Theor. Comput. Sci. 757, 36-43 (2019). ZBL1422.68186.

$\endgroup$
  • $\begingroup$ But the OP asks, given a partial order P and a total order T, for a total order T' that is a linear extension of P and minimizes the number of vertices v such that v's rank in T' differs from its rank in T. In general, this is not the same as minimizing the number of inversions of T w.r.t. T' (the problem you give references for). $\endgroup$ – Neal Young Aug 6 '20 at 19:47
  • 1
    $\begingroup$ Thank you for your guidance. I have studied the articles you listed, but found that the problem is different from mine. Nevertheless, your answer did give me some ideas, thank you very much. $\endgroup$ – 2016310588 Aug 13 '20 at 1:26

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.