小瓢虫传媒

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.