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

Donald Falkenhagen; Kaya Hoshi; Shamil Asgarli

arxiv: 2511.02819 · v3 · submitted 2025-11-04 · 🧮 math.CO

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

Shamil Asgarli , Donald Falkenhagen , Kaya Hoshi This is my paper

Pith reviewed 2026-05-18 00:35 UTC · model grok-4.3

classification 🧮 math.CO

keywords induced acyclic subgraphlower boundsdigraphsfeedback vertex setBhatia-Davis inequalityrandomized algorithmsgraph theory

0 comments

The pith

A variance-based refinement using the Bhatia-Davis inequality yields a strictly tighter lower bound than the AGJS bound for the maximum induced acyclic subgraph in a digraph.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops two improvements to the AGJS lower bound on the size of a largest induced acyclic vertex set in directed graphs. One incorporates local neighborhood degree information for each vertex. The other computes the variance of the output size from a randomized feedback vertex set algorithm and applies the Bhatia-Davis inequality to strengthen the guarantee beyond the original expectation. Readers care because the exact maximum is NP-hard to compute, so stronger efficiently obtainable lower bounds aid both practical estimation in networks and theoretical understanding of directed graph structure.

Core claim

The authors prove that the lower bound on the order of a maximum induced acyclic subgraph is at least the expectation of the size of a random feedback vertex set plus a positive term derived from its variance through the Bhatia-Davis inequality, producing a strictly better estimate than the AGJS bound based on expectation alone.

What carries the argument

The variance of the size of a feedback vertex set returned by a randomized algorithm, refined via the Bhatia-Davis inequality to tighten the probabilistic lower bound.

If this is right

A neighborhood refinement adjusts the bound using local degree data of each vertex.
The variance refinement is strictly stronger whenever the variance is positive.
Both new bounds remain polynomial-time computable.
The methods adapt undirected-graph refinement ideas to the directed setting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar variance or moment-based refinements could apply to other induced-subgraph problems in digraphs.
The technique points toward using concentration inequalities for tighter probabilistic guarantees in related graph algorithms.
Practical tests on large digraphs could reveal how much the new bounds improve over AGJS in applications.

Load-bearing premise

The randomized algorithm for a feedback vertex set has a variance that can be bounded so the resulting expression exceeds the pure-expectation AGJS guarantee.

What would settle it

An explicit digraph where direct computation shows the variance-based bound equals or falls below the AGJS value, or where the Bhatia-Davis application does not produce the claimed improvement.

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper adapts two undirected-graph refinements to the AGJS bound and claims both give strictly better explicit lower bounds on maximum induced acyclic sets in digraphs.

read the letter

This paper refines the AGJS lower bound for the size of a largest induced acyclic vertex set in a digraph with two adaptations from the undirected Caro-Wei literature. The first pulls in local neighborhood degree data for each vertex. The second computes the variance of the size of a random feedback vertex set and feeds it through the Bhatia-Davis inequality. Both steps are new in the directed setting and follow the same probabilistic counting that worked in the undirected case. The neighborhood version should improve the bound whenever degrees vary, which is the typical situation. The variance version is the one that requires care. Bhatia-Davis supplies an upper bound on variance, so the algebra must still be checked to confirm that the final closed-form expression is always at least as large as AGJS and strictly larger on some instances. The abstract asserts this holds, but the letter should include the explicit comparison and a small example where the numerical gain is visible. The derivations use only standard inequalities and graph counting, with no fitted constants or circular steps. The work is aimed at people who need computable lower bounds for feedback vertex set or related digraph problems. A reader interested in probabilistic refinements of Caro-Wei-style bounds will find the directed versions worth seeing. It deserves peer review because the claims are modest, the techniques are checkable, and the potential gap in the variance step is narrow enough that referees can settle it quickly.

Referee Report

2 major / 2 minor

Summary. The manuscript claims two improvements to the AGJS lower bound on the size of a maximum induced acyclic vertex set in a digraph. The first is a neighborhood-based refinement that incorporates local degree information for each vertex, adapting techniques from Selkow and Harant-Mohr. The second computes the variance of the size of a random feedback vertex set produced by a randomized algorithm and combines it with the Bhatia-Davis inequality to obtain a strictly tighter explicit lower bound than the original AGJS expectation-based guarantee.

Significance. If the algebraic comparison establishing strict improvement holds, the variance-based refinement would constitute a useful strengthening of existing probabilistic bounds for an NP-hard digraph problem, extending established Caro-Wei-style refinements from the undirected case. The neighborhood refinement is a natural local improvement and adds value when degree sequences are available.

major comments (2)

