Courcelle's theorem states that any property of graphs definable in monadic second-order logic (MSO2) can be decided in linear time on any class of graphs of bounded tree width. A recent paper showed that Courcelle's theorem still holds when "linear time" is replaced with "logspace". However, this does not settle the space complexity of Graph Isomorphism on graphs with bounded tree width. The best known result puts it in LogCFL.
Are there other problems that are :
- NP-hard (or not known to be in P) on general graphs, and
- known to be solvable in linear/polynomial time on graphs with bounded tree width, and
- NOT known to be in LogSpace ?