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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.