Research resources · Directed graphs

Digraph Parameters

Explore how structural parameters of directed graphs relate.
For parameters of undirected graphs, see Graph Parameter Hierarchy.
Follow an arrow, compare definitions, and find the source behind each relation.

A referenced relation mapGenerated by GPT 6.1 SolCurated by Myounghwan LeeUpdated 2 November 2026

02 / Directory

Parameter index

56 parameter groups, including equivalent names and the version-qualified definitions below. Select a name to open it in the map.

Definition and notes

For a vertex partition (A,B), add the maximum induced-matching size in the bipartite digraph containing only arcs A->B to the maximum induced-matching size in the bipartite digraph containing only arcs B->A. The width of a subcubic leaf-labelled branch decomposition is the maximum of this sum over its edge cuts; bi-mim-width minimizes over all such decompositions.

Explicitly extend to bimimw(empty)=bimimw(singleton)=0 because a subcubic leaf-labelled tree requires at least two leaves in the literal definition. Edgeless digraphs have width 0; the two-vertex one-arc digraph has width 1 and the two-vertex digon has width 2.

Definition and notes

The maximum number of vertices in a simple directed cycle, with value zero when there is no directed cycle.

Weak (∞, →)-coloring number · LIFO-search number · LIFO-haven order · Strong-shelter thickness · Exclusion of large Lk, CCk and TCk as butterfly minors

Definition and notes

The recursive elimination depth of directed cycles: acyclic digraphs have rank zero, non-strongly-connected digraphs take the maximum over SCCs, and a cyclic SCC takes one plus the minimum rank after one vertex deletion.

The names in this box share boundedness. The obstruction families Lk, CCk and TCk use the precise conventions of HKLW25.

Definition and notes

The maximum, over nonempty subdigraphs H, of the minimum cycle-degree of a vertex of H.

Cycle-degree counts a vertex hitting set through a fixed vertex, not a number of arc-disjoint cycles.

DS-width

Definition and notes

Safari’s original directed tree-decomposition width, with the support-edge condition for every strongly connected vertex set.

The original support-edge condition is essential: retain a tree edge in the support of S only when its endpoint bags meet S. D₀ uses maximum bag size minus one; D₁=D₀+1. DS-width has the same bounded classes.

Exclusion of long directed paths as subdigraphs

Definition and notes

The DAG-depth parameter of Ganian et al.; its bounded classes are exactly the classes excluding sufficiently long directed paths as subdigraphs.

Defined on general digraphs. It is distinct from DAG treedepth parameters whose definitions require an acyclic input.

Definition and notes

Choose a covering sequence of vertex bags (X1,...,Xs) with interval occurrences for each vertex. For every arc (u,v), require that v belongs to the first bag containing its tail u: either u,v lie in X1 or, for some i>=2, u lies in Xi minus Xi-1 and v lies in Xi. Minimize maxi |Xi|-1.

Use value 0 on the empty graph as an explicit extension; this avoids the -1 yielded by a literal all-empty bag expression. Nonempty edgeless digraphs and the singleton have value 0. Any directed path of order at least two has value 1. Every tournament on n>=1 vertices has value n-1 (Section 3.1).

Arc-disjoint cycle packing

Definition and notes

The minimum number of arcs whose deletion makes the digraph acyclic.

The packing alias is an equivalence of bounded classes, not equality of the two numbers. Apply the directed Erdős–Pósa theorem to the directed line graph.

Vertex-disjoint cycle packing

Definition and notes

The minimum number of vertices whose deletion makes the digraph acyclic.

The packing alias is an equivalence of bounded classes, not equality of the two numbers.

Star dichromatic number · Circular dichromatic number

Definition and notes

The minimum number of acyclic color classes in a vertex coloring.

Definition and notes

Over all vertex orders, minimize the maximum positive span of an arc. Empty maximum is zero; a DAG has value zero by reversing a topological order.

Definition and notes

Start with the singleton vertex partition, repeatedly merge two parts, and finish with the one-part partition. Distinct parts X,Y are homogeneous when both directed adjacency relations X->Y and Y->X are constant across their ordered vertex pairs. A nonhomogeneous pair is red. Minimize, over all contraction sequences, the maximum number of red-neighbour parts of a part at any stage.

tww(empty)=0 by explicit extension; singleton, edgeless digraphs, and bidirected complete graphs have tww=0. Degree counts other parts only. This is twin-width of the digraph/binary structure, not the different 'oriented twin-width' of an undirected graph.

Definition and notes

The maximum number of colors used by greedy dicoloring over all vertex orders.

Bi-cut-rank-width of the directed line graph

Definition and notes

The arc-labelled directed branch-width of Bumpus–Meeks–Pettersson.

The line-graph qualifier in the alias is indispensable. This is not the vertex-labelled cycle-hitting width also called directed branchwidth in other papers.

Bi-rank-width over F₂ · Directed rank-width over F₄

Definition and notes

A representative of three equivalent boundedness classes: directed clique-width, binary bi-rank-width and F₄ directed rank-width.

The binary bi-rank function sums the two directed cut ranks. The F₄ encoding records both arc directions. Numerical bounds from this group specify the representative used.

Definition and notes

The minimum, over vertex orders, of the maximum number of backward arcs across an order cut.

SCC haven number

Boundedness class A

Definition and notes

Maximum k such that a function beta assigns to every Z with |Z|<k the vertex set of an SCC of D-Z, with Z' subset Z implying beta(Z) subset beta(Z'). This is the ordinary directed haven, distinct from the cycle-rank/LIFO-haven parameter already in the hierarchy.

hn(D) <= NW(D) + 1. Source: JRST01; CLMS22; JRST01 Theorem (3.1); CLMS22 Proposition 2.12 .

NW(D) <= 3 hn(D) + 1. Source: JRST01; CLMS22; JRST01 Theorem (3.3); CLMS22 Proposition 2.13 .

bns(D) <= hn(D). Source: KHK25; Safari05; KHK25 Lemma 2.7, attributed to Safari05 .

hn(D) <= 2 bns(D). Source: KHK25; Safari05; KHK25 Lemma 2.8, attributed to Safari05 .

