1
$\begingroup$

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.

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

1 Answer 1

2
+25
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.