<p>We have a matrix <span class="math-container">$M$</span> of size <span class="math-container">$n$</span> by <span class="math-container">$n$</span> where
<span class="math-container">$M[i][j] \ge 0$</span> and <span class="math-container">$M[i][i] = 0$</span>.</p>
<p>We want to create a permutation of integers <span class="math-container">$[1,\dots,N]$</span>, like <span class="math-container">$\langle P_1, P_2,\dots,P_n \rangle$</span>, such that</p>
<p><span class="math-container">$$
\sum_{i=1}^{N} \sum_{j=i}^{N} M[P_i][P_j]
$$</span></p>
<p>is maximized.</p>
<p>Of course we can try a greedy algorithm to create the permutation <span class="math-container">$P$</span> step by step, but what I am looking for at this time is whether this problem is NP-Complete or not. And if so, is there any approximation known for it?</p>
<p>For Fun: Here is what <a href="https://chatgpt.com/share/eaea7cc0-7b78-421d-ab56-b8ffa1d9960c" rel="nofollow noreferrer">ChatGPT</a> think about it.</p>
<p>Edit1. The problem can be described as:
We have n soccer teams. These teams played some random matches against each other (Team 1 could just have one game against Team 2  while Team 3 having 100 games against Team 4, etc). Entry <span class="math-container">$M[i][j]$</span> represents how many times team <span class="math-container">$i$</span> won team <span class="math-container">$j$</span>. We want to find a ranking <span class="math-container">$P$</span>, for the teams, such that it maximizes the stated summation (which our definition of how well the ranking is).</p>

CC BY-SA 4.0
2024-06-13T19:53:19.190Z
If I understand the question correctly, then this seems to be essentially Directed Feedback Vertex Set also known as Maximum Acyclic Subgraph. The summation is over forward arcs for the ordering implied by the permutation, so if the aim is to maximize the sum then we directly get Maximum Acyclic Subgraph, if we want to minimize the sum, then the solution ordering is the reverse of an optimal one for Maximum Acyclic Subgraph.
Christian Komusiewicz
CC BY-SA 4.0
2024-06-13T20:53:38.950Z
@ChristianKomusiewicz The problem does not require for the transformed graph to be Acyclic.
Amir
CC BY-SA 4.0
2024-06-15T01:43:28.680Z
Please don't use "Edit1. more information".  Instead, please revise the question so it reads well for someone who encounters it for the first time.  See https://cs.meta.stackexchange.com/q/657/755.  What ChatGPT thinks is irrelevant and can be deleted.
D.W.
CC BY-SA 4.0
2024-06-15T15:01:48.480Z
As @ChristianKomusiewicz noted, this is the Maximum Weighted Acyclic Subgraph problem. OP should check the definitions and verify that this is indeed a correct interpretation. Maximum Weighted Acyclic Subgraph is used in ranking problems.
Chandra Chekuri
<ds.algorithms><approximation-algorithms><time-complexity><np-complete>
Is finding the best permutation an NP-Complete problem?
Amir
# Is finding the best permutation an NP-Complete problem?

(Asked by: username_0 on 2024-06-13)

We have a matrix $M$ of size $n$ by $n$ where
$M[i][j] \ge 0$ and $M[i][i] = 0$.

We want to create a permutation of integers $[1,\dots,N]$, like $\langle P\_1, P\_2,\dots,P\_n \rangle$, such that

$$
\sum\_{i=1}^{N} \sum\_{j=i}^{N} M[P\_i][P\_j]
$$

is maximized.

Of course we can try a greedy algorithm to create the permutation $P$ step by step, but what I am looking for at this time is whether this problem is NP-Complete or not. And if so, is there any approximation known for it?

For Fun: Here is what [ChatGPT](https://chatgpt.com/share/eaea7cc0-7b78-421d-ab56-b8ffa1d9960c) think about it.

Edit1. The problem can be described as:
We have n soccer teams. These teams played some random matches against each other (Team 1 could just have one game against Team 2 while Team 3 having 100 games against Team 4, etc). Entry $M[i][j]$ represents how many times team $i$ won team $j$. We want to find a ranking $P$, for the teams, such that it maximizes the stated summation (which our definition of how well the ranking is).

**Tags:** ds.algorithms, approximation-algorithms, time-complexity, np-complete

> **Comments:**
> **username_1**: If I understand the question correctly, then this seems to be essentially Directed Feedback Vertex Set also known as Maximum Acyclic Subgraph. The summation is over forward arcs for the ordering implied by the permutation, so if the aim is to maximize the sum then we directly get Maximum Acyclic Subgraph, if we want to minimize the sum, then the solution ordering is the reverse of an optimal one for Maximum Acyclic Subgraph.  
> **username_0**: @ChristianKomusiewicz The problem does not require for the transformed graph to be Acyclic.  
> **username_2**: Please don't use "Edit1. more information".  Instead, please revise the question so it reads well for someone who encounters it for the first time.  See https://cs.meta.stackexchange.com/q/657/755.  What ChatGPT thinks is irrelevant and can be deleted.  
> **username_3**: As @ChristianKomusiewicz noted, this is the Maximum Weighted Acyclic Subgraph problem. OP should check the definitions and verify that this is indeed a correct interpretation. Maximum Weighted Acyclic Subgraph is used in ranking problems.  

---

## 0 answers