[Abstract and § on variance refinement] Abstract (paragraph on variance computation) and the section presenting the second refinement: the manuscript must exhibit the explicit closed-form lower-bound expression obtained after substituting the Bhatia-Davis upper bound on Var(S) and verify algebraically that the resulting quantity is strictly larger than the AGJS bound for every digraph. Because Bhatia-Davis supplies only an upper estimate on variance, any refinement term that increases with Var(S) yields at best an upper estimate on the improvement; the direction and strictness of the final inequality therefore require direct verification rather than being left implicit.
[Section describing the randomized algorithm and variance calculation] The randomized algorithm for the feedback vertex set is invoked to produce both the expectation (recovering AGJS) and the variance term. The manuscript should state the precise probability distribution used for the random set and confirm that the variance expression is computed exactly (or bounded in a way that preserves the strict improvement) rather than relying solely on the Bhatia-Davis envelope for the final numerical comparison.

minor comments (2)

[Introduction and references] Ensure that the bibliography entries for the cited works of Selkow, Harant-Mohr, and Angel-Campigotto-Laforest are complete and that the precise statements being adapted are referenced with page or theorem numbers.
[Section on the second refinement] Clarify the notation for the random variable S (size of the feedback vertex set or its complement) at first use to avoid ambiguity when the variance is introduced.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and will revise the paper to incorporate the requested explicit derivations, statements, and algebraic verifications.

read point-by-point responses

Referee: [Abstract and § on variance refinement] Abstract (paragraph on variance computation) and the section presenting the second refinement: the manuscript must exhibit the explicit closed-form lower-bound expression obtained after substituting the Bhatia-Davis upper bound on Var(S) and verify algebraically that the resulting quantity is strictly larger than the AGJS bound for every digraph. Because Bhatia-Davis supplies only an upper estimate on variance, any refinement term that increases with Var(S) yields at best an upper estimate on the improvement; the direction and strictness of the final inequality therefore require direct verification rather than being left implicit.

Authors: We agree that the manuscript should present the explicit closed-form expression and provide an algebraic verification of the strict improvement. In the revised version we will substitute the Bhatia-Davis upper bound on variance into our expression for the lower bound on the maximum induced acyclic set and display the resulting closed-form formula. We will then prove algebraically, by direct term-by-term comparison after clearing denominators, that the new quantity is strictly larger than the AGJS bound whenever the variance is positive (i.e., for every digraph that is not a disjoint union of isolated vertices). Although Bhatia-Davis supplies an upper bound on Var(S), the refinement we obtain is still a valid lower bound; the algebraic comparison shows that even this conservative estimate exceeds the original AGJS expectation for all non-trivial digraphs. revision: yes
Referee: [Section describing the randomized algorithm and variance calculation] The randomized algorithm for the feedback vertex set is invoked to produce both the expectation (recovering AGJS) and the variance term. The manuscript should state the precise probability distribution used for the random set and confirm that the variance expression is computed exactly (or bounded in a way that preserves the strict improvement) rather than relying solely on the Bhatia-Davis envelope for the final numerical comparison.

Authors: We will revise the relevant section to state explicitly that the randomized algorithm selects each vertex v independently with probability 1/(1 + d^+(v)), where d^+(v) denotes the out-degree of v; this distribution yields the AGJS expectation as its mean. Because the indicators are independent, the variance is computed exactly as the sum over v of p_v(1 - p_v). We will add a sentence confirming that this exact variance expression is inserted into the Bhatia-Davis inequality and that the resulting lower bound is shown algebraically to be strictly stronger than AGJS without any numerical checks. The algebraic verification already accounts for the upper bound on variance supplied by Bhatia-Davis, thereby preserving the strict improvement in the general case. revision: yes

Circularity Check

0 steps flagged

No circularity; bounds derived from explicit variance computation and external inequalities

full rationale

The paper computes an explicit expression for the variance of a randomized feedback vertex set size and combines it with the Bhatia-Davis inequality (an external result) to refine the AGJS expectation-based lower bound. No step reduces a claimed prediction or first-principles result to a fitted parameter, self-defined quantity, or self-citation chain by construction. The neighborhood refinement and variance step are presented as direct adaptations of cited external techniques (Selkow/Harant-Mohr and Angel-Campigotto-Laforest) without importing uniqueness theorems or ansatzes from the authors' prior work. The derivation remains self-contained against standard probabilistic and graph-theoretic counting arguments.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard directed-graph definitions and the validity of the Bhatia-Davis inequality; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)

standard math Standard properties of directed graphs and induced subgraphs hold.
Invoked throughout the bound derivations.
standard math Bhatia-Davis inequality applies to the random variable representing feedback vertex set size.
Used to obtain the second tighter bound.

