PaperlayerView exact revision on arXiv

Source-linked AI summary

Polynomial directed treewidth forces a large bramble with congestion two

Victor A. Campos, Raul Lopes, Rodrigo Nogueira, Ignasi Sau

arXiv:2610.13270v1cs.DScs.DMmath.CO

TL;DR

Large constant-congestion brambles in digraphs have structural and routing applications, but the general bounds were either extremely large or polynomial only for congestion 8. This paper introduces walkages to obtain a polynomial bound at congestion 2, the smallest possible value, and derives routing consequences.

  • Problem

    Although constant-congestion brambles support routing applications, the general directed-treewidth bound remains a height-22 power tower, and whether congestion 2 could have a polynomial bound was open.

    Source: §1 · p. 3

  • Method

    The proof improves the congestion-8 approach with walkages, using linkages to form closed walks that retain well-linked vertices.

    Source: §2 · pp. 7–9

  • Results

    f2(k) = O(k^96 · log^23 k) suffices for every digraph of directed treewidth at least f2(k) to contain a size-k bramble of congestion 2.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The result yields polynomial strong-connectivity thresholds for digraphs to be (k, 2)-linked, with corresponding solutions findable in polynomial time.

    Source: §1 · p. 4

    The web-based strategy gives congestion-2 brambles at directed treewidth roughly 2k, but the authors could not extend it to polynomial-in-k cylindrical-grid construction.

    Source: §1 · p. 5

Abstract

from arXiv · show

Brambles of constant congestion in directed graphs have interesting structural and algorithmic applications, and it is desirable to find the smallest function $f_c(k)$ such that if a digraph has directed treewidth at least $f_c(k)$, then it contains a bramble of size at least $k$ and congestion at most $c$. By the Directed Grid Theorem of Kawarabayashi and Kreutzer [STOC 2015], such a function $f_c(k)$ exists for every value $c \geq 2$ of the congestion. However, even using the recent improvements due to Hatzel et al. [FOCS 2024], the resulting function is a power tower of height $22$. Recently, Masařík et al. [SIAM J. Discrete Math. 2022] proved that, for congestion $8$, the function $f_8(k)$ can be made polynomial; more precisely, they showed that $f_8(k) = \mathcal{O}(k^{48} \cdot \log^{13} k)$. They asked whether it is possible to decrease the congestion, ideally to $2$, even at the cost of a higher polynomial function. In this work we answer their question affirmatively with the best possible value of the congestion, by proving that $f_2(k) = \mathcal{O}(k^{96}\cdot \log^{23} k)$. We also obtain smaller polynomials for higher congestion, namely $f_4(k) = \mathcal{O}(k^{72} \cdot \log^{21} k)$ and $f_6(k) = \mathcal{O}(k^{66} \cdot \log^{18} k)$. Our results are inspired by the proof for congestion $8$, which we improve by introducing walkages. Walkages allow us to avoid technicalities of the original proof by translating ideas due to Reed and Wood [Eur. J. Comb. 2012] that work for undirected graphs to the directed setting. Our proofs are constructive and naturally yield polynomial-time algorithms to find the brambles assuming a certificate for large directed treewidth is given. Moreover, we discuss algorithmic applications of our results for the Directed Disjoint Paths with Congestion problem, and to half-integral packings of subgraphs with large directed treewidth.

1 Introduction

The introduction motivates polynomial bounds for finding large constant-congestion brambles in digraphs, where directed treewidth generalizes treewidth but the Directed Grid Theorem bound remains enormous. The paper answers the open congestion-2 question and describes algorithmic consequences and remaining questions.

1 Introduction

  • The directed-treewidth-to-bramble question differs from the undirected setting, where brambles are dual to treewidth and polynomial grid bounds are known.Directed brambles are only approximate duals to directed treewidth [39]; the Directed Grid Theorem bound is a power tower of height 22.Source: §1 · pp. 2–3
  • dtw(D) ≥ O(k^96 · log^23 k) guarantees a bramble of size k and congestion 2.The produced bramble is strong, meaning all its bags pairwise intersect.Source: §1 · p. 3
  • f4(k) = O(k^72 · log^21 k) and f6(k) = O(k^66 · log^18 k), while the techniques do not improve the congestion-8 bound.The congestion-8 bound remains f8(k) = O(k^48 · log^13 k).Source: §1 · pp. 3–4
  • The results yield polynomial-time bramble-finding algorithms when a certificate of large directed treewidth is supplied.The main running-time bottleneck is applying the algorithmic Lovász Local Lemma [33].Source: §1 · p. 4
  • Theorem 1.1 gives polynomial-threshold routing consequences: sufficiently strongly connected digraphs are (k, 2)-linked, with solutions findable in polynomial time.The theorem also improves a subgraph-packing congestion bound from 4 to 2, at a worse polynomial dependence than [34, Theorem 5].Source: §1 · p. 4
  • A polynomial bound for building cylindrical grids remains open, although the authors describe a shorter web-based route to congestion-2 brambles at directed treewidth roughly 2k.They could not extend that strategy to polynomial dependence on k for cylindrical grids.Source: §1 · p. 5