bnw(D) <= hn(D). Source: CLMS22; Lemma 2.14 .

hn(D) <= 2 bnw(D). Source: CLMS22; Lemma 2.14 .

Directed linear NLC-width · Directed neighbourhood-width · Directed linear rank-width over F₄

Definition and notes

A representative of four equivalent boundedness classes obtained from linear directed graph expressions or linear cut-rank decompositions.

The four names have equivalent boundedness; their numerical values need not coincide. Numerical bounds to another group refer to directed linear clique-width unless specified.

Definition and notes

A nonempty vertex set M is a directed module if all its vertices have identical incoming and outgoing neighbourhoods outside M. Directed modular width is the least k>=1 such that |V(D)|<=k, or V(D) can be partitioned into between 2 and k directed modules, each inducing a digraph recursively of directed modular width at most k. This is the Steiner-Wiederrecht recursive arity convention, including binary series/parallel/order nodes.

The source minimizes over k>=1, so dmw(empty)=dmw(singleton)=1. Any edgeless graph or bidirected complete graph of order at least two has dmw=2. Do not silently identify this numeric normalization with a prime-node-only undirected modular-width convention.

Directed neighborhood diversity

Definition and notes

Count the equivalence classes of u~v defined by N-(u) minus {v}=N-(v) minus {u}, N+(u) minus {v}=N+(v) minus {u}, and the additional condition that u->v is present if and only if v->u is present. Each class is an independent set or a bidirected clique; every two distinct classes have uniform directed adjacency in each direction.

This is distinct from directed neighbourhood-width in the linear algebraic group.

dnd(empty)=0; every nonempty edgeless graph and every nonempty bidirected complete graph has dnd=1. For every tournament of order n, dnd=n. The reciprocal-arc condition is essential for transitivity.

Definition and notes

Fujita’s explicitly proposed outward definition: partition vertices into directed-distance layers from an arbitrary root set; interbag arcs may only go from one layer to the next.

Fujita’s explicitly proposed outward definition: partition vertices into directed-distance layers from an arbitrary root set; interbag arcs may only go from one layer to the next. Minimize the maximum layer size; there is no subtraction of one.

This is a proposal in arXiv:2408.02299v9, Definitions 6.1.4–6.1.5, not a claim about the contents of a separate inaccessible 2024 manuscript. Root sets are arbitrary; backward interbag arcs are forbidden. The value is not invariant under reversing all arcs.

All comparison arrows involving this proposal are direct deductions from the specified definition, rather than theorem claims attributed to Fujita.

Definition and notes

Minimum largest part of a vertex partition whose loopless quotient is a directed path; internal arcs are discarded.

Kelly-pathwidth · Directed vertex separation · Directed proper-path-width (literal Fujita v9 definition)

Definition and notes

The minimum maximum-bag-size-minus-one of a directed path decomposition.

The proper-path-width alias uses only literal Definition 6.1.17 in Fujita’s v9 proposal. The equality with directed pathwidth is a direct deduction, not a theorem attributed to that author. Keeping only bags at last vertex occurrences proves the equality without increasing width.

A standard directed path decomposition with arc condition u in Xi, v in Xj for some i<=j for every arc u->v, and the extra condition Xi is not a subset of Xj for every i<j. Minimize maximum bag size minus one.

Cylindrical-wall weak-directed-immersion exclusion

Definition and notes

The minimum width of a near-partition tree decomposition with arc guards for crossing cycles and, at every node, either all in-onions or all out-onions.

Minimum over quadruples (T,beta,gamma,theta), with unrestricted-degree tree T and possibly empty disjoint bags covering V(D), of max(max|beta(x)|,max|gamma(e)|,max|theta(x)|). The arc guard gamma(e) hits every directed cycle crossing the cut induced by T-e. At node x, theta(x) must hit either every out-onion or every in-onion there, choice varying with x. An onion has two root-to-tip arcs and one tip-to-root arc; its immersion paths are mutually arc-disjoint. Writing y,z for the bag nodes of tip,root, an out-onion has y!=x and y,z not in the same component of T-x; an in-onion has z!=x and the same component condition. Width has no minus-one. Nonempty DAGs have value one.

BHOP26 is the public October 2026 preprint; the source reports acceptance for SODA 2027. The width has no subtraction of one. The onion guard may choose the incoming or outgoing condition separately at each tree node.

No large cylindrical wall as a weak directed immersion is equivalent in boundedness (BHOP26, Theorems 1.1–1.2).

Definition and notes

Minimum largest part of a vertex partition whose loopless quotient is a rooted out-arborescence. Internal arcs are discarded; all arcs between distinct parts must follow that arborescence.

Direct SCC bounds: for a nonempty loopless digraph with directed tree-partition width k, SCC Vertex-integrity ≤ k, Cycle rank ≤ k−1, and Circumference ≤ k. Every SCC lies in a single part of size at most k. Choose the empty deletion set in the integrity definition; apply the cycle-rank recursion within each SCC; every directed cycle stays in one SCC. These are direct deductions from JPB21’s tree-partition convention, not theorem claims attributed to that source.

Weak (∞, ↔)-coloring number

Definition and notes

Precisely the weak (∞, ↔)-coloring number in Kreutzer et al., Section 6.2.

This is not the treedepth of the underlying undirected graph.

Cyclewidth · Cylindrical-grid butterfly-minor exclusion

Boundedness class A

Definition and notes

A common boundedness class of several directed treewidth definitions, cyclewidth and cylindrical-grid butterfly-minor exclusion. Its numerical definitions are distinguished below.

Class A denotes equivalent boundedness, not equality of numerical values. The seven numerical variants and seven dual/search parameters carry the same Class A marker.

Boundedness class A

Definition and notes

The same incident-union-size-minus-one width and nonempty partition bags as NW, but require only that no closed directed walk of D-Xe meet both descendant union Ut and its complement. Ut may meet Xe. This is exactly the strong crossing-cycle-guard convention of HKLW25, since a crossing closed walk contains a crossing simple directed cycle. NCW is not butterfly-minor monotone.

NCW(D) <= NW(D). Source: KHK25; Definitions 4.2-4.3; Figure 2 .

