2010/10/01 by Michael Elberfeld, Andreas Jakoby, Till Tantau · 1 citation
Computer Science · #Advanced Graph Theory Research
paper · doi:10.1109/focs.2010.21
openalex publication_date 2010/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Bodlaender's Theorem states that for every k there is a linear-time algorithm that decides whether an input graph has tree width k and, if so, computes a width-k tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula φ and for every k there is a linear-time algorithm that decides whether a given logical structure A of tree width at most k satisfies φ. We prove that both theorems still hold when "linear time" is replaced by "logarithmic space." The transfer of the powerful theoretical framework of monadic second-order logic and bounded tree width to logarithmic space allows us to settle a number of both old and recent open problems in the log space world.