pith-pipeline@v0.9.0 · 5696 in / 1203 out tokens · 25210 ms · 2026-05-18T00:35:54.391023+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

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.
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 5.1 ... # —α(D) ≥ ∑ ρ_D(v) + Var(|S|) / (∑ ρ_D(v) − c) − c

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages · 1 internal anchor

[1]

Chromatic Number and Dichromatic Polynomial of Digraphs

S. Akbari, A. H. Ghodrati, A. Jabalameli, and M. Saghafian,Chromatic number and dichromatic polynomial of digraphs, arXiv preprint (2017), 1–13, Available athttps://arxiv.org/abs/1711.06293

work page internal anchor Pith review Pith/arXiv arXiv 2017
[2]

Angel, R

E. Angel, R. Campigotto, and C. Laforest,A new lower bound on the independence number of graphs, Discrete Appl. Math.161(2013), no. 6, 847–852. 19

work page 2013
[3]

Bhatia and C

R. Bhatia and C. Davis,A Better Bound on the Variance, The American Mathematical Monthly107(2000), no. 4, 353–357

work page 2000
[4]

Caro,New results on the independence number, Tech

Y. Caro,New results on the independence number, Tech. report, Tel-Aviv University, 1979

work page 1979
[5]

Math.159(2011), no

Hermann Gruber,Bounding the feedback vertex number of digraphs in terms of vertex degrees, Discrete Appl. Math.159(2011), no. 8, 872–875. MR 2782647

work page 2011
[6]

Harant and S

J. Harant and S. Mohr,On Selkow’s bound on the independence number of graphs, Discuss. Math. Graph Theory (2019), no. 3, 655–657

work page 2019
[7]

3, 265–270

Víctor Neumann-Lara,The dichromatic number of a digraph, Journal of Combinatorial Theory, Series B33(1982), no. 3, 265–270

work page 1982
[8]

S. M. Selkow,A probabilistic lower bound on the independence number of graphs, Discrete Mathematics132(1994), no. 1-3, 363–365

work page 1994
[9]

V. K. Wei,A lower bound on the stability number of a simple graph, Tech. Report 81-11217-9, Bell Laboratories, Murray Hill, NJ, 1981. Dept. of Mathematics & Computer Science, Santa Clara University, Santa Clara, CA 95053. Email address:sasgarli@scu.edu Monte Sereno, CA 95030 Email address:donaldfalkenhagen@gmail.com School of Engineering, Santa Clara Univ...

work page 1981

[1] [1]

Chromatic Number and Dichromatic Polynomial of Digraphs

S. Akbari, A. H. Ghodrati, A. Jabalameli, and M. Saghafian,Chromatic number and dichromatic polynomial of digraphs, arXiv preprint (2017), 1–13, Available athttps://arxiv.org/abs/1711.06293

work page internal anchor Pith review Pith/arXiv arXiv 2017

[2] [2]

Angel, R

E. Angel, R. Campigotto, and C. Laforest,A new lower bound on the independence number of graphs, Discrete Appl. Math.161(2013), no. 6, 847–852. 19

work page 2013

[3] [3]

Bhatia and C

R. Bhatia and C. Davis,A Better Bound on the Variance, The American Mathematical Monthly107(2000), no. 4, 353–357

work page 2000

[4] [4]

Caro,New results on the independence number, Tech

Y. Caro,New results on the independence number, Tech. report, Tel-Aviv University, 1979

work page 1979

[5] [5]

Math.159(2011), no

Hermann Gruber,Bounding the feedback vertex number of digraphs in terms of vertex degrees, Discrete Appl. Math.159(2011), no. 8, 872–875. MR 2782647

work page 2011

[6] [6]

Harant and S

J. Harant and S. Mohr,On Selkow’s bound on the independence number of graphs, Discuss. Math. Graph Theory (2019), no. 3, 655–657

work page 2019

[7] [7]

3, 265–270

Víctor Neumann-Lara,The dichromatic number of a digraph, Journal of Combinatorial Theory, Series B33(1982), no. 3, 265–270

work page 1982

[8] [8]

S. M. Selkow,A probabilistic lower bound on the independence number of graphs, Discrete Mathematics132(1994), no. 1-3, 363–365

work page 1994

[9] [9]

V. K. Wei,A lower bound on the stability number of a simple graph, Tech. Report 81-11217-9, Bell Laboratories, Murray Hill, NJ, 1981. Dept. of Mathematics & Computer Science, Santa Clara University, Santa Clara, CA 95053. Email address:sasgarli@scu.edu Monte Sereno, CA 95030 Email address:donaldfalkenhagen@gmail.com School of Engineering, Santa Clara Univ...

work page 1981