Bramble (graph theory)

---

title: "Bramble (graph theory)" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-theory-objects", "graph-minor-theory"] description: "Method of graph decomposition" topic_path: "science/mathematics" source: "https://en.wikipedia.org/wiki/Bramble_(graph_theory)" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Method of graph decomposition ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/5/5a/3x3_grid_graph_haven.svg" caption="A bramble of order four in a 3×3 grid graph, consisting of six mutually touching connected subgraphs"] ::

In graph theory, a bramble for an undirected graph G is a family of connected subgraphs of G that all touch each other: for every pair of disjoint subgraphs, there must exist an edge in G that has one endpoint in each subgraph. The order of a bramble is the smallest size of a hitting set, a set of vertices of G that has a nonempty intersection with each of the subgraphs. Brambles may be used to characterize the treewidth of G.{{citation | last1 = Seymour | first1 = Paul D. | author1-link = Paul Seymour (mathematician) | last2 = Thomas | first2 = Robin | author2-link = Robin Thomas (mathematician) | doi = 10.1006/jctb.1993.1027 | issue = 1 | journal = Journal of Combinatorial Theory | series = Series B | mr = 1214888 | pages = 22–33 | title = Graph searching and a min-max theorem for tree-width | volume = 58 | year = 1993| doi-access = free

Treewidth and havens

A haven of order k in a graph G is a function β that maps each set X of fewer than k vertices to a connected component of G − X, in such a way that every two subsets β(X) and β(Y) touch each other. Thus, the set of images of β forms a bramble in G, with order k. Conversely, every bramble may be used to determine a haven: for each set X of size smaller than the order of the bramble, there is a unique connected component β(X) that contains all of the subgraphs in the bramble that are disjoint from X.

Seymour and Thomas proved that the order of a bramble (or equivalently, of a haven) characterizes treewidth: if k is the largest possible order among all brambles of a graph, then the graph has treewidth k − 1. In particular, if k is the order of some bramble, then the treewidth is at least k − 1.

Size of brambles

Expander graphs of bounded degree have treewidth proportional to their number of vertices, and therefore also have brambles of linear order. However, as Martin Grohe and Dániel Marx showed, for these graphs, a bramble of such a high order must include exponentially many sets. More strongly, for these graphs, even brambles whose order is slightly larger than the square root of the treewidth must have exponential size. However, Grohe and Marx also showed that every graph of treewidth k has a bramble of polynomial size and of order \Omega(k^{1/2}/\log^2 k).{{citation | last1 = Grohe | first1 = Martin | author1-link = Martin Grohe | last2 = Marx | first2 = Dániel | doi = 10.1016/j.jctb.2008.06.004 | issue = 1 | journal = Journal of Combinatorial Theory | series = Series B | mr = 2467827 | pages = 218–228 | title = On tree width, bramble size, and expansion | volume = 99 | year = 2009| doi-access = free

Computational complexity

Because brambles may have exponential size, it is not always possible to construct them in polynomial time for graphs of unbounded treewidth. However, when the treewidth is bounded, a polynomial time construction is possible: it is possible to find a bramble of order k, when one exists, in time O(n**k + 2) where n is the number of vertices in the given graph. Even faster algorithms are possible for graphs with few minimal separators.{{citation | last1 = Chapelle | first1 = Mathieu | last2 = Mazoit | first2 = Frédéric | last3 = Todinca | first3 = Ioan | contribution = Constructing brambles | doi = 10.1007/978-3-642-03816-7_20 | location = Berlin | mr = 2539494 | pages = 223–234 | publisher = Springer | series = Lecture Notes in Computer Science | title = Mathematical Foundations of Computer Science 2009: 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009, Proceedings | volume = 5734 | year = 2009| bibcode = 2009LNCS.5734..223C | isbn = 978-3-642-03815-0 | s2cid = 16299415

Bodlaender, Grigoriev, and Koster{{citation | last1 = Bodlaender | first1 = Hans L. | author1-link = Hans L. Bodlaender | last2 = Grigoriev | first2 = Alexander | last3 = Koster | first3 = Arie M. C. A. | doi = 10.1007/s00453-007-9056-z | issue = 1 | journal = Algorithmica | mr = 2385750 | pages = 81–98 | title = Treewidth lower bounds with brambles | volume = 51 | year = 2008| doi-access = free | last1 = Kreutzer | first1 = Stephan | last2 = Tazari | first2 = Siamak | contribution = On brambles, grid-like minors, and parameterized intractability of monadic second-order logic | pages = 354–364 | title = Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10) | url = http://dl.acm.org/citation.cfm?id=1873601.1873631 | year = 2010| publisher = Association for Computing Machinery | isbn = 978-0-89871-698-6

Directed brambles

The concept of bramble has also been defined for directed graphs.{{citation | last1 = Reed | first1 = Bruce | contribution = Introducing directed tree width | pages = 222–229 | title =Electronic Notes in Discrete Mathematics | doi = 10.1016/S1571-0653(05)80061-7 | volume = 3 | year = 1999 | publisher = Elsevier | contribution = Directed Tree-Width | title = Journal of Combinatorial Theory, Series B | volume = 82 | number = 1 | pages = 138–154 | year = 2001 | doi = 10.1006/jctb.2000.2031 | first1 = Thor | last1 = Johnson | first2 = Neil | last2 = Robertson | first3 = Paul | last3 = Seymour | first4 = Robin | last4 = Thomas | doi-access = free The bramble number of a directed graph is within a constant factor of its directed treewidth.{{citation | last1 = Kawarabayashi | first1 = Ken-ichi | last2 = Kreutzer | first2 = Stephan | contribution = The Directed Grid Theorem | title = Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC '15) | year = 2015 | location = Portland, Oregon, USA | pages = 655–664 | doi = 10.1145/2746539.2746586 | publisher = ACM| arxiv = 1411.5681 | isbn = 978-1-4503-3536-2 | s2cid = 1517283

References

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::