Meta Research

We study a graph reordering problem motivated by compressing massive graphs such as social networks and inverted indexes. Given a graph, G = (V, E), the Minimum Logarithmic Arrangement problem is to find a permutation, π, of the vertices that minimizes

      ∑                  (1 + ⌊lg |π(u) − π(v)|⌋).
(u,v)∈E

This objective has been shown to be a good measure of how many bits are needed to encode the graph if the adjacency list of each vertex is encoded using relative positions of two consecutive neighbors under the π order in the list rather than using absolute indices or node identifiers, which requires at least lg n bits per edge. We show the first non-trivial approximation factor for this problem by giving a polynomial time O(log k)-approximation algorithm for graphs with treewidth k.