NCW∅(D) <= NCW(D). Source: KHK25; Definitions 4.3-4.4; Figure 2 .

Boundedness class A

Definition and notes

NCW closed-walk guarding with a partition into possibly empty bags; the root bag must be nonempty. Minimize the same incident-union-size-minus-one width. It is the only butterfly-minor-monotone parameter among these five principal definitions. The emptyset subscript is source notation, not an invented alias.

NCW∅(D) <= NCW(D). Source: KHK25; Definitions 4.3-4.4; Figure 2 .

NCW∅(D) <= SC∅(D). Source: KHK25; Definitions 4.4-4.5; Figure 2 .

SCd(D) <= 3 NCW∅(D) + 2. Source: KHK25; Lemma 4.16 .

NCW∅(D) <= SC∅*(D). Source: KHK25; Definition 4.4 and Section 7 definition of SC∅* .

Boundedness class A

Definition and notes

Minimize maxt |beta(t) union all incident edge guards|-1 over rooted out-tree decompositions whose bags partition V(D) into nonempty sets. For every parent-child edge e=(s,t), its descendant union Ut is disjoint from guard Xe, and no directed walk of D-Xe starts and ends in Ut while leaving Ut. Endpoints may differ: this is the normal-set condition. NW is the source notation. It is not butterfly-minor monotone.

NW(D) <= SCd(D). Source: KHK25; Definitions 4.2,4.6; Figure 2 .

NCW(D) <= NW(D). Source: KHK25; Definitions 4.2-4.3; Figure 2 .

SC∅(D) <= NW(D). Source: KHK25; JRST01add; KHK25 Section 4.1 and Figure 2, citing the JRST addendum conversion .

hn(D) <= NW(D) + 1. Source: JRST01; CLMS22; JRST01 Theorem (3.1); CLMS22 Proposition 2.12 .

NW(D) <= 3 hn(D) + 1. Source: JRST01; CLMS22; JRST01 Theorem (3.3); CLMS22 Proposition 2.13 .

cSCC(D) <= NW(D) + 1. Source: KHK25; JRST01; KHK25 Lemma 2.2(1) .

NW(D) <= 3 cSCC(D) + 1. Source: KHK25; JRST01; KHK25 Lemma 2.2(2) .

Boundedness class A

Definition and notes

Minimize the common width over nonempty partition bags, requiring each descendant union to be one SCC after deleting its incoming guard. Additionally, at each node t the union of all proper descendant bags is disjoint from the union of ALL guards incident with t, including its incoming guard. It is not butterfly-minor monotone. A width <k decomposition directly gives a robber-monotone k-cop SCC-game strategy.

NW(D) <= SCd(D). Source: KHK25; Definitions 4.2,4.6; Figure 2 .

SCd(D) <= 3 NCW∅(D) + 2. Source: KHK25; Lemma 4.16 .

Boundedness class A

Definition and notes

Minimize the common width over partitions into possibly empty bags, root nonempty, requiring each descendant union Ut to be exactly one SCC of D-Xe and requiring |V(T)| <= |V(D)|2. In particular Ut is disjoint from Xe. This is the addendum convention, not literally the original JRST NW definition. It is not butterfly-minor monotone.

SC∅(D) <= NW(D). Source: KHK25; JRST01add; KHK25 Section 4.1 and Figure 2, citing the JRST addendum conversion .

NCW∅(D) <= SC∅(D). Source: KHK25; Definitions 4.4-4.5; Figure 2 .

SC∅*(D) <= SC∅(D). Source: KHK25; Section 7, Lemma 7.1 .

Boundedness class A

Definition and notes

The SC∅ definition with only the tree-size cap removed. Root remains nonempty, other bags may be empty, and each descendant union is exactly one SCC after deleting its guard. This is an explicitly defined numerical proof-tool variant in the source, with the same width normalization.

SC∅*(D) <= SC∅(D). Source: KHK25; Section 7, Lemma 7.1 .

USC∅(D) <= SC∅*(D). Source: KHK25; Section 7, before Lemma 7.2 .

SC∅*(D) <= USC∅(D). Source: KHK25; Lemma 7.2 .

NCW∅(D) <= SC∅*(D). Source: KHK25; Definition 4.4 and Section 7 definition of SC∅* .

Boundedness class A

Definition and notes

As SC∅*, but descendant unions may be unions of several SCCs of the guard-deleted graph, rather than one SCC. They remain disjoint from the guard; root is nonempty, other bags may be empty; no tree-size cap. This decomposition class differs from SC∅*, but the minimized numerical widths are equal by Lemma 7.2. A union of SCCs need not be normal in the NW sense.

USC∅(D) <= SC∅*(D). Source: KHK25; Section 7, before Lemma 7.2 .

SC∅*(D) <= USC∅(D). Source: KHK25; Lemma 7.2 .

Boundedness class A

Definition and notes

Maximum |A| such that for every ordered pair of DISJOINT subsets X,Y of A with equal cardinality, there are |X| vertex-disjoint directed X-to-Y paths in D. No requirement is imposed here to avoid A minus (X union Y). This explicit CLMS numerical definition must not be silently replaced by a well-linked convention with internal avoidance, nor by balanced-separator linkedness order.

wlink(D) <= 4 bnw(D). Source: CLMS22; Definition 2.8 and Lemma 2.15 .

bnw(D) <= wlink(D). Source: CLMS22; Definition 2.8 and Lemma 2.15 .

Definition and notes

The minimum number of cops in the entanglement game on a digraph.

Definition and notes

Minimum total weight of a fractional vertex cover by acyclic induced vertex sets: xA >= 0 and sumA contains v xA >= 1.

Kenny-width

Definition and notes

The maximum number of distinct simple directed s–t paths over distinct vertices s and t. The paths need not be disjoint.

This is distinct from Kelly-width.

Definition and notes

Use exactly the bi-mim cut function, but restrict the subcubic leaf-labelled branch-decomposition tree to a caterpillar. Minimize its maximum cut value over such linear decompositions.

Explicitly extend lbimimw(empty)=lbimimw(singleton)=0. Edgeless digraphs have width 0; the two-vertex one-arc digraph has width 1 and the two-vertex digon has width 2. Single-vertex leaf cuts can have value 2 and must not be discarded when quoting an exact numerical bound.

