Cycle rank (digraph)¶

Assigns a finite digraph its minimum nested vertex-elimination depth, optimizing deletion within cyclic strong components and taking the maximum depth across separate components.

Version: v1 · 2026-10-17 · History
Domain-specific #: 14114
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Directed Graph Theory → Mathematics

Core Idea¶

Cycle rank, in the directed-graph sense, assigns a finite digraph its minimum nested depth of cycle-breaking vertex elimination. An acyclic graph has rank zero. Separate strongly connected components contribute their maximum rank, while a cyclic strongly connected graph contributes one plus the smallest residual rank achievable by deleting a vertex. The minimum chooses the best deletion; the maximum records the deepest remaining branch.^[1]

For a finite digraph \(G=(V,E)\), with \(G-v\) the induced graph after removing \(v\),

\[ r(G)=\begin{cases} 0,&G\text{ is acyclic},\\ 1+\min_{v\in V}r(G-v),&G\text{ is cyclic and strongly connected},\\ \max_{C\in\operatorname{SCC}(G)}r(C),&\text{otherwise}. \end{cases} \]

^[1]

The acyclic base has priority, including for the empty graph. This entry retains Gruber's convention that a singleton with a self-loop is cyclic and has rank one; an isolated loop-free vertex has rank zero. Thus the graph category and loop convention are part of a meaningful comparison.^[1]

The quantity is also the minimum height of a directed elimination forest for the graph's nontrivial strong components. A particular forest's height is only a certificate of an upper bound until its optimality is established. It is a depth parameter, rather than the number of cycles or the number of all vertices removed across branches.^[1]

Structural Signature¶

Finite directed carrier — the vertices and directed arcs, with the loop convention fixed; discarding direction or changing whether loops count can change the value.^[1]
Acyclic base — zero on a graph without cyclic strong components, providing the recursion's stopping value; a looped singleton does not satisfy this base in the retained convention.^[1]
Strong-component decomposition — the maximum of separate component ranks, preserving deepest branch depth rather than accumulating a cycle tally.^[1]
Optimized vertex deletion — one level plus the minimum residual rank over single-vertex deletions inside a cyclic strong component; a convenient ordering need not achieve that minimum.^[1]
Minimum nested-depth interpretation — the equivalent optimum over directed elimination-forest heights; it interprets the number without identifying it with one displayed tree.^[1]
Comparison and evidence scope — distinguishes the exact invariant, a proved bound and an application-specific consequence; graph representation, convention and proof status govern what a reported number warrants.^[1]^[2]

The last role concerns evidence and use; an algorithm or an empirical measurement is not required for the mathematical value to be defined. The forest description is an equivalent interpretation of the recurrence, rather than an independent extra axiom.

What It Is Not¶

It is not the cyclomatic number of an undirected graph's cycle space, despite the shared phrase “cycle rank.” The recurrence uses directed strong connectivity, vertex deletion and branch depth. Counting an independent-cycle basis or applying an edges-minus-vertices formula addresses another invariant.

It is not the cardinality of a feedback vertex set or the height of an arbitrary elimination forest. The optimization is over nested componentwise depth; counting all selected deletion vertices answers a different question.

It is not automatically a language's star height when computed on one chosen automaton. Eggan's theorem takes the minimum cycle rank over accepting nondeterministic automata; equality for a single automaton requires further conditions, such as the minimal trim DFA of a bideterministic language in Gruber's stated theorem.^[1]

A low value is not a general tractability guarantee. The cited abstract-argumentation reduction retains hard credulous acceptance under preferred semantics even when its graph has rank one.^[2]

Scope of Application¶

The parameter applies literally to finite directed graph models with declared loop conventions:

Directed graph analysis — the recurrence compares cycle-elimination depth while retaining orientations and strong-component structure.^[1]
Elimination-forest analysis — source-worked graph decompositions distinguish a candidate forest's height from the optimized graph value.^[1]
Abstract argumentation — directed attacks in the source's loop-free formula construction yield rank one through independent literal-pair components.^[2]
Automaton transition graphs — structural rank can inform regular-language analysis, with the minimization or bideterministic conditions retained before inferring star height.^[1]

The connection to sparse matrix factorization is reported as an elimination-forest context, rather than a universal numerical claim about factorization cost.^[1]

Clarity¶

Cycle rank separates nested depth from how many cyclic pieces exist. Several independent two-cycle components can all have rank one without their values being added. It also separates the optimum from its representation: a displayed deletion tree can be deeper than the graph's minimum.^[1]^[2]

The distinction between graph rank and language star height exposes another hidden choice. Two automata can describe one language, while a theorem about minimizing over those representations is not an equality for whichever automaton happens to be supplied.^[1]

