On the Approximability of Digraph Ordering

Sreyash Kenkre, Vinayaka Pandit, Manish Purohit +1

Given an n-vertex digraph D = (V, A) the Max-k-Ordering problem is to compute a labeling $\ell :V\to [k]$ maximizing the number of forward edges, i.e. edges (u,v) such that $\ell…