2 Proof overview

The proof adapts Reed and Wood’s undirected approach to digraphs using walkages, which simplify arguments involving linkages and well-linked sets. From an initial path system, it builds a congestion-two bramble or intermediate structures that yield one.

Improving tools from [35]

  • Replacing the overlap-three constructions and Bowtie steps of, the authors use congestion-two walkages and vertex-disjoint closed walks to keep congestion at most 2.If a collection does not yield a congestion-two bramble, its closed walks can be assumed vertex-disjoint, so merging collections does not increase congestion; the extended Bowtie construction uses one untangled threaded linkage and vertex-disjoint closed walks.Source: §2 · pp. 7–8

Walkages

  • Walkages replace paths with walks, letting the proof adapt Reed and Wood’s path-system ideas to digraphs without discarding well-linked vertices when converting walks back into paths.In digraphs, directed paths need not be strong subgraphs; walkages also allow self-intersections and avoid walk-to-path polishing steps.Source: §2 · pp. 8–9
  • For each base path, a linkage from its later portion to its earlier portion closes it into a walk while retaining a large subset of the well-linked set.The linkage is chosen to leave well-linked vertices in the middle of the path.Source: §2 · p. 8, Figure 1 · p. 8

Unpacking Lemma 4.13

  • Lemma 4.13 turns an untangled threaded walkage into a linked cyclic walkage or a bramble; its constructions preserve congestion at most 2.The proof splits the input into walkages, untangles them or finds cyclic walkages, and uses intersection-graph sparsity or density to assemble the result.Source: §2 · pp. 10–11

Unpacking Lemma 5.2

  • Lemma 5.2 uses linked cyclic walkages between pairs of walks to build a strong system, or finds a bramble with congestion 2.Walkages permit concatenating smaller walks without discarding potentially important well-linked vertices to recover paths.Source: §2 · p. 11

Unpacking Lemma 5.3

  • Lemma 5.3 converts a strong system into a bramble of size k and congestion 2 using dense or sparse intersection-graph cases.Dense pairs yield a clique minor directly; sparse pairs yield disjoint closed walks whose intersection graph contains a large clique minor.Source: §2 · pp. 11–12

Finding the brambles in polynomial time

  • Assuming a path system is given, the constructions yield polynomial-time algorithms; the main running-time bottleneck is the algorithmic Lovász Local Lemma.The proofs also use polynomial-time intersection-graph degeneracy computations and walk-selection steps.Source: §2 · p. 12

Brambles with congestion 4 and 6

  • For congestion 4 and 6, the authors adapt path systems into walk systems and handle dense and sparse intersection-graph cases to obtain improved directed-treewidth bounds.Walkages are retained to build on the results of Section 4, though they are not strictly necessary for these higher-congestion proofs.Source: §2 · pp. 12–13

3 Preliminaries

This section establishes graph and parameterized-complexity notation, then introduces directed brambles, well-linked sets, and tools used to obtain brambles from closed walks.

3.1 Graphs and digraphs

  • The section defines basic graph, digraph, path, walk, and connectivity terminology, including strong connectivity and strongly connected components.It also specifies vertex deletion, induced subgraphs, and graph minors.Source: §3.1 · pp. 13–14

3.2 Parameterized complexity

  • Parameterized problems are classified here using FPT and XP running-time definitions; W[1]-hardness is presented as evidence against fixed-parameter tractability.The section also defines degeneracy and states auxiliary results used in the later arguments.Source: §3.2 · p. 14, §3.4 · p. 17

3.3 Directed treewidth, brambles, and well-linked sets

  • A directed bramble is a family of strongly connected bags that intersect pairwise or have arcs in both directions between each pair; strong brambles have pairwise-intersecting bags.The order is the minimum size of a vertex set meeting every bag, and congestion is the maximum number of bags containing one vertex.Source: §3.3 · pp. 14–15
  • A well-linked set supports disjoint paths between equal-sized disjoint subsets, and a path containing such a set can be obtained alongside a bounded-width arboreal decomposition or as an alternative output.The path and well-linked set form the backbone for path systems; congestion-2 proofs use strong systems, while congestion-4 and -6 proofs relax path systems to walk systems.Source: §3.3 · pp. 15–16

