May 21, 2019
CORE, room b-135
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.