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.