3.4 Clique minors and multicolored independent sets

  • The sparse-versus-dense strategy examines degeneracy in intersection graphs of closed walks: sparse cases use multicolored independent sets, while dense cases yield clique minors.A family of closed walks with bounded congestion and a sufficiently degenerate intersection graph yields a bramble with the same congestion.Source: §3.4 · pp. 16, 18

4 Walkages

This section develops walkages, a walk-based generalization of linkages, as a framework for turning well-linked or structured inputs into cyclic walkages or congestion-two brambles. It establishes bounded-size alternatives and transformations from untangled inputs to linked cyclic outputs while preserving congestion two.

4 Walkages

  • Walkages replace linkage paths with pairwise vertex-disjoint walks and extend to arbitrary congestion, simplifying arguments that use both linkages and well-linked sets.A walkage’s congestion is the congestion of its walks’ vertex sets.Source: §4 · p. 18
  • Walkages permit self-intersections and avoid walk-to-path polishing that can remove vertices from a well-linked set.The authors introduce them to overcome this issue and develop techniques unavailable with linkages.Source: §4 · pp. 18–19
  • Allowing arbitrary congestion generalizes half-integral linkages and helps reduce the polynomial degree for brambles of congestion 4 and 6.The relaxation avoids constructions that need not be as strict as in the congestion-2 case.Source: §4 · p. 19
  • Threaded walkages connect constituent walks via threads; untangled threads intersect the rest only in adjacent walks, while cyclic walkages close each walk for tighter congestion control.The section uses these structures to control congestion when building brambles.Source: §4 · pp. 19–20
  • Untangled threaded walkages remain disjoint when selected consecutive segments are joined, and sufficiently large threaded walkages contain either a 2-cyclic subwalkage of size s or an untangled one of size u.The threshold is s(u + 1) − 1 walks.Source: §4 · p. 21
  • A c-cyclic walkage of size at least s·d3.8(k) yields either a size-k bramble of congestion at most c or a cyclic subwalkage of size s.The result lets the construction continue with a cyclic subwalkage when it does not directly produce the bramble.Source: §4 · p. 23
  • When two untangled walkages have union intersection-graph minimum degree at least d4.8(s), they yield size-s 2-cyclic subwalkages and s closed walks of congestion 2 pairing distinct walks from each.Combining an untangled walkage with a c-cyclic one under the same degree condition yields size-s (c + 1)-cyclic subwalkages and closed walks of congestion at most c + 1.Source: §4 · pp. 23–24
  • Concatenating walks from W and S constructs s closed walks of congestion at most c + 1, each containing a walk from both walkages.The resulting subwalkages of W and S are (c + 1)-cyclic and have size s.Source: §4 · p. 24
  • With an untangled walkage and a structured walkage, Corollary 4.10 gives a size-k bramble of congestion 2 or cyclic subwalkages of size s alongside a closed walkage pairing distinct walks from each input.Its degree threshold is d4.10(k, s) = O(ks√log k).Source: §4 · p. 25
  • From a well-linked walkage of threshold w4.11(s, u) = O(s^2u), Lemma 4.11 yields a size-s 2-cyclic or size-u untangled subwalkage.Unlike [35, Lemma 3.5] and [35, Lemma 3.6], this approach keeps congestion at 2, at a small extra cost in input walkage size.Source: §4 · pp. 25–26
  • A well-linked walkage of size at least w4.12(k, s, u) = O(k^2s^2u · log k) yields a size-k bramble of congestion 2, a size-s cyclic subwalkage, or a size-u untangled subwalkage.Source: §4 · p. 26
  • An untangled ℓ′-linked walkage meeting Lemma 4.13’s thresholds yields either a size-k bramble of congestion 2 or an ℓ-linked cyclic walkage of size w.The required linkedness threshold is ℓ4.13(k, ℓ, w) = O(ℓ + w^6k^6 · log^3 k).Source: §4 · p. 27

5 Strong systems

Walkages and strong systems adapt the path-system strategy for undirected graphs to directed graphs, where directed paths alone do not provide the strong subgraphs needed for brambles. The section builds strong systems from cyclic walkages and shows that they yield congestion-2 brambles.