Definition and notes

The maximum average vertex cycle-degree over all nonempty subdigraphs.

The comparisons to cycle-degeneracy and maximum cycle-degree are direct min/average/max deductions.

Definition and notes

The maximum vertex cycle-degree. At v, cycle-degree is the smallest number of other vertices meeting every directed cycle through v.

Boundedness class A

Definition and notes

Maximum k admitting a directed tangle of order k: an orientation of every directed separation of order <k whose selected small sides have no triple covering V(D). A directed separation has A union B=V(D), order |A intersection B|, and one cross-arc direction absent. The objects and maximum order occur in the source; tn is notation introduced in our artifact, not a claim of a universally standardized symbol.

tn(D) <= bns(D). Source: GKKK22; Inspected arXiv version, Lemma 5.10 .

bns(D) <= 3 tn(D) + 2. Source: GKKK22; Inspected arXiv version, Lemma 5.8 .

Definition and notes

The oriented-tree-decomposition width used in Kaiser–Kreutzer–Rabinovich–Siebertz.

Boundedness class A

Definition and notes

Minimum cops in the same visible SCC helicopter game, now requiring the robber's available SCC space to shrink monotonically during every consistent play. This is ROBBER monotonicity, not cop monotonicity (never reoccupying a vertex). The parameter need not be butterfly-minor monotone, despite being boundedness equivalent to its nonmonotone version.

cSCCrm(D) <= 3 cSCC(D) + 2. Source: KHK25; JRST01; KHK25 Lemma 2.2(3) .

cSCC(D) <= cSCCrm(D). Source: KHK25; Section 2.2 definitions of monotone strategies .

Definition and notes

The minimum of |F| plus the largest SCC order of G−F, over arc sets F.

The empty digraph has largest SCC order zero. The source is credited for the definition; the comparison arrows are direct deductions.

Definition and notes

The minimum of |X| plus the largest SCC order of G−X, over vertex sets X.

The empty digraph has largest SCC order zero. The source is credited for the definition; the comparison arrows are direct deductions.

Boundedness class A

Definition and notes

A strong bramble is a family of strongly connected subgraphs whose vertex sets pairwise INTERSECT. Its order is the minimum vertex hitting-set cardinality. The parameter is the maximum such order. It is butterfly-minor monotone, unlike the weak variant.

bns(D) <= hn(D). Source: KHK25; Safari05; KHK25 Lemma 2.7, attributed to Safari05 .

hn(D) <= 2 bns(D). Source: KHK25; Safari05; KHK25 Lemma 2.8, attributed to Safari05 .

tn(D) <= bns(D). Source: GKKK22; Inspected arXiv version, Lemma 5.10 .

bns(D) <= 3 tn(D) + 2. Source: GKKK22; Inspected arXiv version, Lemma 5.8 .

Definition and notes

The analogous maximum directed-path crossing number across the cuts of an olive-tree decomposition.

Definition and notes

The ordinary undirected pathwidth of the underlying undirected graph: a sequence of bags covers all vertices, contains both endpoints of each undirected edge in a common bag, and has interval occurrences for each vertex; width is maximum bag size minus one.

Set upw(empty)=0 explicitly; nonempty edgeless graphs and the singleton have value 0. The underlying path of order at least two has value 1. This is ordinary pathwidth applied to the underlying graph, not directed pathwidth.

Definition and notes

The ordinary treewidth of the undirected graph obtained by forgetting arc directions.

Boundedness class A

Definition and notes

