Meike Hatzel ; Pawel Komosa ; Marcin Pilipczuk ; Manuel Sorge - Constant Congestion Brambles

dmtcs:6699 - Discrete Mathematics & Theoretical Computer Science, March 31, 2022, vol. 24, no. 1 - https://doi.org/10.46298/dmtcs.6699
Constant Congestion Brambles

Authors: Meike Hatzel ; Pawel Komosa ; Marcin Pilipczuk ; Manuel Sorge

    A bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with one endpoint in $V(H_1)$ and the second endpoint in $V(H_2)$. The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble. Brambles are objects dual to treewidth: As shown by Seymour and Thomas, the maximum order of a bramble in an undirected graph $G$ equals one plus the treewidth of $G$. However, as shown by Grohe and Marx, brambles of high order may necessarily be of exponential size: In a constant-degree $n$-vertex expander a bramble of order $\Omega(n^{1/2+\delta})$ requires size exponential in $\Omega(n^{2\delta})$ for any fixed $\delta \in (0,\frac{1}{2}]$. On the other hand, the combination of results of Grohe and Marx and Chekuri and Chuzhoy shows that a graph of treewidth $k$ admits a bramble of order $\widetilde{\Omega}(k^{1/2})$ and size $\widetilde{\mathcal{O}}(k^{3/2})$. ($\widetilde{\Omega}$ and $\widetilde{\mathcal{O}}$ hide polylogarithmic factors and divisors, respectively.) In this note, we first sharpen the second bound by proving that every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetilde{\Omega}(k^{1/2})$ and congestion $2$, i.e., every vertex of $G$ is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second, we provide a tight upper bound for the lower bound of Grohe and Marx: For every $\delta \in (0,\frac{1}{2}]$, every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetilde{\Omega}(k^{1/2+\delta})$ and size $2^{\widetilde{\mathcal{O}}(k^{2\delta})}$.


    Volume: vol. 24, no. 1
    Section: Graph Theory
    Published on: March 31, 2022
    Accepted on: February 9, 2022
    Submitted on: August 6, 2020
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics
    Fundings :
      Source : OpenAIRE Research Graph
    • Cuts and decompositions: algorithms and combinatorial properties; Funder: European Commission; Code: 714704
    • Structure Theory for Directed Graphs; Funder: European Commission; Code: 648527

    Share

    Consultation statistics

    This page has been seen 549 times.
    This article's PDF has been downloaded 614 times.