# Minimum feedback arc set for dense directed graph

This is really a matrix problem, but the theory I believe lies in graphs. Consider some matrix $$A$$ and permutation matrix $$P$$, where we define $$\tilde{A}:= PAP^T$$. I want to pick $$P$$ such that if $$\tilde{A} = L + D + U$$, for (strictly) lower triangular, diagonal, and (strictly) upper triangular pieces, respectively, I minimize $$\|U\|/\|L\|$$ in some norm (Frobenius, $$\ell^2$$,...). In some cases, $$A$$ may be a DAG (with self-loops on the diagonal), and so a topological sort would yield $$\|U\| = 0$$. In other cases, $$A$$ is symmetric, so regardless of $$P$$, we should always have $$\|U\|/\|L\| = 1$$. To solve this exactly I believe is NP-hard, but I just need a reasonable approximation that is cheap to compute (at least as cheap as computing direct $$A^{-1}$$, preferably much cheaper).

This is essentially a minimum feedback arc set problem, but approximating the FAS problem is typically posed by eliminating cycles. Here, $$A$$ is usually going to be dense/fully connected. Broadly, my question is if using FAS approximation algorithms makes sense on a fully connected graph, if certain methods may make more sense than others, or if there is a different/better way to pose this problem?

• In case this is of use to anyone else, I implemented one of the early algorithms from Eades et al. (citeseerx.ist.psu.edu/viewdoc/…) and applied it to random matrices, where I scale the lower and upper triangular parts by some constant, then randomly shuffle the matrix $P^TAP$. Overall it is quite reliable in providing good approximations and has the correct limiting behavior of doing a topological sort if $A$ is a DAG and of course having a ratio of 1 for a symmetric matrix. There are probably better more recent options, but this works well. – Ben Southworth Oct 8 '20 at 22:54