{"id":"arxiv/2610.13270","url":"https://arxiv.org/abs/2610.13270","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Polynomial directed treewidth forces a large bramble with congestion two","domain":"cs.DS","source":"arxiv","authors":["Victor A. Campos","Raul Lopes","Rodrigo Nogueira","Ignasi Sau"],"reviews":0,"subject":"cs.DS","summary":"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$.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-09","reactions":{}}