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.
Core Idea¶
Cycle rank gives a finite digraph its minimum nested depth of cycle-breaking vertex elimination.[^ref-6c58723f971e] Acyclic graphs have rank zero; separate strong components contribute their maximum rank, while a cyclic strong component contributes one plus the smallest rank after deleting a vertex.[^ref-6c58723f971e] Strong connectivity means each vertex can reach every other by a directed path.[^ref-6c58723f971e] The retained convention counts self-loops as cyclic, so a looped singleton has rank one rather than zero.[^ref-6c58723f971e]
Scope of Application¶
The parameter travels literally where a finite directed graph and its loop convention are specified:
- Directed graph analysis — compare optimized deletion depth while preserving orientations and strong components.[^ref-6c58723f971e]
- Elimination forests — distinguish a candidate forest's height from the minimum over admissible forests.[^ref-6c58723f971e]
- Abstract argumentation — the source's loop-free formula construction has rank one from separate literal-pair components.[^ref-b99c8b442354]
- Automaton transition graphs — use structural rank with the theorem's minimization or bideterministic conditions before inferring language star height.[^ref-6c58723f971e]
Clarity¶
The quantity distinguishes nested depth from a count of cycles, and an optimized value from one displayed certificate. Gruber's worked graph has a displayed tree of height three,[^ref-6c58723f971e] while applying the recurrence and proving both bounds gives rank two. The qualified digraph name also separates this recurrence from the independent-cycle counting associated with cyclomatic number: neither shared wording nor a visually cyclic drawing determines the parameter.
Manages Complexity¶
Many deletion orders collapse into two choices: optimize the vertex inside a cyclic strong component, then retain the deepest separate branch.[^ref-6c58723f971e] Independent branches contribute a maximum rather than a sum, so adding literal-pair components need not increase the source argumentation construction's rank.[^ref-b99c8b442354] The scalar compresses that depth while leaving graph topology and task semantics unresolved; its rank-one credulous-acceptance problem remains hard under the source's preferred-semantics interpretation.[^ref-b99c8b442354]
Abstract Reasoning¶
Use component decomposition, candidate deletion and paired bounds: a deletion forest supplies an upper bound, while a structural obstruction can certify a lower one. In the four-vertex example, every first deletion leaves a loop; deleting one particular vertex achieves residual rank one, establishing overall rank two by the recurrence. Before moving from graph rank to a language conclusion, retain the minimum over accepting automata or the stated minimal-trim bideterministic equality conditions.[^ref-6c58723f971e]
Knowledge Transfer¶
Graph analysis and the source's argumentation case literally reuse the quantity.[ref-6c58723f971e][ref-b99c8b442354] The report generally ignores self-loops; its chosen case has none, so that convention difference leaves the value unchanged.[ref-b99c8b442354][ref-6c58723f971e] Graph Invariant is the parent genus: relabeling preserves the assignment while the min/max depth rule supplies the differentia. Recursion is a related procedure, and literal transfer needs the same directed graph model; low depth alone does not promise easy task reasoning.[^ref-b99c8b442354]
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 (73rd 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
- Graph Toughness — 0.84
- Factor-critical graph — 0.83
- Dissociation number — 0.83
- Closure problem — 0.83
- Degeneracy (graph theory) — 0.83
Computed from structural-signature embeddings · 2026-10-17
References¶
[^ref-6c58723f971e]: 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. [^ref-b99c8b442354]: 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.