Polynomial directed treewidth forces a large bramble with congestion two
Abstract
Brambles of constant congestion in directed graphs have interesting structural and algorithmic applications, and it is desirable to find the smallest function fc(k) such that if a digraph has directed treewidth at least fc(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 fc(k) exists for every value c ≥ 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 f8(k) can be made polynomial; more precisely, they showed that f8(k) = 𝒪(k48 · log13 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 f2(k) = 𝒪(k96· log23 k). We also obtain smaller polynomials for higher congestion, namely f4(k) = 𝒪(k72 · log21 k) and f6(k) = 𝒪(k66 · log18 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.
Related
- Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth
- Bounds on Treewidth via Excluding Disjoint Unions of Cycles
- Treewidth and the Product of Tree-Independence and Tree-Chromatic Numbers
- An improved bound on the treewidth of planar graphs excluding a grid minor
- Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
BibTeX
@misc{campos2026polynomial,
title = {{Polynomial directed treewidth forces a large bramble with congestion two}},
author = {Victor A. Campos and Raul Lopes and Rodrigo Nogueira and Ignasi Sau},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13270},
eprint = {2610.13270},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13270},
}
RIS
TY - UNPB
TI - Polynomial directed treewidth forces a large bramble with congestion two
AU - Victor A. Campos
AU - Raul Lopes
AU - Rodrigo Nogueira
AU - Ignasi Sau
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13270
UR - https://arxiv.org/abs/2610.13270
AB - 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 ≥ 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) = 𝒪(k^48 · 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) = 𝒪(k^96· log^23 k). We also obtain smaller polynomials for higher congestion, namely f_4(k) = 𝒪(k^72 · log^21 k) and f_6(k) = 𝒪(k^66 · 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.
ER -