Top

Published in:

2017 | OriginalPaper | Chapter

Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity

Authors : Dušan Knop, Martin Koutecký, Tomáš Masařík, Tomáš Toufar

Published in: Graph-Theoretic Concepts in Computer Science

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper settles the computational complexity of model checking of several extensions of the monadic second order (MSO) logic on two classes of graphs: graphs of bounded treewidth and graphs of bounded neighborhood diversity.

A classical theorem of Courcelle states that any graph property definable in MSO is decidable in linear time on graphs of bounded treewidth. Algorithmic metatheorems like Courcelle’s serve to generalize known positive results on various graph classes. We explore and extend three previously studied MSO extensions: global and local cardinality constraints (CardMSO and MSO-LCC) and optimizing a fair objective function (fairMSO).

We show how these fragments relate to each other in expressive power and highlight their (non)linearity. On the side of neighborhood diversity, we show that combining the linear variants of local and global cardinality constraints is possible while keeping FPT runtime but removing linearity of either makes this impossible, and we provide an XP algorithm for the hard case. Furthemore, we show that even the combination of the two most powerful fragments is solvable in polynomial time on graphs of bounded treewidth.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Mixed Dominating Set: A Parameterized Perspective

next chapter Extending Partial Representations of Trapezoid Graphs

Alves, S.R., Dabrowski, K.K., Faria, L., Klein, S., Sau, I., dos Santos Souza, U.: On the (parameterized) complexity of recognizing well-covered (r, 1) graphs. In: Chan, T.H.H., Li, M., Wang, L. (eds.) COCOA. LNCS, pp. 423–437. Springer, Heidelberg (2016). doi:10.1007/978-3-319-48749-6

Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308–340 (1991)CrossRefMathSciNetMATH

Bodlaender, H.L.: Treewidth: characterizations, applications, and computations. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 1–14. Springer, Heidelberg (2006). doi:10.1007/11917496_1 CrossRef

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

Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theor. Comput. Syst. 33(2), 125–150 (2000). http://dx.doi.org/10.1007/s002249910009 CrossRefMathSciNetMATH

Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. In: Schmidt, G., Berghammer, R. (eds.) WG 1991. LNCS, vol. 570, pp. 13–24. Springer, Heidelberg (1992). doi:10.1007/3-540-55121-2_2 CrossRef

Cygan, M., Fomin, F.V., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Heidelberg (2015). doi:10.1007/978-3-319-21275-3 CrossRefMATH

Dvořák, P., Knop, D., Toufar, T.: Target Set Selection in Dense Graph Classes. CoRR 1610.07530 (October 2016)

Dvořák, P., Knop, D., Masařík, T.: Anti-path cover on sparse graph classes. In: Bouda, J., Holík, L., Kofroň, J., Strejček, J., Rambousek, A. (eds.) Proceedings 11th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, Telč, Czech Republic, 21st–23rd October 2016. Electronic Proceedings in Theoretical Computer Science, vol. 233, pp. 82–86. Open Publishing Association (2016)

10.

Fiala, J., Gavenčiak, T., Knop, D., Koutecký, M., Kratochvíl, J.: Fixed parameter complexity of distance constrained labeling and uniform channel assignment problems. In: Dinh, T.N., Thai, M.T. (eds.) COCOON 2016. LNCS, vol. 9797, pp. 67–78. Springer, Cham (2016). doi:10.1007/978-3-319-42634-1_6 CrossRef

11.

Freuder, E.C.: Complexity of K-tree structured constraint satisfaction problems. In: Proceedings of the Eighth National Conference on Artificial Intelligence, vol. 1, pp. 49. AAAI 1990, AAAI Press (1990). http://dl.acm.org/citation.cfm?id=1865499.1865500

12.

Frick, M., Grohe, M.: The complexity of first-order and monadic second-order logic revisited. Ann. Pure Appl. Logic 130(1–3), 3–31 (2004). http://dx.doi.org/10.1016/j.apal.2004.01.007

13.

Ganian, R.: Using neighborhood diversity to solve hard problems. CoRR abs/1201.3091 (2012). http://arxiv.org/abs/1201.3091

14.

