<p>Treewidth plays an important role in FPT algorithms, in part because many problems are FPT parameterized by treewidth. A related, more restricted, notion is that of pathwidth. If a graph has pathwidth $k$, it also has treewidth at most $k$, while in the converse direction, treewidth $k$ only implies pathwidth at most $k\log n$ and this is tight.</p>

<p>Given the above, one may expect that there may be a significant algorithmic advantage to graphs of bounded pathwidth. However, it seems that most problems which are FPT for one parameter are FPT for the other. I'm curious to know of any counter-examples to this, that is, problems which are "easy" for pathwidth but "hard" for treewidth.</p>

<p>Let me mention that I was motivated to ask this question by running into a recent paper by Igor Razgon ("On OBDDs for CNFs of bounded treewidth", KR'14) which gave an example of a problem with a $2^{k}n$ solution when $k$ is the pathwidth and a (roughly) $n^k$ lower bound when $k$ is the treewidth. I am wondering if there exist other specimens with this behavior.</p>

<p><strong>Summary:</strong> Are there any examples of natural problems which are W-hard parameterized by treewidth but FPT parameterized by pathwidth? More broadly, are there examples of problems whose complexity is known/believed to be much better when parameterized by pathwidth instead of treewidth?</p>

CC BY-SA 3.0
2014-11-26T15:51:15.463Z
There are problems that are easy on paths but NP-Hard on trees. These include minimum multicut and maximum integer multiflow.
Chandra Chekuri
CC BY-SA 3.0
2014-11-26T16:43:16.107Z
@ChandraChekuri This is a good point, but do the algorithms for paths for such problems usually generalize to pathwidth? For example, for max integer multiflow, I think this is not the case. Garg, Vazirani and Yannakakis proved NP-hardness for trees in "Primal-dual approximation algorithms for integral flow and multicut in trees". The reduction there uses a tree of height 3. This means that the problem is NP-hard for constant pathwidth.
Michael Lampis
CC BY-SA 3.0
2014-11-26T17:48:13.687Z
This is again not a clean answer to the original question. The flow-cut gap in pathwidth k graphs is known to be bounded by f(k) for some function f via a result of Lee and Sidiropoulos. It is an important open problem whether such a result holds for treewidth. The case k=3 is open for treewidth.
Chandra Chekuri
CC BY-SA 3.0
2014-11-27T20:55:15.227Z
The best algorithm for Hamiltonian Cycle parameterized by pathwidth has runtime $(2+\sqrt{2})^{pw}$ (http://arxiv.org/abs/1211.1506 ) while the best treewidth one is $4^{tw}$ (http://arxiv.org/abs/1103.0534 )  This is probably just a gap waiting to be closed, though.
daniello
CC BY-SA 4.0
2020-09-11T13:38:57.743Z
Please post the answer you found: [Grundy Coloring](https://arxiv.org/abs/2008.07425) (distinguishes treewidth from pathwidh).
Cyriac Antony
<parameterized-complexity><treewidth><graph-minor>
Algorithmic advantages of pathwidth over treewidth
Michael Lampis
# Algorithmic advantages of pathwidth over treewidth

(Asked by: username_0 on 2014-11-26)

Treewidth plays an important role in FPT algorithms, in part because many problems are FPT parameterized by treewidth. A related, more restricted, notion is that of pathwidth. If a graph has pathwidth $k$, it also has treewidth at most $k$, while in the converse direction, treewidth $k$ only implies pathwidth at most $k\log n$ and this is tight.

Given the above, one may expect that there may be a significant algorithmic advantage to graphs of bounded pathwidth. However, it seems that most problems which are FPT for one parameter are FPT for the other. I'm curious to know of any counter-examples to this, that is, problems which are "easy" for pathwidth but "hard" for treewidth.

Let me mention that I was motivated to ask this question by running into a recent paper by Igor Razgon ("On OBDDs for CNFs of bounded treewidth", KR'14) which gave an example of a problem with a $2^{k}n$ solution when $k$ is the pathwidth and a (roughly) $n^k$ lower bound when $k$ is the treewidth. I am wondering if there exist other specimens with this behavior.

**Summary:** Are there any examples of natural problems which are W-hard parameterized by treewidth but FPT parameterized by pathwidth? More broadly, are there examples of problems whose complexity is known/believed to be much better when parameterized by pathwidth instead of treewidth?

**Tags:** parameterized-complexity, treewidth, graph-minor
> **Comments:**
> **username_1**: There are problems that are easy on paths but NP-Hard on trees. These include minimum multicut and maximum integer multiflow.  
> **username_0**: @ChandraChekuri This is a good point, but do the algorithms for paths for such problems usually generalize to pathwidth? For example, for max integer multiflow, I think this is not the case. Garg, Vazirani and Yannakakis proved NP-hardness for trees in "Primal-dual approximation algorithms for integral flow and multicut in trees". The reduction there uses a tree of height 3. This means that the problem is NP-hard for constant pathwidth.  
> **username_1**: This is again not a clean answer to the original question. The flow-cut gap in pathwidth k graphs is known to be bounded by f(k) for some function f via a result of Lee and Sidiropoulos. It is an important open problem whether such a result holds for treewidth. The case k=3 is open for treewidth.  
> **username_2**: The best algorithm for Hamiltonian Cycle parameterized by pathwidth has runtime $(2+\sqrt{2})^{pw}$ (http://arxiv.org/abs/1211.1506 ) while the best treewidth one is $4^{tw}$ (http://arxiv.org/abs/1103.0534 )  This is probably just a gap waiting to be closed, though.  
> **username_3**: Please post the answer you found: [Grundy Coloring](https://arxiv.org/abs/2008.07425) (distinguishes treewidth from pathwidh).  

---

## 0 answers

