Theoretical Computer Science

# Logspace algorithms on graphs with bounded tree width

Tree width measures how close a graph is to a tree. It is NP-hard to compute tree width. The best known approximation algorithm achieves $O(\sqrt{{\log}n})$ factor.

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 ?

## Solution

Tutte polynomial is an example.

This is a generalization of the chromatic polynomial, which itself is a #P-hard problem in any reasonable formulation. In

Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width, S. D. Noble, Combinatorics, Probability and Computing, 1998,

a polynomial time algorithm is given where the time complexity is about $O(f(k)n^{4+\epsilon})$, where $k$ is the treewidth and $n$ is the number of nodes. Related works can be seen in here. For a survey, there are article on Arxiv, where the complexity issue discussed in section 8.

It seems that the problem cannot be expressed in MSO2 directly, though I'm not familiar with the detailed definitions... Hope this problem is what you need!

• +0 – According to the paper, it is a function in $k$ with order about $O(2^{(k^{3+\epsilon})})$. — Oct 20, 2010 at 03:12