3

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.

maxdan94
  • 563
  • 2
  • 10
  • Related question: https://cstheory.stackexchange.com/questions/38274/ – maxdan94 Mar 12 '21 at 22:20
  • 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. – user3209423940248 Mar 14 '21 at 11:45
  • 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 Mar 14 '21 at 12:38
  • 1
    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 Mar 15 '21 at 08:08
  • @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 Mar 15 '21 at 13:15
  • 1
    The average degree is $2m/n$, so a minimum degree vertex has degree at most $2m/n$. – Laakeri Mar 15 '21 at 13:49
  • 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 Mar 15 '21 at 15:43
  • 1
    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 Mar 15 '21 at 16:19
  • Yes that is correct. Thanks! – maxdan94 Mar 16 '21 at 14:26
  • related: https://mathoverflow.net/questions/383368 – maxdan94 Mar 18 '21 at 19:55
  • Not a proof but an argument which is in favor of NP-hardness: in this post @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 May 27 '21 at 20:52

1 Answers1

1

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

Alt-Tab
  • 121
  • 7