Abstract:The spread of a vertex $v$ in a tree decomposition is the number of bags that contain $v$. We study the trade-off between spread and width in tree decompositions, answering every open question from Wood [arXiv:2509.01140]. First, Wood asked for the infimum of $c > 0$ such that there exists $c'$ such that each graph $G$ has a tree decomposition of width $c \cdot tw(G)$ in which each vertex $v$ has spread at most $c'(d(v)+1)$. We show that the answer is $3$. Second, we prove a conjecture of Wood, stating that every tree-decomposition of the $(n \times n)$-grid with width $n$ has a vertex with spread $\Omega(n)$. Finally, we answer the last question of Wood by showing that near-optimal average spread can be achieved simultaneously with width $O(tw(G))$.
From: Carla Groenland [view email]
[v1]
Wed, 7 Jan 2026 15:56:54 UTC (31 KB)
[v2]
Tue, 20 Jan 2026 16:33:27 UTC (32 KB)
[v3]
Fri, 4 Sep 2026 16:30:34 UTC (228 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。