Manages Complexity¶

The recurrence reduces many possible deletion sequences to two organizing choices: take the best vertex within a cyclic strong component, then retain the deepest component branch. This compresses a search space into a scalar depth without erasing the component boundaries that explain it.^[1]

The value does not reconstruct the graph. In the argumentation construction, increasing the number of independent literal pairs does not require increasing the maximum depth. A graph's task semantics remain separate: the source's acceptance problem can stay hard at rank one.^[2]

Abstract Reasoning¶

Use component decomposition, candidate deletion, and paired bounds. An elimination forest or a deletion choice gives an upper bound; a structural obstruction gives a lower bound. Matching the two identifies the optimum. For the source's four-vertex graph, a surviving self-loop blocks a zero residual after any first deletion, while one particular first deletion achieves residual one; together they establish rank two.^[1]

Relabeling invariance follows by induction on vertex count: an arc-preserving bijection preserves cyclicity, strong components and the correspondence between deletion choices, so every base, minimum and maximum receives the same value. This is a proof about the graph assignment, not a claim that runtime is independent of representation.

Before transferring the number to another decision, test the additional conditions. The automaton theorem needs the stated minimization or minimal-trim bideterministic setting, and the argumentation example blocks the inference from low depth alone to easy acceptance reasoning.^[1]^[2]

Knowledge Transfer¶

Transfer is literal when a receiving model is a finite digraph with the same loop convention. Vertices may represent arguments, states or abstract graph positions; replacing their labels preserves the parameter if the directed structure stays fixed. Changing the arc relation or ignoring self-loops can instead change the value.^[1]^[2]

Graph Invariant captures the general isomorphism-preserved assignment pattern. Recursion is related to the computation, but does not supply this particular graph category, minimum deletion choice or maximum branch rule. A resemblance to loops or hierarchy in another field is insufficient until those graph-model commitments are made explicit.

Examples¶

A source graph with a nonoptimal displayed tree¶

Gruber's Figure 1 has vertices \(A,B,C,D\), loops at \(B\) and \(D\), reciprocal pairs \(A\leftrightarrow B\), \(B\leftrightarrow C\), \(C\leftrightarrow D\), and arcs \(A\to D\), \(D\to B\).^[1] Its displayed elimination tree starts with \(A\), then \(C\), then separate \(B\) and \(D\) leaves: height three.^[1] The source's Example 4 identifies the components left by deleting \(B\) as \(\{A\}\) and \(\{C,D\}\).^[1]

Derived here: every first deletion leaves at least one of the two looped vertices, so the residual rank is at least one. Deleting \(B\) achieves that lower bound: \(\{A\}\) has rank zero, and \(\{C,D\}\) has rank one because deleting \(D\) leaves an acyclic singleton. Thus \(r(G)=1+1=2\). The displayed tree is a valid deeper certificate; the source does not claim it is optimal.

Mapped back: the finite directed carrier is the specified four-vertex graph with loops. The acyclic base applies after the relevant looped vertex is removed. Strong-component decomposition takes the maximum of zero and one after deleting \(B\). Optimized vertex deletion is certified by that upper bound and the surviving-loop lower bound. Minimum nested-depth interpretation gives an optimum height of two. Comparison and evidence scope marks this value as an explicit derivation from the source graph and definition, distinct from its displayed height-three tree.

Literal-pair components in a formula-to-argumentation construction¶

Dvořák, Pichler and Woltran's Example 4 uses the formula \((z_1\lor z_2\lor z_3)\land(\neg z_2\lor\neg z_3\lor\neg z_4)\land(\neg z_1\lor z_2\lor z_4)\).^[2] Its construction gives a vertex for each literal and complement, clause vertices and a target formula vertex.^[2] Complement pairs attack each other; appropriate literals attack clauses, and clauses attack the target.^[2] In the proof of Theorem 1, each two-vertex literal-pair component has rank one, while clause and target singleton components have rank zero, giving overall rank one.^[2]

Mapped back: the finite directed carrier consists of those arguments and attacks. The acyclic base handles loop-free singleton remainders. Strong-component decomposition takes the maximum over independent pairs and singletons. Optimized vertex deletion removes either member of a pair to reach rank zero. Minimum nested-depth interpretation yields one level across the pairs. Comparison and evidence scope preserves the formal-reduction grade and the paper's hard preferred-semantics credulous-acceptance task.^[2]

That report's general definition ignores self-loops, whereas Gruber's retained convention counts them. This particular construction is loop-free, so the convention difference does not alter its value. Exact rank one is asserted for the worked nonempty-variable case, not for every degenerate formula construction.^[1]^[2]

