# Is this node permutation optimization NP-Hard?

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.

• Related question: cstheory.stackexchange.com/questions/38274 Mar 12 '21 at 22:20
• 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. Mar 14 '21 at 11:45
• 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$. Mar 15 '21 at 8:08
• The average degree is $2m/n$, so a minimum degree vertex has degree at most $2m/n$. Mar 15 '21 at 13:49
• 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. Mar 15 '21 at 16:19