Improved lower bounds for the maximum order of an induced acyclic subgraph

Shamil Asgarli, Donald Falkenhagen, Kaya Hoshi

Computing the cardinality of a maximum induced acyclic vertex set in a digraph is NP-hard. Since finding an exact solution is computationally difficult, a fruitful approach is to e…