Structural Tensions¶

Exact optimum versus feasible certification. A user may need the true minimum while also limiting search and memory. Gruber's 2012 study distinguishes general NP-complete decision, exact search and polynomial approximation.^[1] Choosing a cheaper certificate or approximation can leave a bound rather than establish the optimum; calling that bound the exact value hides the cost. Choosing exact certification may require more search in the supplied general algorithms. The diagnostic is: does the downstream inference need the true minimum, or would a proved bound answer it?

This is a computational reporting tradeoff, not an assertion that every graph is hard, that every exact algorithm must be exponential, or that the invariant itself becomes approximate.

Structural–Framed Character¶

Cycle rank lies toward the structural end of the spectrum, with a formal graph-category and loop-convention frame. Once the directed graph and convention are fixed, the min/max rule constrains the result rather than rating a graph according to a preference.

Evaluative weight: depth is not goodness or a promise of an easy downstream task; the rank-one argumentation case retains hard acceptance reasoning.^[2] Human-practice dependence: people choose the graph model, loop convention and certification procedure, while the resulting mathematical relations determine the value.^[1] Institutional origin: the rule is a mathematical definition, not an enacted eligibility condition. Vocabulary travel: the same quantity travels across finite digraph models; the shared phrase in cycle-space counting does not make that other invariant identical. Import versus recognition: modeling selects vertices and arcs, but recognition within that model applies the recurrence rather than a subjective difficulty judgement.

Its character: a structural graph-depth quantity whose interpretation requires stated graph and loop conventions and honest separation of optimum from bound.

Structural Core vs. Domain Accent¶

The skeleton is an isomorphism-preserved graph assignment with a particular recursive minimum-depth rule. Graph Invariant captures the general assignment pattern; the accent fixes directed reachability, strong components, single-vertex deletion, self-loop treatment and the maximum/minimum branches.^[1]

A larger minimum-decomposition-depth pattern would need independently mapped non-graph cases with the same branch and optimization logic. Merely changing application labels within digraphs does not establish that larger pattern. This named parameter therefore retains its graph-specific commitments rather than becoming the general Recursion or Cycle Prime.

This entry is a kind of Graph Invariant.

Cycle rank is a Graph Invariant, specialized to the directed elimination-depth rule. Graph Invariant admits many other graph-valued rules, while this parameter fixes the directed elimination-depth recurrence. Recursion describes a related general procedure; base, minimum and component maximum together determine this particular quantity. Cycle describes a recurring structure, while a cycle count or a cyclic process alone does not specify rank.

The closest named catalog homonym, Cyclomatic number, counts independent cycles through an undirected cycle-space construction. Entanglement (graph measure) uses a mobile-cop game; similarity in concern with cyclic structure does not identify its value with the present recurrence.

Relationships to Other Abstractions¶

Current abstraction Cycle rank (digraph) Domain-specific

Parents (1) — more general patterns this builds on

Cycle rank (digraph) is a kind of Graph Invariant Domain-specific

Cycle rank is a Graph Invariant specialized to the finite directed min/max vertex-elimination-depth recurrence.

Hierarchy path (1) — routes to 1 parentless root

Cycle rank (digraph) → Graph Invariant

Neighborhood in Abstraction Space¶

Cycle rank (digraph) sits in a sparse region of the domain-specific corpus (73^rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Graph Classes & Invariants (39 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-17

Not to Be Confused With¶

Cyclomatic number or control-flow cyclomatic complexity: independent-cycle or path-basis counting, rather than recursive directed elimination depth.
A feedback vertex set's size: total deletion cardinality rather than minimum maximum branch depth.
One elimination forest's height: a candidate upper bound until minimality is proved.^[1]
A language's star height: minimization across accepting automata, or equality under the stated bideterministic conditions.^[1]
General computational difficulty: task semantics and algorithms need separate evidence; low cycle rank alone is insufficient.^[2]

References¶

[1] Gruber, Hermann (2012). “Digraph Complexity Measures and Applications in Formal Language Theory.” Discrete Mathematics & Theoretical Computer Science 14(2):189–204. Original published article defining cycle rank and elimination forests, with the Figure 1 graph and qualified automaton relationships. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27 ↩28 ↩29 ↩30

[2] Dvořák, Wolfgang, Pichler, Reinhard, and Woltran, Stefan (2011). “Towards Fixed-Parameter Tractable Algorithms for Abstract Argumentation.” DBAI Technical Report DBAI-TR-2011-74, Technische Universität Wien. Original technical report with the worked formula construction and acceptance-hardness proof; its general self-loop convention differs from the retained one, while the selected construction is loop-free. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o