[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Between Treewidth and Clique-Width

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Many hard graph problems can be solved efficiently when restricted to graphs of bounded treewidth, and more generally to graphs of bounded clique-width. But there is a price to be paid for this generality, exemplified by the four problems MaxCut, Graph Coloring, Hamiltonian Cycle and Edge Dominating Set that are all FPT parameterized by treewidth but none of which can be FPT parameterized by clique-width unless FPT = W[1], as shown by Fomin et al. (Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, pp 493–502, 2010a; SIAM J Comput 39(5):1941–1956, 2010b). We therefore seek a structural graph parameter that shares some of the generality of clique-width without paying this price. Based on splits, branch decompositions and the work of Vatshelle (New width parameters of graphs. The University of Bergen, 2012) on maximum matching-width, we consider the graph parameter sm-width which lies between treewidth and clique-width. Some graph classes of unbounded treewidth, like distance-hereditary graphs, have bounded sm-width. We show that MaxCut, Graph Coloring, Hamiltonian Cycle and Edge Dominating Set are all FPT parameterized by sm-width.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. In Fomin et al. [9] the problems Graph Coloring, Hamiltonian Cycle and Edge Dominating Set are shown to be FPT only if FPT = W[1], while in Fomin et al. [8] the authors focus on showing that neither of MaxCut, Hamiltonian Cycle and Edge Dominating Set can have a \(f(k)n^{o(k)}\) algorithm parameterized by clique-width unless the exponential Time Hypothethis fails. However, in Fomin et al. [8] they also show that MaxCut is FPT only if FPT = W[1].

  2. A graph class also having this characteristic is the class of complement k-decomposable graphs [1], which combines aspects of co-graphs with bounded treewidth. Interpreted as a parameter, it is incomparable to sm-width, but does lie between treewidth and clique-width. However, we do not see how to compute a decomposition in FPT time.

References

  1. Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposabilitya survey. BIT Numer. Math. 25(1), 1–23 (1985)

    Article  MathSciNet  Google Scholar 

  2. Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. Theor. Comput. Sci. 412(39), 5187–5204 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  3. Charbit, P., de Montgolfier, F., Raffinot, M.: Linear time split decomposition revisited. SIAM J. Discrete Math. 26(2), 499–514 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  4. Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 34(4), 825–847 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  5. Courcelle, B., Makowsky, J., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125–150 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  6. Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12–75 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cunningham, W.H.: Decomposition of directed graphs. SIAM J. Algebr. Discrete Methods 3(2), 214–228 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  8. Fomin, F., Golovach, P., Lokshtanov, D., Saurabh, S.: Algorithmic lower bounds for problems parameterized by clique-width. In: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pp. 493–502. (2010a)

  9. Fomin, F., Golovach, P., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J. Comput. 39(5), 1941–1956 (2010b)

  10. Gajarský, J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: Parameterized and Exact Computation, pp. 163–176. Springer, Berlin (2013)

  11. Ganian, R.: Twin-cover: beyond vertex cover in parameterized algorithmics. In: Parameterized and Exact Computation, pp. 259–271. Springer, Berlin (2011)

  12. Ganian, R., Hliněnỳ, P., Nešetřil, J., Obdržálek, J., de Mendez, P.O., Ramadurai, R.: When trees grow low: shrubs and fast mso1. In: Mathematical Foundations of Computer Science 2012, pp. 419–430. Springer, Berlin (2012)

  13. Hliněnỳ, P., Oum, S., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51(3), 326–362 (2008)

    Google Scholar 

  14. Kreutzer, S., Tazari, S.: Lower bounds for the complexity of monadic second-order logic. In: Logic in Computer Science (LICS), 2010 25th Annual IEEE Symposium on, pp. 189–198. IEEE Computer Society, Silver Spring, MD (2010)

  15. Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64(1), 19–37 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  16. Oum, S.: Rank-width and vertex-minors. J. Comb. Theory, Ser. B 95(1), 79–100 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  17. Oum, S., Seymour, P.: Approximating clique-width and branch-width. J. Comb. Theory, Ser. B 96(4), 514–528 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  18. Rao, Michaël: Solving some NP-complete problems using split decomposition. Discrete Appl. Math. 156(14), 2768–2780 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  19. Robertson, Neil, Seymour, Paul D.: Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory, Ser. B 52(2), 153–190 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  20. Sæther, S.H.: Solving hamiltonian cycle by an EPT algorithm for a non-sparse parameter. In: Algorithms and Discrete Applied Mathematics, pp. 205–216. Springer, Berlin (2015)

  21. Vatshelle, M.: New width parameters of graphs. PhD thesis, The University of Bergen, (2012)

Download references

Author information

Authors and Affiliations

  1. Department of Informatics, University of Bergen, Bergen, Norway

    Sigve Hortemo Sæther & Jan Arne Telle

Authors
  1. Sigve Hortemo Sæther
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jan Arne Telle
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sigve Hortemo Sæther.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sæther, S.H., Telle, J.A. Between Treewidth and Clique-Width. Algorithmica 75, 218–253 (2016). https://doi.org/10.1007/s00453-015-0033-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-015-0033-7

Keywords

Search

Navigation