Courcelle's theorem

In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth.[1][2][3] The result was first proved by Bruno Courcelle in 1990[4] and independently rediscovered by Borie, Parker & Tovey (1992).[5] It is considered the archetype of algorithmic meta-theorems.[6][7]

  1. ^ Eger, Steffen (2008), Regular Languages, Tree Width, and Courcelle's Theorem: An Introduction, VDM Publishing, ISBN 9783639076332.
  2. ^ Courcelle, Bruno; Engelfriet, Joost (2012), Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach (PDF), Encyclopedia of Mathematics and its Applications, vol. 138, Cambridge University Press, ISBN 9781139644006, Zbl 1257.68006.
  3. ^ Downey, Rodney G.; Fellows, Michael R. (2013), "Chapter 13: Courcelle's theorem", Fundamentals of parameterized complexity, Texts in Computer Science, London: Springer, pp. 265–278, CiteSeerX 10.1.1.456.2729, doi:10.1007/978-1-4471-5559-1, ISBN 978-1-4471-5558-4, MR 3154461, S2CID 23517218.
  4. ^ Courcelle, Bruno (1990), "The monadic second-order logic of graphs. I. Recognizable sets of finite graphs", Information and Computation, 85 (1): 12–75, doi:10.1016/0890-5401(90)90043-H, MR 1042649, Zbl 0722.03008
  5. ^ Borie, Richard B.; Parker, R. Gary; Tovey, Craig A. (1992), "Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families", Algorithmica, 7 (5–6): 555–581, doi:10.1007/BF01758777, MR 1154588, S2CID 22623740.
  6. ^ Kneis, Joachim; Langer, Alexander (2009), "A practical approach to Courcelle's theorem", Electronic Notes in Theoretical Computer Science, 251: 65–81, doi:10.1016/j.entcs.2009.08.028.
  7. ^ Lampis, Michael (2010), "Algorithmic meta-theorems for restrictions of treewidth", in de Berg, Mark; Meyer, Ulrich (eds.), Proc. 18th Annual European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 6346, Springer, pp. 549–560, doi:10.1007/978-3-642-15775-2_47, ISBN 978-3-642-15774-5, Zbl 1287.68078.