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.