Show that a problem about permutations is NP-Complete

Question

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.

Answer 1

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.