Minimum number of cops with any winning strategy in the JRST SCC game. From visible position (C,v), cops announce C'; robber chooses v' in the same SCC of D-(C intersection C') as v; cops then land on C', capturing if v' belongs to C'. Cops may jump arbitrarily. No monotonicity restriction. This is not the usual edge-moving directed cop game. cSCC is notation supplied here.

cSCC(D) <= NW(D) + 1. Source: KHK25; JRST01; KHK25 Lemma 2.2(1) .

NW(D) <= 3 cSCC(D) + 1. Source: KHK25; JRST01; KHK25 Lemma 2.2(2) .

cSCCrm(D) <= 3 cSCC(D) + 2. Source: KHK25; JRST01; KHK25 Lemma 2.2(3) .

cSCC(D) <= cSCCrm(D). Source: KHK25; Section 2.2 definitions of monotone strategies .

Boundedness class A

Definition and notes

A weak bramble is a family of strongly connected subgraphs whose distinct elements either intersect or have an arc in EACH direction between their vertex sets. Order is the minimum vertex hitting-set cardinality; maximize that order. The parameter need not be butterfly-minor monotone. CLMS22 calls this simply bramble number, so its convention must be stated.

bnw(D) <= hn(D). Source: CLMS22; Lemma 2.14 .

hn(D) <= 2 bnw(D). Source: CLMS22; Lemma 2.14 .

wlink(D) <= 4 bnw(D). Source: CLMS22; Definition 2.8 and Lemma 2.15 .

bnw(D) <= wlink(D). Source: CLMS22; Definition 2.8 and Lemma 2.15 .

Definition and notes

Gruber’s SCC separator number: maximize over U⊆V the minimum |S| such that each SCC of G[U−S] has at most ⌈|U−S|/2⌉ vertices.

The threshold is ⌈|U−S|/2⌉. A weighted separator number or a threshold based on |U| is a different convention.

Definition and notes

The minimum, over vertex orders, of the maximum number of crossings of an order cut by a simple directed path.

03 / Evidence

Relation index

Literature results, consequences of definitions, and direct comparisons are recorded separately. The maps select a readable set of arrows; this index also retains internal equivalences and additional comparisons.

FromRelationToEvidenceSource
DAG-width→Directed treewidthLiterature
Evidence

Bounded DAG-width implies bounded Directed treewidth.

BDHK06, Proposition 4.1(i), author PDF p. 8

D-width→Directed treewidthLiterature
Evidence

Bounded D-width implies bounded Directed treewidth.

ES05, Theorem 2, p. 67, explicitly credited there to Safari05.

ES05 labels this result “Theorem 2 (Safari (6))”, and its reference 6 is Safari’s MFCS 2005 paper. Safari05 is therefore credited as the original source, while ES05 is retained for the directly verified statement. The complete MFCS proof was not independently available in this audit, so no unverified theorem number is assigned to it.

K-width→DAG-widthLiterature
Evidence

Bounded K-width implies bounded DAG-width.

GHKLOR09, Theorem 2.10, author extended PDF p. 5 (proof also in appendix)

Kelly-width→DAG-widthLiterature
Evidence

Bounded Kelly-width implies bounded DAG-width.

KKRS14, Theorem 5.1 and Corollary 5.2

DAG-width→Kelly-widthConjecture
Evidence

Conjectured: there is a function f such that Kelly-width(G) ≤ f(DAG-width(G)) for every digraph G.

HK07, §6, concluding unnumbered conjecture (author PDF p. 8); HK08, §7, Conjecture 30, p. 218; AKKRS15, §4, final paragraph, p. 45

Hunter and Kreutzer already conjectured a constant-factor relationship between the two widths in SODA 2007; the journal version states it as Conjecture 30. This arrow records only the weaker boundedness consequence from DAG-width to Kelly-width. AKKRS15 explicitly leaves this function-bound direction open in the final paragraph of §4. Its proved reverse implication, from bounded Kelly-width to bounded DAG-width, is shown separately by the solid arrow.

Directed pathwidth→Kelly-widthLiterature
Evidence

Bounded Directed pathwidth implies bounded Kelly-width.

KKK11 (arXiv:1107.4824v1), §6.2, Lemma 6.4 (PDF p. 12) and Corollary 6.5 (PDF p. 13)

Directed pathwidth→Oriented treewidthDirect comparison
Evidence

Oriented treewidth ≤ directed pathwidth + 1 (maximum-bag-size convention).

E2; path-decomposition restriction

Orient a directed path decomposition from first to last bag. If arc endpoints never share a bag, their occurrence intervals are ordered forward. This gives an oriented tree decomposition.

Oriented treewidth→D-widthLiterature
Evidence

Bounded Oriented treewidth implies bounded D-width.

KKRS14, Theorem 5.12

Cycle rank→Directed pathwidthLiterature
Evidence

Bounded Cycle rank implies bounded Directed pathwidth.

G08, Theorem 6, author PDF p. 3 (proof p. 4)

Directed cutwidth→Directed pathwidthLiterature
Evidence

Bounded Directed cutwidth implies bounded Directed pathwidth.

FP13 full version, Appendix C.2, Lemma 7 (arXiv:1112.1538v2, PDF p. 20); GR19 §5.2 for the later improved constant.

FP13 proves directed pathwidth(D) ≤ 2·directed cutwidth(D) for every digraph D. Its proof appears in the full-version Appendix C.2, despite that appendix also discussing semi-complete digraphs. GR19 later improves the coefficient to one. The earlier factor-two bound already establishes the boundedness arrow shown here.

Circumference→DAG-widthLiterature
Evidence

Bounded Circumference implies bounded DAG-width.

K14, Theorem 2, arXiv:1401.2662v1 PDF p. 2; BL16, Theorem 3.1 (stronger numerical bound)

The first public version of Kintali’s paper is from January 2014. Theorem 2 already bounds DAG-width by circumference plus one, which establishes this boundedness implication. BL16 is retained for its later sharper numerical bound under its conventions. The same paper was published in Theoretical Computer Science in 2017.

Circumference→Kelly-widthLiterature
Evidence

Bounded Circumference implies bounded Kelly-width.

K14, Theorem 2, arXiv:1401.2662v1 PDF p. 2 (journal publication 2017)

Directed pathwidth→EntanglementLiterature
Evidence

Bounded Directed pathwidth implies bounded Entanglement.

BGKR12, Proposition 7.5

Entanglement→Directed treewidthLiterature
Evidence

Bounded Entanglement implies bounded Directed treewidth.

R13, Theorem 7.13 and game characterization

DFAS number→DFVS numberDirect comparison
Evidence

DFVS number ≤ DFAS number.

E1; feedback-set definitions

Choose the tails of a feedback arc set. Deleting those vertices also destroys every directed cycle.

DFAS number→SCC Arc-integrityDirect comparison
Evidence

SCC Arc-integrity ≤ DFAS number + 1.

E1; SCC Arc-integrity definition

A feedback arc set leaves an acyclic digraph, whose SCCs have order at most one.

DFVS number→SCC Vertex-integrityDirect comparison
Evidence

SCC Vertex-integrity ≤ DFVS number + 1.

E1; SCC Vertex-integrity definition

A feedback vertex set leaves an acyclic digraph, whose SCCs have order at most one.

SCC Arc-integrity→SCC Vertex-integrityDirect comparison
Evidence

SCC Vertex-integrity ≤ SCC Arc-integrity.

E1; integrity definitions

For an arc set F, delete its set X of tails. Then |X|≤|F| and G−X is a subdigraph of G−F, so its largest SCC cannot be larger.

SCC Vertex-integrity→Cycle rankDirect comparison
Evidence

Cycle rank ≤ SCC Vertex-integrity.

E1; cycle-rank recursion

For any vertex set X, recursively deleting X gives cr(G)≤|X|+cr(G−X)≤|X|+the largest SCC order of G−X. Minimize over X.

DAG-depth→Cycle rankLiterature
Evidence

For every nonempty loopless digraph D, cr(D) + 1 ≤ ddp(D). Hence bounded DAG-depth implies bounded cycle rank.

GHKLOR14, Corollary 3.12(b), author manuscript p. 10; Definitions 3.1 and 3.9.

This comparison is stated explicitly in Corollary 3.12(b). Theorem 3.11 characterizes DAG-depth by lift-free search against an unrestricted visible robber; Proposition 3.6 characterizes cycle rank plus one by lift-free search against a robber confined to one strongly connected component. A strategy for the unrestricted robber also wins against the confined robber. The exact +1 inequality uses cycle rank zero on DAGs and DAG-depth one on a singleton; the empty graph is excluded from this numerical statement.

DFAS number→Directed cutwidthDirect comparison
Evidence

Directed cutwidth ≤ DFAS number.

E1; topological ordering

Order the graph after deleting a minimum feedback arc set topologically. Every backward arc of the original digraph belongs to that feedback set.

Directed treedepth→DAG-depthLiterature
Evidence

Bounded Directed treedepth implies bounded DAG-depth.

KORS17 §6.2, the lemma comparing the weak (∞, ↔)-colouring number with directed-path length; GHKLOR09, Proposition 2.9.

KORS17 bounds the length of a directed path by a function of the weak (∞, ↔)-colouring number. GHKLOR09 Proposition 2.9 bounds DAG-depth by the maximum number of vertices on a directed path. Combining these two original statements yields the displayed implication; it is not attributed to the 2009 paper alone.

Underlying treewidth→Directed branch-widthLiterature
Evidence

Bounded Underlying treewidth implies bounded Directed branch-width.

BMP, Corollary 25

Directed branch-width→D-widthDirect comparison
Evidence

D₁-width ≤ max{2, 3·directed branch-width}.

E5; BMP Lemma 27 and decomposition conversion

Remove isolated vertices, split sources and sinks as in BMP Lemma 27, and use the resulting equality with undirected branch-width. A branch decomposition yields tree bags from at most three incident middle sets (include both endpoints at an edge leaf). Every ordinary tree decomposition is a D-decomposition. Source–sink splitting preserves nontrivial SCCs, and D₁-width is SCC-local.

Directed linear clique-width→Directed clique-widthDirect comparison
Evidence

Directed clique-width is bounded by the linear algebraic group.

E3; expression restriction; GR19 §4.1

Every directed linear clique-width expression is an unrestricted directed clique-width expression. The four linear widths share boundedness by GR19.

Directed pathwidth→Zig-zag numberLiterature
Evidence

Bounded Directed pathwidth implies bounded Zig-zag number.

O13, Theorem 4.1 and Appendix A

Zig-zag number→Tree-zig-zag numberLiterature
Evidence

Bounded Zig-zag number implies bounded Tree-zig-zag number.

O16, Equation (1)

Directed treewidth→Tree-zig-zag numberLiterature
Evidence

Bounded Directed treewidth implies bounded Tree-zig-zag number.

O16, Theorem 3

Directed treewidth→Cycle-degeneracyLiterature
Evidence

Bounded Directed treewidth implies bounded Cycle-degeneracy.

NPS24 §2

Cycle-degeneracy→Dichromatic numberLiterature
Evidence

Bounded Cycle-degeneracy implies bounded Dichromatic number.

NPS24 §2

Directed treewidth→Weak separator numberLiterature
Evidence

Bounded Directed treewidth implies bounded Weak separator number.

G12 §3.2, final paragraph

Maximum average cycle-degree→Cycle-degeneracyDirect comparison
Evidence

Cycle-degeneracy is bounded by Maximum average cycle-degree.

E4; cycle-degree definitions

In every nonempty subdigraph, minimum cycle-degree is at most average cycle-degree. Maximize over subdigraphs.

Maximum cycle-degree→Maximum average cycle-degreeDirect comparison
Evidence

Maximum average cycle-degree is bounded by Maximum cycle-degree.

E4; cycle-degree monotonicity

Cycle-degree does not increase in a subdigraph. Hence each subdigraph’s average cycle-degree is at most the original maximum.

Maximum cycle-degree→Digrundy numberLiterature
Evidence

Bounded Maximum cycle-degree implies bounded Digrundy number.

NPS24 §2

Digrundy number→Dichromatic numberLiterature
Evidence

Bounded Digrundy number implies bounded Dichromatic number.

AMOR22 §2, opening displayed inequality dc(D) ≤ dG(D) ≤ dac(D)

Directed modular width→Directed clique-widthLiterature
Evidence

directed clique-width(D) <= dmw(D)

SW20 full version, Theorem 2.6

The source proves the numerical bound for directed clique-width by assigning one label to each module after recursively constructing its induced digraph. It yields boundedness for the existing algebraic equivalence group; no identical numerical formula is claimed for every representative. The theorem number is that of the full version linked by the published CALDAM paper.

Directed neighbourhood diversity→Directed modular widthDirect comparison
Evidence

dmw(D) <= max{2,dnd(D)}

FFMPR25 §6.2, Lemma 6.6 and Corollary 6.7; SW20 Definition 2.2; supplied module argument

Let k=dnd(D). The k twin classes are directed modules and each induces an independent set or a bidirected clique, hence has dmw<=2. If k>=2, use the class partition in SW's recursive arity definition with bound k. If k<=1, dmw<=2 directly, including the explicitly normalized empty case. The bound is derived here from the two published definitions; FFMPR25 does not state this comparison as a numbered theorem.

Directed neighbourhood diversity→Directed linear clique-widthDirect comparison
Evidence

directed linear clique-width(D) <= dnd(D)+1

FFMPR25 §6.2, Corollary 6.7; GR19 §4.1; supplied linear-expression construction

Reserve one permanent label for each twin class and one temporary label. Build an independent class by repeatedly adding vertices carrying its permanent label. Build a bidirected clique class by adding a temporary-label vertex, inserting both directions between the temporary and permanent labels, then relabelling it to the permanent label. After all classes are built, insert the uniform arcs between class labels. Every disjoint union adds exactly one new vertex, so the expression is linear and uses at most k+1 labels. The empty case satisfies the displayed safe bound under either the zero- or one-label empty-expression convention. Boundedness then transfers to the existing linear equivalence group.

Directed clique-width→Bi-mim-widthLiterature
Evidence

bimimw(D) <= bi-rank-width over F2(D)

JKT22 §3, Lemma 11 with r=1, printed p. 38:9; full proof arXiv v1 Lemma 3.8

An induced matching of size t in one direction across a cut gives a t-by-t identity submatrix, so that matching size is at most the binary rank of the corresponding adjacency submatrix. Add the two directions and use the same branch decomposition. This is the r=1 instance of the published stronger graph-power lemma. The numerical inequality uses the bi-rank representative of the existing algebraic group.

Directed linear clique-width→Linear bi-mim-widthDirect comparison
Evidence

lbimimw(D) <= 2 * directed linear clique-width(D)

JKT22 §3, Definition 6, printed p. 38:8; GR19 §4.1; supplied prefix-cut proof

For a nonempty digraph take a directed linear k-expression, k>=1. Just before a future vertex is added, prefix vertices with the same current label have identical final incoming and outgoing adjacency to all future vertices because subsequent operations treat whole labels and never split them. Thus an induced matching in each direction across a prefix cut uses at most one prefix vertex per label and has size at most k; their sum is at most 2k. The caterpillar from this order has only such prefix cuts and singleton leaf cuts, whose bi-mim value is at most 2<=2k. The empty/singleton extension gives width zero separately. This is a proof supplied here, not a numbered published linear-clique-width inequality.

Linear bi-mim-width→Bi-mim-widthDefinition
Evidence

bimimw(D) <= lbimimw(D)

JKT22 §3, Definitions 5–6, printed p. 38:8

Every caterpillar branch decomposition is an admissible unrestricted branch decomposition, with the same cut function. The zero-vertex and one-vertex extensions agree.

Directed clique-width→Digraph twin-widthLiterature
Evidence

Bounded Directed clique-width implies bounded Digraph twin-width.

GN26 §6, opening discussion, for the directed/binary-structure extension; BKTW22 §4.2 for the original undirected clique-width comparison.

BKTW22 proves the original clique-width to twin-width bound for undirected graphs. GN26 explicitly records that the proof extends to arbitrary binary structures, including digraphs. Both sources are given because the older undirected statement alone does not specify the directed extension.

DAG-pathwidth→Underlying pathwidthLiterature
Evidence

upw(D) <= dagpw(D)

Section 3.2, Theorem 1, journal page 275.

Each arc's endpoints share the bag where its tail first occurs. The covering and interval conditions are already undirected path-decomposition conditions, so every DAG-path-decomposition is an ordinary path decomposition of the underlying graph with the same maximum bag size. Normalizing both empty cases to zero preserves the inequality.

Underlying pathwidth→Underlying treewidthDefinition
Evidence

underlying treewidth(D) <= underlying pathwidth(D)

Definitions of ordinary path- and tree-decompositions: regard the same path of bags as a tree of bags.

Every ordinary path-decomposition is a tree-decomposition on the same path, with unchanged bags and width. This is a definition inclusion, not a theorem attributed to the DAG-pathwidth paper.

Underlying pathwidth→Directed pathwidthDefinition
Evidence

dpw(D) <= upw(D)

GR19 §4, Theorem 4.1(1), arXiv:1812.06653v1 PDF p. 8; proof immediately below. YC08 §4, Definition 4.2 for the directed path-decomposition convention.

Every ordinary path-decomposition of the underlying graph is a directed path-decomposition of the same width, because both ends of every arc occur together in a bag. GR19 explicitly records this inequality; YC08 Definition 4.2 supplies the directed convention.

Directed path-partition width→Directed tree-partition widthDefinition
Evidence

dtpart <= dppart

Section 3, after Definition 2

A directed path is an out-arborescence.

Directed tree-partition width→D-widthLiterature
Evidence

D1 <= dtpart (maximum-bag-size normalization)

Proposition 3; full-version Appendix A proof

Every SCC is contained in one partition part. These parts form a valid D-decomposition; each SCC of every induced subgraph is still contained in one part.

Directed tree-partition width→Underlying treewidthLiterature
Evidence

tw(und G) <= 2 dtpart(G)-1

Proposition 3; full-version Appendix A proof

A directed tree partition is an undirected tree partition with the same largest part; apply the standard tree-partition/treewidth bound cited and used in the proof.

Digraph bandwidth→Directed cutwidthDirect comparison
Evidence

dcw <= b(b+1)/2

Definition on proceedings p. 18:2; counting proof supplied here

Fix an order of bandwidth b. A forward arc crossing cut i has tail position i-a and head position i+c, where a >= 0, c >= 1 and a+c <= b. In a simple digraph at most one arc exists for each such ordered pair; there are b(b+1)/2 pairs. Reverse the order if the existing cutwidth convention counts the opposite direction.

Dichromatic number→Fractional dichromatic numberLiterature
Evidence

The fractional dichromatic number is bounded by the Dichromatic-number group.

MW16 §1, fractional-colouring linear program and its digraph analogue; HS22 for the stronger star-dichromatic comparison.

MW16 introduces fractional digraph colouring through acyclic vertex sets. Give weight one to each class of an acyclic k-colouring and zero to the other acyclic sets; this is a feasible fractional colouring of total weight k. HS22 additionally proves the stronger comparison with the star dichromatic number, whose boundedness is grouped with ordinary dichromatic number here.

Directed treewidth · SCd→Directed treewidth · NWDefinition
Evidence

NW(D) <= SCd(D)

Definitions 4.2,4.6; Figure 2

A descendant union equal to one SCC is normal, and all SCd bags are nonempty; thus every SCd decomposition is an NW decomposition of the same width.

Directed treewidth · NW→Directed treewidth · NCWDefinition
Evidence

NCW(D) <= NW(D)

Definitions 4.2-4.3; Figure 2

A closed walk crossing a descendant cut would give a forbidden return walk for the NW normality condition.

Directed treewidth · NW→Directed treewidth · SC∅Literature
Evidence

SC∅(D) <= NW(D)

JRST01add, unnumbered Theorem on p. 1, proof pp. 1–2; KHK25 §4.1 explicitly attributes SC∅ ≤ NW to that proof.

The addendum conversion produces the SC∅ form without increasing width; this is not a direct inclusion of decomposition classes.

Directed treewidth · NCW→Directed treewidth · NCW∅Definition
Evidence

NCW∅(D) <= NCW(D)

Definitions 4.3-4.4; Figure 2

Allowing empty nonroot bags only enlarges the admissible decomposition class.

Directed treewidth · SC∅→Directed treewidth · SC∅*Definition
Evidence

SC∅*(D) <= SC∅(D)

Section 7, Lemma 7.1

Drop the tree-size cap from the admissible decomposition conditions.

Directed treewidth · SC∅*↔Directed treewidth · USC∅Literature
Evidence

SC∅* = USC∅ numerically.

KHK25, Lemma 7.2 and the definitions preceding it

A single SCC is a union of SCCs; the converse decomposition conversion of Lemma 7.2 does not increase width.

Directed treewidth · USC∅→Directed treewidth · NCW∅Literature
Evidence

NCW∅(D) ≤ USC∅(D).

KHK25, Definition 4.4 and Lemma 7.2

By Lemma 7.2, convert a USC∅ decomposition to SC∅* without increasing width. The single-SCC condition then forbids a closed walk from crossing a descendant cut, so the same decomposition satisfies NCW∅.

Directed tree-cutwidth→Directed treewidthLiterature
Evidence

dtwBHOP(D) <= g((dtcw(D)+1)2+1); the existing dtw node denotes a boundedness family

BHOP26 Conclusions; Theorem 1.2, Lemma 5.2 and Theorem 4.7; KHK25 variant equivalence

For q=dtcw(D), exclude W(q+1)2+1 as an immersion, hence as a directed topological minor. The directed grid theorem bounds BHOP26 directed treewidth by g((q+1)2+1). Transfer boundedness to all five principal KHK25 directed-treewidth variants. BHOP26 uses near-partition bags and cycle vertex guards; no stronger unverified numerical convention identification is required here.

Directed cutwidth→Directed tree-cutwidthDirect comparison
Evidence

dtcw(D) <= max{1,2 dcw(D)}

Definition 4.4; supplied direct proof E14b

Put an optimal directed-cutwidth order in singleton bags on a path. Each edge guard is the at most c crossing arcs in the counted direction; every crossing cycle meets it. Each node guard is the union of its at most two adjacent edge guards. A qualifying onion has its two endpoints separated by an adjacent cut and contains directed paths in both directions, so meets the guard.

DFAS number→Directed tree-cutwidthDirect comparison
Evidence

dtcw(D) <= max{1,dfas(D)}

Definition 4.4; supplied direct proof E14c

Use singleton bags on any tree and a fixed minimum feedback arc set F as every edge guard and every node guard. It meets every crossing cycle; every onion immersion model contains a directed cycle and therefore also meets F.

Directed path-distance-width (Fujita v9 proposal)→Directed path-partition widthDirect comparison
Evidence

Directed path-partition width ≤ proposed path-distance width.

F26v9, Definitions 6.1.4–6.1.5; direct proof E13

Its ordered distance layers already form a valid directed path partition.

Directed path-distance-width (Fujita v9 proposal)→Underlying pathwidthDirect comparison
Evidence

Underlying pathwidth ≤ 2·proposed path-distance width − 1.

F26v9, Definitions 6.1.4–6.1.5; direct proof E13

If every layer has size at most k and interlayer arcs join only consecutive layers, the unions of consecutive layers give an ordinary path decomposition with bag size at most 2k.

Directed path-distance-width (Fujita v9 proposal)→Digraph bandwidthDirect comparison
Evidence

Digraph bandwidth ≤ proposed path-distance width − 1.

F26v9, Definitions 6.1.4–6.1.5; direct proof E13

Order the layers in reverse order, and vertices inside each layer arbitrarily. All interlayer arcs go backward. The forward span of an arc inside a layer is at most k−1.

Underlying pathwidth→Directed linear clique-widthDirect comparison
Evidence

Directed linear clique-width ≤ underlying pathwidth + 2.

Direct proof E13; underlying path decomposition

Maintain one label for each active vertex of a path decomposition and one persistent label for forgotten vertices. Introduce each vertex at its first bag, join it individually to its active neighbours in the required directions, and forget a vertex only after its last bag. There are at most p+1 active singleton labels and one forgotten label; forgotten vertices have no future neighbours.

04 / Sources

References

Download relation data

Source identifiers are shared by the map and the evidence panel. The locator attached to a relation identifies the relevant statement or definition; preprint versions are stated where they matter.

[AMOR22]

The digrundy number of digraphs

Gabriela Araujo-Pardo; Juan José Montellano-Ballesteros; Mika Olsen; Christian Rubio-Montiel

Discrete Applied Mathematics 317, pages 117–123 (2022). Earlier preprint arXiv:2103.11917v1 (2021).

[BHOP26]

Potatoes and Onions

M. Brianski, M. Hatzel, K. Okrasa and M. Pilipczuk

arXiv:2610.20391v1, 14 October 2026; accepted for SODA 2027

[BKTW22]

Twin-width I: Tractable FO Model Checking

Édouard Bonnet; Eun Jung Kim; Stéphan Thomassé; Rémi Watrigant

Journal of the ACM 69(1), article 3, pages 3:1–3:46 (2022). Conference version FOCS 2020.

[FFMPR25]

Parameterizing path partitions

Henning Fernau; Florent Foucaud; Kevin Mann; Utkarsh Padariya; Rajath Rao K. N.

Theoretical Computer Science 1028, article 115029 (2025).

[GKKK22]

Directed Tangle Tree-Decompositions and Applications

Archontia C. Giannopoulou; Ken-ichi Kawarabayashi; Stephan Kreutzer; O-joung Kwon

SODA 2022, 377–405. Lemma numbering here follows arXiv:2009.13184v1, whose title is ‘The canonical directed tree decomposition and its applications to the directed disjoint paths problem’.

[JRST01]

Directed Tree-Width

Thor Johnson; Neil Robertson; Paul D. Seymour; Robin Thomas

Journal of Combinatorial Theory, Series B 82(1), 138–154 (2001).

[KO14]

Width-measures for directed graphs and algorithmic applications

Stephan Kreutzer, Sebastian Ordyniak

In Quantitative Graph Theory: Mathematical Foundations and Applications, CRC Press, 2014. Editors Matthias Dehmer and Frank Emmert-Streib. ISBN 9781466584518. The exact SCd formalization and attribution here follow KHK25 Definition 4.6.

[Reed99]

Introducing directed tree-width

Bruce Reed

Electronic Notes in Discrete Mathematics 3:222-229, 1999. Historical weak-bramble attribution verified through explicit KHK25 citations.

[V96]

Integrity of Digraphs

R. C. Vandell

PhD dissertation, Western Michigan University, 1996. Official abstract gives both SCC integrity definitions: