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

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 establish high-quality lower bounds that are efficiently computable. We build on the Akbari–Ghodrati–Jabalameli–Saghafian (AGJS) bound for digraphs by adapting refinement techniques used by (a) Selkow and Harant–Mohr and (b) Angel–Campigotto–Laforest in their respective improvements of the Caro–Wei bound for undirected graphs. First, inspired by (a), we prove a neighborhood-based refinement of the AGJS bound that incorporates local degree data of each vertex. Second, inspired by (b), we compute the variance of the size of a feedback vertex set returned by a randomized algorithm. This result, combined with the Bhatia–Davis inequality, yields a tighter lower bound than the AGJS bound.