| DAG-width | → | Directed treewidth | Literature | EvidenceBounded DAG-width implies bounded Directed treewidth. BDHK06, Proposition 4.1(i), author PDF p. 8 |
| D-width | → | Directed treewidth | Literature | EvidenceBounded 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-width | Literature | EvidenceBounded K-width implies bounded DAG-width. GHKLOR09, Theorem 2.10, author extended PDF p. 5 (proof also in appendix) |
| Kelly-width | → | DAG-width | Literature | EvidenceBounded Kelly-width implies bounded DAG-width. KKRS14, Theorem 5.1 and Corollary 5.2 |
| DAG-width | → | Kelly-width | Conjecture | EvidenceConjectured: 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-width | Literature | EvidenceBounded 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 treewidth | Direct comparison | EvidenceOriented 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-width | Literature | EvidenceBounded Oriented treewidth implies bounded D-width. KKRS14, Theorem 5.12 |
| Cycle rank | → | Directed pathwidth | Literature | EvidenceBounded Cycle rank implies bounded Directed pathwidth. G08, Theorem 6, author PDF p. 3 (proof p. 4) |
| Directed cutwidth | → | Directed pathwidth | Literature | EvidenceBounded 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-width | Literature | EvidenceBounded 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-width | Literature | EvidenceBounded Circumference implies bounded Kelly-width. K14, Theorem 2, arXiv:1401.2662v1 PDF p. 2 (journal publication 2017) |
| Directed pathwidth | → | Entanglement | Literature | EvidenceBounded Directed pathwidth implies bounded Entanglement. BGKR12, Proposition 7.5 |
| Entanglement | → | Directed treewidth | Literature | EvidenceBounded Entanglement implies bounded Directed treewidth. R13, Theorem 7.13 and game characterization |
| DFAS number | → | DFVS number | Direct comparison | EvidenceDFVS 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-integrity | Direct comparison | EvidenceSCC 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-integrity | Direct comparison | EvidenceSCC 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-integrity | Direct comparison | EvidenceSCC 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 rank | Direct comparison | EvidenceCycle 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 rank | Literature | EvidenceFor 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 cutwidth | Direct comparison | EvidenceDirected 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-depth | Literature | EvidenceBounded 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-width | Literature | EvidenceBounded Underlying treewidth implies bounded Directed branch-width. BMP, Corollary 25 |
| Directed branch-width | → | D-width | Direct comparison | EvidenceD₁-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-width | Direct comparison | EvidenceDirected 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 number | Literature | EvidenceBounded Directed pathwidth implies bounded Zig-zag number. O13, Theorem 4.1 and Appendix A |
| Zig-zag number | → | Tree-zig-zag number | Literature | EvidenceBounded Zig-zag number implies bounded Tree-zig-zag number. O16, Equation (1) |
| Directed treewidth | → | Tree-zig-zag number | Literature | EvidenceBounded Directed treewidth implies bounded Tree-zig-zag number. O16, Theorem 3 |
| Directed treewidth | → | Cycle-degeneracy | Literature | EvidenceBounded Directed treewidth implies bounded Cycle-degeneracy. NPS24 §2 |
| Cycle-degeneracy | → | Dichromatic number | Literature | EvidenceBounded Cycle-degeneracy implies bounded Dichromatic number. NPS24 §2 |
| Directed treewidth | → | Weak separator number | Literature | EvidenceBounded Directed treewidth implies bounded Weak separator number. G12 §3.2, final paragraph |
| Maximum average cycle-degree | → | Cycle-degeneracy | Direct comparison | EvidenceCycle-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-degree | Direct comparison | EvidenceMaximum 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 number | Literature | EvidenceBounded Maximum cycle-degree implies bounded Digrundy number. NPS24 §2 |
| Digrundy number | → | Dichromatic number | Literature | EvidenceBounded Digrundy number implies bounded Dichromatic number. AMOR22 §2, opening displayed inequality dc(D) ≤ dG(D) ≤ dac(D) |
| Directed modular width | → | Directed clique-width | Literature | Evidencedirected 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 width | Direct comparison | Evidencedmw(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-width | Direct comparison | Evidencedirected 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-width | Literature | Evidencebimimw(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-width | Direct comparison | Evidencelbimimw(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-width | Definition | Evidencebimimw(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-width | Literature | EvidenceBounded 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 pathwidth | Literature | Evidenceupw(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 treewidth | Definition | Evidenceunderlying 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 pathwidth | Definition | Evidencedpw(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 width | Definition | Evidencedtpart <= dppart Section 3, after Definition 2 A directed path is an out-arborescence. |
| Directed tree-partition width | → | D-width | Literature | EvidenceD1 <= 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 treewidth | Literature | Evidencetw(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 cutwidth | Direct comparison | Evidencedcw <= 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 number | Literature | EvidenceThe 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 · NW | Definition | EvidenceNW(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 · NCW | Definition | EvidenceNCW(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 | EvidenceSC∅(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 | EvidenceNCW∅(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 | EvidenceSC∅*(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 | EvidenceSC∅* = 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 | EvidenceNCW∅(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 treewidth | Literature | EvidencedtwBHOP(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-cutwidth | Direct comparison | Evidencedtcw(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-cutwidth | Direct comparison | Evidencedtcw(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 width | Direct comparison | EvidenceDirected 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 pathwidth | Direct comparison | EvidenceUnderlying 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 bandwidth | Direct comparison | EvidenceDigraph 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-width | Direct comparison | EvidenceDirected 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. |