• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Maximal acyclic subgraphs and closest stable matrices

Protasov V. Y., Cvetkovic A.

We develop a matrix approach to the Maximal Acyclic Subgraph (MAS) problem by reducing it to finding the closest nilpotent matrix to the matrix of the graph. Using recent results on the closest Schur stable systems and on minimising the spectral radius over special sets of non-negative matrices we obtain an algorithm for finding an approximate solution of MAS. Numerical results for graphs from $50$ to $1500$ vertices demonstrate its fast convergence and give the rate of approximation in most cases larger than $0.6$. The same method 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.  Several modifications,  when each vertex is assigned with its own maximal number~$r_i$ of cut edges, when some of edges are ``untouchable'', are also considered. Some applications are discussed.