3
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

The proof that this problem is actually NP-hard is available in the Annex B of this paper (thanks to Louis' work).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.