Exploiting Spanning Trees for Directed Acyclicity

Sergei Khargeliia, Danil Sagunov

We study the weighted case of the \textsc{Maximum Acyclic Subgraph (MAS)} problem, where each edge of a given directed graph has a positive weight assigned, and the task is to find…