# Show that a problem about permutations is NP-Complete

I want to prove that the following problem is NP-Complete.

Input: Set $$S = \{s_1, \dots, s_n \}$$, set $$T \subset S \times S$$, that contains ordered pairs $$(s_i, s_j) : s_i \neq s_j$$, and an integer $$k \geq 1$$.

Output: Is there a permutation $$p:\{1, \dots, n\} \rightarrow \{1, \dots, n\}$$ for the elements of $$S$$, so that there are at most $$k$$ pairs $$(s_i, s_j) \in T$$ such that $$p(i) > p(j)$$ (i.e. pairs that are "inconsistent" with the order of the permutation)?

Due to the form of $$S$$ and $$T$$, which are reminiscent of vertices and edges, I tried to reduce a known NP-Complete problem with Graphs to the current one, but without success.

I tried using the Vertex Cover and the Sparse Subgraph problems (which may be wrong choices), by setting $$S = V$$ (vertices) and $$T = E$$ (edges) and tried to "encode" the presence of an edge as an "inconsistent" pair (as above mentioned). However, I cannot see how to use a property concerning permutations. I was also wondering if it is a wrong idea anyway to use reduction based on graphs.

I would appreciate any help.

• Take a look at the minimum feedback arc set problem. Jan 30, 2022 at 11:55
• Thank you very much. Indeed it can be reduced to my problem as I see. Jan 31, 2022 at 3:36

The decision version of the minimum feedback arc set problem is as follows: given a directed graph $$G=(V,E)$$ with no self-loops and an integer $$k$$, decide whether there is a set $$F \subseteq E$$ of edges such that $$|F| \le k$$ and the graph $$G - F = (V, E \setminus F)$$ is acyclic.
This is a well-known NP-Complete problem. To get an instance of the problem in the question pick $$S = V$$, and $$T=E$$ (the value of $$k$$ stays the same).
If there is a solution $$F$$ to the minimum feedback arc set instance, then $$G-F$$ is acyclic and hence there is a topological ordering $$v_1, \dots, v_n$$ of the vertices in $$V$$. Choosing $$v_i$$ as the $$i$$-th element of the permutation $$p$$ we have that all edges $$(v_i, v_j) \in E \setminus F$$ satisfy $$i < j$$, and hence there are at most $$|F| \le k$$ pairs in $$T$$ that are "inconsistent" with $$p$$.
Conversely, if there permutation $$p$$ with at most $$k$$ "inconsistencies" for the instance of the problem in the question, then we can choose $$F$$ as the set of all edges $$(u,v)$$ such that $$u$$ follows $$v$$ in $$p$$. This ensures that the permutation of $$S$$ is exactly a topological ordering of $$G-F$$, i.e., $$G-F$$ is acyclic. Since $$|F| \le k$$, $$F$$ is a solution to the minimum feedback arc set instance.