5 Strong systems

  • Directed paths are not strong subgraphs, so translating path-system methods into bramble constructions requires additional work.The congestion-8 approach in faced this issue when adapting the undirected path-system strategy.Source: §5 · p. 28
  • An (ℓ, w)-strong system pairs a closed walkage W of size w with closed walkages L_ij of size ℓ, each meeting both corresponding walks W_i and W_j.Avoiding order within closed walks makes strong systems simpler to work with than path systems.Source: §5 · pp. 28–29
  • A sufficiently linked cyclic walkage yields either a size-k congestion-2 bramble or an (ℓ, w)-strong system.Lemma 5.2 constructs the system using walkages between pairs of walks, then makes each pairwise walkage cyclic or untangled.Source: §5 · pp. 29–30
  • Walkages generalize linkages by replacing paths with walks, helping preserve well-linked vertices while concatenating smaller walks.This adapts ideas behind Reed and Wood’s undirected path-system strategy [40] to directed graphs.Source: §5 · p. 30
  • An (ℓ, k)-strong system with ℓ = O(k^3√log k) contains a size-k bramble of congestion 2.The proof uses disjoint closed walks to obtain a subdivided K_k, then forms intersecting closed walks while keeping congestion at most two.Source: §5 · pp. 30–31

6 Congestion two and applications

The section proves a polynomial directed-treewidth threshold for finding congestion-2 brambles, then applies the result to directed disjoint paths and half-integral packings. It also discusses the running-time qualification and a stronger property of the packing construction.

6.1 Finding the bramble

  • dtw(D) ≥ O(k^96 · log^23 k) guarantees a size-k bramble of congestion 2.The proof starts with a sufficiently linked walkage and proceeds through a cyclic walkage and a strong system unless an intermediate step already yields the bramble.Source: §6.1 · p. 31
  • The congestion-4 and congestion-6 variants require directed treewidth Ω(k^90 · polylog k) and Ω(k^78 · polylog k), respectively.The section omits their technical details and later gives alternative proofs with smaller directed-treewidth dependencies.Source: §6.1 · p. 31
  • The bramble construction is claimed to run in polynomial time when the path and well-linked set from Proposition 3.5 are given, but its precise running-time bound is unavailable.The authors use the algorithmic Lovász Local Lemma version from; Proposition 3.9’s precise running time is not known.Source: §6.1 · p. 32

6.2 Directed Disjoint Paths with Congestion

  • A k-strong digraph with dtw(D) ≥ O(k^192 · log^23 k) is (k, 2)-linked, with a solution findable in polynomial time.The bramble result is combined with the bramble-to-linkage proposition; the section also states that congestion-2 disjoint paths are solvable in O(n^f(k)) time in k-strong digraphs.Source: §6.2 · p. 33

6.3 Half-integral packings of subgraphs with high directed treewidth

  • dtw(D) ≥ O((dk)^96 · log^23(dk)) guarantees a half-integral packing of k subgraphs, each with directed treewidth at least d.The construction groups a congestion-2 bramble into k parts; it also yields strong subgraphs that pairwise intersect, and the authors believe the bound is far from tight.Source: §6.3 · p. 34

7 Higher congestion

This section adapts the earlier bramble construction using walkages, simplifying the proof and controlling the congestion of the resulting brambles. It proves polynomial directed-treewidth bounds for brambles of congestion 4 and 6.

7 Higher congestion

  • Walkages adapt the proof for congestion 8, simplify its case analysis, and improve control over intermediate structures to obtain congestion 4 or 6.The section describes dense and sparse configurations as the two routes to these brambles.Source: §7 · pp. 34, 36
  • When w ≥ w7.2(k), a walkage covering at least 0.6(w^2 − w) ordered pairs of a walk system yields a size-k bramble of congestion at most 4.Lemma 7.2 constructs closed walks from walks connecting pairs in both directions, then combines them into the bramble.Source: §7 · p. 35
  • The congestion-4 lemma can reach congestion 2 when its input walk system is clean, but the authors report no way to force that input without using strong systems.They describe passing through strong systems as necessary for their congestion-2 strategy.Source: §7 · p. 36
  • If a digraph D contains an (ℓ, w)-walk system S = (A, W), with ℓ ≥ ℓ7.4(k, w) and w ≥ w7.2(k), then D contains a bramble of size k with congestion at most 6.Source: §7 · p. 38
  • O(k^72 · log^21 k) directed treewidth forces a size-k bramble of congestion at most 4, while O(k^66 · log^18 k) suffices for congestion at most 6.These are Theorems 7.5 and 7.6, respectively.Source: §7 · p. 39

Related papers

Loading 2610.13270v1…