Boolean-Width of Graphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

Boolean-Width of Graphs

  • Conference paper
Parameterized and Exact Computation (IWPEC 2009)

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

Included in the following conference series:

Abstract

We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods across a cut of a graph. For many graph problems this number is the runtime bottleneck when using a divide-and-conquer approach. Boolean-width is similar to rank-width, which is related to the number of GF(2)-sums (1+1=0) of neighborhoods instead of the Boolean-sums (1+1=1) used for boolean-width. For an n-vertex graph G given with a decomposition tree of boolean-width k we show how to solve Minimum Dominating Set, Maximum Independent Set and Minimum or Maximum Independent Dominating Set in time O(n(n + 23k k )). We show for any graph that its boolean-width is never more than the square of its rank-width. We also exhibit a class of graphs, the Hsu-grids, having the property that a Hsu-grid on Θ(n 2) vertices has boolean-width Θ(logn) and tree-width, branch-width, clique-width and rank-width Θ(n). Moreover, any optimal rank-decomposition of such a graph will have boolean-width Θ(n), i.e. exponential in the optimal boolean-width.

Supported by the Norwegian Research Council, project PARALGO.

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. Adler, I., Vatshelle, M.: Personal communication

    Google Scholar 

  2. Bodlaender, H., Koster, A.: Treewidth Computations I Upper Bounds. Technical Report UU-CS-2008-032, Department of Information and Computing Sciences, Utrecht University (2008)

    Google Scholar 

  3. Brandstaedt, A., Lozin, V.V.: On the linear structure and clique-width of bipartite permutation graphs. Ars Combinatoria 67, 719–734 (2003)

    Google Scholar 

  4. Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Fast FPT algorithms for vertex subset and vertex partitioning problems using neighborhood unions, http://arxiv.org/abs/0903.4796+

  5. Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: H-join decomposable graphs and algorithms with runtime single exponential in rankwidth. To appear in DAM: special issue of GROW, http://www.ii.uib.no/~telle/bib/BTV.pdf

  6. Corneil, D., Rotics, U.: On the relationship between clique-width and treewidth. SIAM Journal on Computing 34(4), 825–847 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  7. Damm, C., Kim, K.H., Roush, F.W.: On covering and rank problems for boolean matrices and their applications. In: Asano, T., Imai, H., Lee, D.T., Nakano, S.-i., Tokuyama, T. (eds.) COCOON 1999. LNCS, vol. 1627, pp. 123–133. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  8. Dorn, F.: Dynamic programming and fast matrix multiplication. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 280–291. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  9. Ganian, R., Hliněný, P.: On Parse Trees and Myhill-Nerode-type Tools for handling Graphs of Bounded Rank-width (submitted manuscript), http://www.fi.muni.cz/~hlineny/Research/papers/MNtools+dam3.pdf

  10. Geelen, J., Gerards, A., Whittle, G.: Branch-width and well-quasi-ordering in matroids and graphs. Journal of Combinatorial Theory, Series B 84(2), 270–290 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  11. Hliněný, P., Oum, S.: Finding branch-decompositions and rank-decompositions. SIAM Journal on Computing 38(3), 1012–1032 (2008); Abstract at ESA 2007.

    Article  MATH  MathSciNet  Google Scholar 

  12. Hliněný, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. The Computer Journal 51(3), 326–362 (2008)

    Article  Google Scholar 

  13. Hsu, W.-L.: Decomposition of perfect graphs. Journal of Combinatorial Theory, Series B 43(1), 70–94 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  14. Jelínek, V.: The rank-width of the square grid. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 230–239. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  15. Kim, K.H.: Boolean matrix theory and its applications. Marcel Dekker, New York (1982)

    Google Scholar 

  16. Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics 126(2-3), 197–221 (2003); Abstract at SODA 2001

    Article  MATH  MathSciNet  Google Scholar 

  17. Nguyen, H.X., Thiran, P.: Active measurement for multiple link failures diagnosis in IP networks. In: Barakat, C., Pratt, I. (eds.) PAM 2004. LNCS, vol. 3015, pp. 185–194. Springer, Heidelberg (2004)

    Google Scholar 

  18. Oum, S.: Graphs of Bounded Rank-width. PhD thesis, Princeton University (2005)

    Google Scholar 

  19. Oum, S.: Rank-width is less than or equal to branch-width. Journal of Graph Theory 57(3), 239–244 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  20. Oum, S., Seymour, P.: Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B 96(4), 514–528 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  21. Pattison, P., Breiger, R.: Lattices and dimensional representations: matrix decompositions and ordering structures. Social Networks 24(4), 423–444 (2002)

    Article  Google Scholar 

  22. Robertson, N., Seymour, P.: Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B 52(2), 153–190 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  23. Rooij, J., Bodlaender, H., Rossmanith, P.: Dynamic programming on tree decompositions using generalised fast subset convolution. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 566–577. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Informatics, University of Bergen, Norway

    B. -M. Bui-Xuan, J. A. Telle & M. Vatshelle

Authors
  1. B. -M. Bui-Xuan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. A. Telle
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. M. Vatshelle
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science and Engineering, Texas A&M University, College Station, 77843, Texas, USA

    Jianer Chen

  2. Institutt for informatikk, Universitetet i Bergen, Postboks 7803, 5020, Bergen, Norway

    Fedor V. Fomin

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bui-Xuan, B.M., Telle, J.A., Vatshelle, M. (2009). Boolean-Width of Graphs. In: Chen, J., Fomin, F.V. (eds) Parameterized and Exact Computation. IWPEC 2009. Lecture Notes in Computer Science, vol 5917. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11269-0_5

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-11269-0_5

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-11268-3

  • Online ISBN: 978-3-642-11269-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics