<p>The proof that this problem is actually NP-hard is available in the Annex B of this <a href="https://arxiv.org/pdf/2203.04774.pdf" rel="nofollow noreferrer">paper</a> (thanks to <a href="https://cstheory.stackexchange.com/users/45122/louis">Louis</a>' work).</p>

CC BY-SA 4.0
2022-12-04T10:11:05.983Z
2022-12-04T10:11:05.983Z
Alt-Tab
<p>Let <span class="math-container">$G=(V,E)$</span> be an undirected graph and let <span class="math-container">$\pi$</span> be a permutation of the vertices in <span class="math-container">$V$</span>. For a node <span class="math-container">$v\in V$</span>, we denote by <span class="math-container">$\text{succ}_{\pi}(v)$</span> the set of neighbors of <span class="math-container">$v$</span> that occur after <span class="math-container">$v$</span> in the permutation <span class="math-container">$\pi$</span>.</p>
<p>Is the following optimization problem NP-hard?</p>
<blockquote>
<p><strong>Problem.</strong> For a given undirected graph <span class="math-container">$G=(V,E)$</span>, find a
permutation <span class="math-container">$\pi$</span> of the vertices that minimizes the objective value
<span class="math-container">$\sum_\limits{u\in V} ~\left|\text{succ}_{\pi}(u)\right|^2$</span>.</p>
</blockquote>
<p><strong>Motivation:</strong> The following algorithm lists all triangles in the input graph in linear memory and in time <span class="math-container">$O(\sum_\limits{u\in V} ~\left| \text{succ}_{\pi}(u) \right|^2+m+n)$</span> where <span class="math-container">$m$</span> is the number of edges and <span class="math-container">$n$</span> is the number of nodes.</p>
<pre>
For each node u:  
  For each pair of successors v,w of node u:  
    If edge v,w is in the input undirected graph:  
      output triangle u,v,w
</pre>
<p><em>Implementation details:</em> the graph should be stored in a CSR-like format and, in addition, the edges should be put in a hashtable.</p>
<p>Finding the ordering that minimizes the quantity should lead to a faster algorithm.</p>

CC BY-SA 4.0
2021-03-12T22:20:49.753Z
Related question: https://cstheory.stackexchange.com/questions/38274/
maxdan94
CC BY-SA 4.0
2021-03-14T11:45:48.030Z
Note that if instead of minimizing $\sum_{v\in V} |\mathrm{succ}(v)|^2$ you minimize $\max_{v\in V} |\mathrm{succ}(v)|$, this problem becomes equivalent to finding the degeneracy of the graph and finding a corresponding minimizing permutation, which can be solved in linear time.
user3209423940248
CC BY-SA 4.0
2021-03-14T12:38:56.993Z
Yes that is correct! And leads to a $O(\delta^2n+m+n)$ time algorithm for listing triangles, where $\delta$ is the degeneracy of the graph.
maxdan94
CC BY-SA 4.0
2021-03-15T08:08:12.713Z
For your application, it should be sufficient that the degeneracy ordering is a 4-approximation: we have a lower bound of $lb = m^2/n$, where $m$ is the number of edges and $n$ the number of nodes. By removing the vertex of the smallest degree our cost increases by at most $(2m/n)^2 = 4m^2/n^2 = 4lb/n$.
Laakeri
CC BY-SA 4.0
2021-03-15T13:15:25.440Z
@Laakeri yes indeed: it is a constant factor approximation so the constant factor disappears inside the big-oh. Still I would like to know if the optimization can be solved exactly and efficiently. Why the increase is at most $(2m/n)^2$?
maxdan94
CC BY-SA 4.0
2021-03-15T13:49:46.403Z
The average degree is $2m/n$, so a minimum degree vertex has degree at most $2m/n$.
Laakeri
CC BY-SA 4.0
2021-03-15T15:43:10.307Z
But this is true for the first removal, after that the minimum degree can be larger than the $2m/n$ of the input graph, no? For instance, assume the graph consists of a large clique and many nodes of degree 1 (connected pairs), when you star pealing the large clique de degrees can be larger than the average degree of the input graph. What did I miss?
maxdan94
CC BY-SA 4.0
2021-03-15T16:19:49.643Z
Yes, but in the further steps also $m^2/n$ (of the modified graph) is a lower bound. This lower bound can improve in the progress, but nevertheless holds also for the original graph because we are always dealing with a subgraph of the original graph.
Laakeri
CC BY-SA 4.0
2021-03-16T14:26:16.817Z
Yes that is correct. Thanks!
maxdan94
CC BY-SA 4.0
2021-03-18T19:55:36.063Z
related: https://mathoverflow.net/questions/383368
maxdan94
CC BY-SA 4.0
2021-05-27T20:52:27.627Z
Not a proof but an argument which is in favor of NP-hardness: in this [post](https://cstheory.stackexchange.com/questions/48572/is-that-edge-orientation-optimization-problem-np-hard) @Louis gave a polynomial algorithm to solve a closely related problem. 
Briefly, the problem is to find the edge directions that minimize $ \sum _{u \in V} (d_{out}(u))^2 $ and the algorithm consists in flipping directions on paths when it decreases this quantity. Adapting it to our question (instead of flipping path, permute node labels along the path) it can be stuck in a local minimum.
Alt-Tab
<graph-theory><graph-algorithms><np-hardness><optimization>
Is this node permutation optimization NP-Hard?
maxdan94
# Is this node permutation optimization NP-Hard?

(Asked by: username_0 on 2021-03-12)

Let $G=(V,E)$ be an undirected graph and let $\pi$ be a permutation of the vertices in $V$. For a node $v\in V$, we denote by $\text{succ}_{\pi}(v)$ the set of neighbors of $v$ that occur after $v$ in the permutation $\pi$.
Is the following optimization problem NP-hard?

Problem. For a given undirected graph $G=(V,E)$, find a
permutation $\pi$ of the vertices that minimizes the objective value
$\sum_\limits{u\in V} ~\left|\text{succ}_{\pi}(u)\right|^2$.

Motivation: The following algorithm lists all triangles in the input graph in linear memory and in time $O(\sum_\limits{u\in V} ~\left| \text{succ}_{\pi}(u) \right|^2+m+n)$ where $m$ is the number of edges and $n$ is the number of nodes.

For each node u:  
  For each pair of successors v,w of node u:  
    If edge v,w is in the input undirected graph:  
      output triangle u,v,w

Implementation details: the graph should be stored in a CSR-like format and, in addition, the edges should be put in a hashtable.
Finding the ordering that minimizes the quantity should lead to a faster algorithm.

**Tags:** graph-theory, graph-algorithms, np-hardness, optimization

> **Comments:**
> **username_0**: Related question: https://cstheory.stackexchange.com/questions/38274/  
> **username_1**: Note that if instead of minimizing $\sum_{v\in V} |\mathrm{succ}(v)|^2$ you minimize $\max_{v\in V} |\mathrm{succ}(v)|$, this problem becomes equivalent to finding the degeneracy of the graph and finding a corresponding minimizing permutation, which can be solved in linear time.  
> **username_0**: Yes that is correct! And leads to a $O(\delta^2n+m+n)$ time algorithm for listing triangles, where $\delta$ is the degeneracy of the graph.  
> **username_2**: For your application, it should be sufficient that the degeneracy ordering is a 4-approximation: we have a lower bound of $lb = m^2/n$, where $m$ is the number of edges and $n$ the number of nodes. By removing the vertex of the smallest degree our cost increases by at most $(2m/n)^2 = 4m^2/n^2 = 4lb/n$.  
> **username_0**: @username_2 yes indeed: it is a constant factor approximation so the constant factor disappears inside the big-oh. Still I would like to know if the optimization can be solved exactly and efficiently. Why the increase is at most $(2m/n)^2$?  
> **username_2**: The average degree is $2m/n$, so a minimum degree vertex has degree at most $2m/n$.  
> **username_0**: But this is true for the first removal, after that the minimum degree can be larger than the $2m/n$ of the input graph, no? For instance, assume the graph consists of a large clique and many nodes of degree 1 (connected pairs), when you star pealing the large clique de degrees can be larger than the average degree of the input graph. What did I miss?  
> **username_2**: Yes, but in the further steps also $m^2/n$ (of the modified graph) is a lower bound. This lower bound can improve in the progress, but nevertheless holds also for the original graph because we are always dealing with a subgraph of the original graph.  
> **username_0**: Yes that is correct. Thanks!  
> **username_0**: related: https://mathoverflow.net/questions/383368  
> **username_3**: Not a proof but an argument which is in favor of NP-hardness: in this [post](https://cstheory.stackexchange.com/questions/48572/is-that-edge-orientation-optimization-problem-np-hard) @Louis gave a polynomial algorithm to solve a closely related problem.  Briefly, the problem is to find the edge directions that minimize $ \sum _{u \in V} (d_{out}(u))^2 $ and the algorithm consists in flipping directions on paths when it decreases this quantity. Adapting it to our question (instead of flipping path, permute node labels along the path) it can be stuck in a local minimum.  

---

## 1 answers

### Answer by username_3 on 2022-12-04. Score: 1

The proof that this problem is actually NP-hard is available in the Annex B of this [paper](https://arxiv.org/pdf/2203.04774.pdf) (thanks to [Louis](https://cstheory.stackexchange.com/users/45122/louis)' work).


---

