<p><a href="http://en.wikipedia.org/wiki/Tutte_polynomial"><strong>Tutte polynomial</strong></a> is an example. </p>

<p>This is a generalization of the <a href="http://en.wikipedia.org/wiki/Chromatic_polynomial">chromatic polynomial</a>, which itself is a #P-hard problem in any reasonable formulation. In </p>

<blockquote>
  <p><a href="http://bura.brunel.ac.uk/bitstream/2438/817/1/tutte.pdf">Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width</a>, S. D. Noble, 
  Combinatorics, Probability and Computing, 1998,</p>
</blockquote>

<p>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 <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6V00-3V0YRSD-3&amp;_user=10&amp;_coverDate=08/28/1998&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=88a9eb1a5d9f2063c103a19058a4a1ea&amp;searchtype=a">here</a>. For a survey, there are article on <a href="http://arxiv.org/PS_cache/arxiv/pdf/0803/0803.3079v2.pdf">Arxiv</a>, 
where the complexity issue discussed in section 8.</p>

<p>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!</p>

CC BY-SA 2.5
2010-10-20T03:02:03.763Z
What is the function f?
Michael Blondin
CC BY-SA 2.5
2010-10-20T03:12:54.650Z
According to the paper, it is a function in $k$ with order about $O(2^{(k^{3+\epsilon})})$.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-10-21T23:05:00.343Z
Makowski says that "all the graph polynomials studied in
the literature are SOL-definable", and gives a formulation of Tutte polynomial in terms of SOL, page 15 of "From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials." In "Algorithmic uses of the Feferman-Vaught theorem" he extends Courcelle's theorem to show tractability for SOL-definable polynomials on bounded tree-width graphs.
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-20T02:33:51.050Z
2010-10-20T02:33:51.050Z
Hsien-Chih Chang 張顯之
<p><a href="http://en.wikipedia.org/wiki/Tree_decomposition">Tree width</a> measures how close a graph is to a tree. It is NP-hard to compute tree width. The best known <a href="http://kintali.wordpress.com/2010/01/28/approximating-treewidth/">approximation</a> algorithm achieves $O(\sqrt{{\log}n})$ factor.</p>

<p>Courcelle's theorem states that <em>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</em>. A recent <a href="http://www.eccc.uni-trier.de/report/2010/062/">paper</a> showed that Courcelle's theorem still holds when "linear time" is replaced with "logspace". However, this does not settle the space complexity of <a href="http://en.wikipedia.org/wiki/Graph_isomorphism_problem">Graph Isomorphism</a> on graphs with bounded tree width. The best known <a href="http://arxiv.org/abs/1001.0383">result</a> puts it in LogCFL.</p>

<p>Are there other problems that are :</p>

<ul>
<li>NP-hard (or not known to be in P) on general graphs, and</li>
<li>known to be solvable in linear/polynomial time on graphs with bounded tree width, and</li>
<li>NOT known to be in LogSpace ?</li>
</ul>

CC BY-SA 2.5
2010-09-16T02:37:15.497Z
What is the $n$ mentioned in the approximation factor?
gphilip
CC BY-SA 2.5
2010-09-16T03:03:53.420Z
$n$ is the number of vertices in the input graph.
Shiva Kintali
CC BY-SA 2.5
2010-09-16T14:06:35.497Z
We can, in general, do better than $O(\sqrt{\log n})$ in approximating treewidth. The best polynomial-time approximation algorithm that I am aware of achieves an $O(\sqrt{\log w})$ approximation factor, where $w$ is the treewidth of the graph. See Feige, Hajiaghayi, and Lee, _Improved approximation algorithms for minimum-weight vertex separators_ , STOC 2005.
gphilip
<cc.complexity-theory><ds.algorithms><graph-theory><space-bounded><treewidth>
Logspace algorithms on graphs with bounded tree width
Shiva Kintali
# Logspace algorithms on graphs with bounded tree width

(Asked by: username_0 on 2010-09-16)

[Tree width](http://en.wikipedia.org/wiki/Tree_decomposition) measures how close a graph is to a tree. It is NP-hard to compute tree width. The best known [approximation](http://kintali.wordpress.com/2010/01/28/approximating-treewidth/) 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](http://www.eccc.uni-trier.de/report/2010/062/) 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](http://en.wikipedia.org/wiki/Graph_isomorphism_problem) on graphs with bounded tree width. The best known [result](http://arxiv.org/abs/1001.0383) 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 ?

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, space-bounded, treewidth
> **Comments:**
> **username_1**: What is the $n$ mentioned in the approximation factor?  
> **username_0**: $n$ is the number of vertices in the input graph.  
> **username_1**: We can, in general, do better than $O(\sqrt{\log n})$ in approximating treewidth. The best polynomial-time approximation algorithm that I am aware of achieves an $O(\sqrt{\log w})$ approximation factor, where $w$ is the treewidth of the graph. See Feige, Hajiaghayi, and Lee, _Improved approximation algorithms for minimum-weight vertex separators_ , STOC 2005.  

---

## 1 answers

### Answer by username_2 on 2010-10-20. Score: 15 | Accepted answer

[**Tutte polynomial**](http://en.wikipedia.org/wiki/Tutte_polynomial) is an example.

This is a generalization of the [chromatic polynomial](http://en.wikipedia.org/wiki/Chromatic_polynomial), which itself is a #P-hard problem in any reasonable formulation. In

> [Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width](http://bura.brunel.ac.uk/bitstream/2438/817/1/tutte.pdf), 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](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V00-3V0YRSD-3&_user=10&_coverDate=08/28/1998&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=88a9eb1a5d9f2063c103a19058a4a1ea&searchtype=a). For a survey, there are article on [Arxiv](http://arxiv.org/PS_cache/arxiv/pdf/0803/0803.3079v2.pdf),
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!

> **Comments:**
> **username_3**: What is the function f?  
> **username_2**: According to the paper, it is a function in $k$ with order about $O(2^{(k^{3+\epsilon})})$.  
> **username_4**: Makowski says that "all the graph polynomials studied in the literature are SOL-definable", and gives a formulation of Tutte polynomial in terms of SOL, page 15 of "From a Zoo to a Zoology: Towards a General Theory of Graph Polynomials." In "Algorithmic uses of the Feferman-Vaught theorem" he extends Courcelle's theorem to show tractability for SOL-definable polynomials on bounded tree-width graphs.  

---

