Skip to main content
Springer Nature Link
Log in

Constructing Brambles

  • Conference paper
Mathematical Foundations of Computer Science 2009 (MFCS 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5734))

Abstract

Given an arbitrary graph G and a number k, it is well-known by a result of Seymour and Thomas [22] that G has treewidth strictly larger than k if and only if it has a bramble of order k + 2. Brambles are used in combinatorics as certificates proving that the treewidth of a graph is large. From an algorithmic point of view there are several algorithms computing tree-decompositions of G of width at most k, if such decompositions exist and the running time is polynomial for constant k. Nevertheless, when the treewidth of the input graph is larger than k, to our knowledge there is no algorithm constructing a bramble of order k + 2. We give here such an algorithm, running in \({\mathcal O}(n^{k+4})\) time. For classes of graphs with polynomial number of minimal separators, we define a notion of compact brambles and show how to compute compact brambles of order k + 2 in polynomial time, not depending on k.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Amini, O., Mazoit, F., Thomassé, S., Nisse, N.: Partition Submodular Functions. To appear in Disc. Math. (2008), http://www.lirmm.fr/~thomasse/liste/partsub.pdf

  2. Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of Finding Embeddings in a k-Tree. SIAM J. on Algebraic and Discrete Methods 8, 277–284 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bachoore, E.H., Bodlaender, H.L.: New Upper Bound Heuristics for Treewidth. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol. 3503, pp. 216–227. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  4. Bellenbaum, P., Diestel, R.: Two Short Proofs Concerning Tree-Decompositions. Combinatorics, Probability & Computing 11(6) (2002)

    Google Scholar 

  5. Bodlaender, H.L.: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM J. Comput. 25, 1305–1317 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bodlaender, H.L.: A Partial k-Arboretum of Graphs with Bounded Treewidth. Theor. Comput. Sci. 209(1-2), 1–45 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bodlaender, H.L., Grigoriev, A., Koster, A.M.C.A.: Treewidth Lower Bounds with Brambles. Algorithmica 51(1), 81–98 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  8. Bodlaender, H.L., Koster, A.M.C.A.: On the Maximum Cardinality Search Lower Bound for Treewidth. Disc. App. Math. 155(11), 1348–1372 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  9. Bodlaender, H.L., Wolle, T., Koster, A.M.C.A.: Contraction and Treewidth Lower Bounds. J. Graph Algorithms Appl. 10(1), 5–49 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  10. Bouchitté, V., Todinca, I.: Treewidth and Minimum Fill-in: Grouping the Minimal Separators. SIAM J. Comput. 31(1), 212–232 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  11. Bouchitté, V., Todinca, I.: Listing All Potential Maximal Cliques of a Graph. Theor. Comput. Sci. 276(1-2), 17–32 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  12. Chapelle, M., Mazoit, F., Todinca, I.: Constructing Brambles. Technical Report, LIFO, Université d’Orléans (2009)

    Google Scholar 

  13. Clautiaux, F., Carlier, J., Moukrim, A., Nègre, S.: New Lower and Upper Bounds for Graph Treewidth. In: Jansen, K., Margraf, M., Mastrolli, M., Rolim, J.D.P. (eds.) WEA 2003. LNCS, vol. 2647, pp. 70–80. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  14. Fomin, F.V., Fraigniaud, P., Nisse, N.: Nondeterministic Graph Searching: From Pathwidth to Treewidth. Algorithmica 53(3), 358–373 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  15. Fomin, F.V., Kratsch, D., Todinca, I., Villanger, Y.: Exact Algorithms for Treewidth and Minimum Fill-in. SIAM J. Comput. 38(3), 1058–1079 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  16. Fomin, F.V., Thilikos, D.M.: An Annotated Bibliography on Guaranteed Graph Searching. Theor. Comput. Sci. 399(3), 236–245 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  17. Grohe, M., Marx, D.: On Tree Width, Bramble Size, and Expansion. J. Comb. Theory, Ser. B 99(1), 218–228 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  18. Lyaudet, L., Mazoit, F., Thomassé, S.: Partitions Versus Sets: A Case of Duality (submitted 2009), http://www.lirmm.fr/~thomasse/liste/dualite.pdf

  19. Mazoit, F.: Décompositions Algorithmiques des Graphes. PhD thesis, École Normale Supérieure de Lyon (2004) (in French)

    Google Scholar 

  20. Mazoit, F.: The Branch-width of Circular-Arc Graphs. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 727–736. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  21. Robertson, N., Seymour, P.D.: Graph Minors X. Obstructions to Tree Decompositions. J. Comb. Theory, Ser. B 52, 153–190 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  22. Seymour, P.D., Thomas, R.: Graph Searching and a Min-Max Theorem for Tree-Width. J. Comb. Theory, Ser. B 58(1), 22–33 (1993)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LIFO, Université d’Orléans, BP-6759, F-45067, Orléans Cedex 2, France

    Mathieu Chapelle & Ioan Todinca

  2. LaBRI, Université de Bordeaux, F-33405, Talence Cedex, France

    Frédéric Mazoit

Authors
  1. Mathieu Chapelle
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Frédéric Mazoit
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ioan Todinca
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Faculty of Mathematics, Physics and Informatics, Comenius University, Research partially funded by grant APVV 0433-06, Bratislava, Slovakia

    Rastislav Královič

  2. Members of EACSL Jury for the Ackermann Award, Poland

    Damian Niwiński

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Chapelle, M., Mazoit, F., Todinca, I. (2009). Constructing Brambles. In: Královič, R., Niwiński, D. (eds) Mathematical Foundations of Computer Science 2009. MFCS 2009. Lecture Notes in Computer Science, vol 5734. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03816-7_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-03816-7_20

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-03815-0

  • Online ISBN: 978-3-642-03816-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation