Operations Research Seminar: Vladimir Protasov

The maximal acyclic subgraph problem and stability of positive dynamical systems

Vladimir Protasov, National Research University Higher School of Economics, Russia

The Maximal Acyclic Subgraph (MAS) is the problem of finding the closest (by the total number of cancelled edges) acyclic subgraph to a given directed graph.  This is known to be  NP-hard, and the best-known polynomial-time computable approximation factor for general graphs is ½ .
We spot the links of this problem to the problem of the nearest stable positive system, which was  intensively studied in the recent literature due to applications to mathematical economics, population dynamics, etc.  This allows us to apply  recent methods of stabilizing non-negative matrices to this problem.  We establish the quadratic rate of convergence of those methods, which justifies their efficiency. Applied to the MAS problem they give the same factor ½  and demonstrate a fast running time in practice for graphs of several thousands  of vertices.
Moreover, some related problems to MAS can be effectively solved by those methods.

A large part  of results presented in  the talk are obtained in a joint research with A.Cvetkovic.