The directed circular arrangement problem

We consider the problem of embedding a directed graph onto evenly-spaced points on a circle while minimizing the total weighted edge length. We present the first poly-logarithmic approximation factor algorithm for this problem which yields an approximation factor of O(log n log log n), thus improving the previous Õ(√n) approximation factor. In order to achieve this, we introduce a new problem which we call the directed penalized linear arrangement. This problem generalizes both the directed feedback edge set problem and the directed linear arrangement problem. We present an O(log n log log n) approximation factor algorithm for this newly defined problem. Our solution uses two distinct directed metrics ("right" and "left") which together yield a lower bound on the value of an optimal solution. In addition, we define a sequence of new directed spreading metrics that are used for applying the algorithm recursively on smaller subgraphs. The new spreading metrics allow us to define an asymmetric region growing procedure that accounts simultaneously for both incoming and outgoing edges. To the best of our knowledge, this is the first time that a region growing procedure is defined in directed graphs that allows for such an accounting.