Ganian, R., Obdržálek, J.: Expanding the expressive power of monadic second-order logic on restricted graph classes. In: Lecroq, T., Mouchard, L. (eds.) IWOCA 2013. LNCS, vol. 8288, pp. 164–177. Springer, Heidelberg (2013). doi:10.1007/978-3-642-45278-9_15 CrossRef

15.

Gargano, L., Rescigno, A.A.: Complexity of conflict-free colorings of graphs. Theor. Comput. Sci. 566, 39–49 (2015). http://www.sciencedirect.com/science/article/pii/S0304397514009463

16.

Gottlob, G., Pichler, R., Wei, F.: Monadic datalog over finite structures with bounded treewidth. In: Proceedings of the 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pp. 165–174 (2007)

17.

Grohe, M., Kreutzer, S.: Methods algorithmic meta theorems. Model Theor. Methods Finite Comb. 558, 181–206 (2011)CrossRefMathSciNetMATH

18.

Kloks, T. (ed.): Treewidth: Computations and Approximations. LNCS, vol. 842. Springer, Heidelberg (1994). doi:10.1007/BFb0045375 MATH

19.

Kneis, J., Langer, A., Rossmanith, P.: Courcelle’s theorem - a game-theoretic approach. Discret. Optim. 8(4), 568–594 (2011)CrossRefMathSciNetMATH

20.

Knop, D., Kouteckỳ, M., Masařík, T., Toufar, T.: Simplified algorithmic metatheorems beyond MSO: Treewidth and neighborhood diversity. arXiv preprint. arXiv:1703.00544 (2017)

21.

Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. J. Comput. Syst. Sci. 61(2), 302–332 (2000). http://www.sciencedirect.com/science/article/pii/S0022000000917136 CrossRefMathSciNetMATH

22.

Kolman, P., Koutecký, M., Tiwary, H.R.: Extension complexity, MSO logic, and treewidth (v3) (12 July 2016). http://arxiv.org/abs/1507.04907, short version presented at SWAT 2016

23.

Kolman, P., Lidický, B., Sereni, J.S.: On Fair Edge Deletion Problems (2009)

24.

Lampis, M.: Algorithmic meta-theorems for restrictions of treewidth. Algorithmica 64(1), 19–37 (2012). http://dx.doi.org/10.1007/s00453-011-9554-x CrossRefMathSciNetMATH

25.

Lampis, M.: Model checking lower bounds for simple graphs. Log. Methods Comput. Sci. 10(1) (2014). http://dx.doi.org/10.2168/LMCS-10(1:18)2014

26.

Langer, A., Reidl, F., Rossmanith, P., Sikdar, S.: Practical algorithms for MSO model-checking on tree-decomposable graphs. Comput. Sci. Rev. 13–14, 39–74 (2014)CrossRefMATH

27.

Libkin, L.: Elements of Finite Model Theory. Springer-Verlag, Berlin (2004). doi:10.1007/978-3-662-07003-1 CrossRefMATH

28.

Masařík, T., Toufar, T.: Parameterized complexity of fair deletion problems. In: Gopal, T.V., Jäger, G., Steila, S. (eds.) TAMC 2017. LNCS, vol. 10185, pp. 628–642. Springer, Heidelberg (2017). doi:10.1007/978-3-319-55911-7_45 CrossRef

29.

Matoušek, J., Nešetřil, J.: Invitation to Discrete Mathematics, 2nd edn. Oxford University Press, Oxford (2009)MATH

30.

Pilipczuk, M.: Problems parameterized by treewidth tractable in single exponential time: a logical approach. In: Murlak, F., Sankowski, P. (eds.) MFCS 2011. LNCS, vol. 6907, pp. 520–531. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22993-0_47 CrossRef

31.

Szeider, S.: Monadic second order logic on graphs with local cardinality constraints. ACM Trans. Comput. Log. 12(2), 12 (2011). http://doi.acm.org/10.1145/1877714.1877718 CrossRefMathSciNetMATH

Title: Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity
Authors: Dušan Knop
Martin Koutecký
Tomáš Masařík
Tomáš Toufar
Publisher: Springer International Publishing
Book: Graph-Theoretic Concepts in Computer Science
Print ISBN: 978-3-319-68704-9

Electronic ISBN: 978-3-319-68705-6

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-68705-6_26

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner