Maximal acyclic subgraphs and closest stable matrices

We develop a matrix approach to the maximal acyclic subgraph (MAS) problem by reducing it to find the closest nilpotent matrix to the matrix of the graph. Using recent results on the closest Schur stable systems and on minimizing the spectral radius over special sets of nonnegative matrices, we obtain an algorithm for finding an approximate solution of the MAS problem. Numerical results for graphs from 50 to 1500 vertices demonstrate its fast convergence and give a rate of approximation larger than 0.6 in most cases. This method also gives the precise solution for the following weakened version of MAS: find the minimal r such that the graph can be made acyclic by cutting at most r incoming edges from each vertex. We also consider several modifications in the case when each vertex is assigned its own maximal number ri of cut edges, and some of the edges are ``untouchable."" Some applications are discussed.