19
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 8
    $\begingroup$ There are problems that are easy on paths but NP-Hard on trees. These include minimum multicut and maximum integer multiflow. $\endgroup$
    – Chandra Chekuri
    Commented Nov 26, 2014 at 15:51
  • 3
    $\begingroup$ @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. $\endgroup$
    – Michael Lampis
    Commented Nov 26, 2014 at 16:43
  • $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Commented Nov 26, 2014 at 17:48
  • 3
    $\begingroup$ The best algorithm for Hamiltonian Cycle parameterized by pathwidth has runtime $(2+\sqrt{2})^{pw}$ (arxiv.org/abs/1211.1506 ) while the best treewidth one is $4^{tw}$ (arxiv.org/abs/1103.0534 ) This is probably just a gap waiting to be closed, though. $\endgroup$
    – daniello
    Commented Nov 27, 2014 at 20:55
  • 3
    $\begingroup$ Please post the answer you found: Grundy Coloring (distinguishes treewidth from pathwidh). $\endgroup$
    – Cyriac Antony
    Commented Sep 11, 2020 at 13:38

1 Answer 1

Reset to default
7
$\begingroup$

It is shown that [1] the Mixed Chinese Postman Problem (MCPP) parameterized by pathwidth is $W[1]$-hard, even if all edges and arcs of the input graph $G$ have weight $1$ and is FPT with respect to treedepth. This is the first problem are aware of that has been shown to be $W[1]$-hard with respect to treewidth but FPT with respect to treedepth. Note that the pathwidth of a graph lies between its treewidth and treedepth.

The Steiner Multicut problem, which asks, given an undirected graph $G$, a collection $T = \{T_1, . . . , T_t\}$, $T_i ⊆ V(G)$, of terminal sets of size at most $p$, and an integer $k$, whether there is a set $S$ of at most $k$ edges or nodes such that of each set $T_i$ at least one pair of terminals is in different connected components of $G \ S$.

Node Steiner Multicut, Edge Steiner Multicut, and Restr. Node Steiner Multicut are $W[1]$-hard for the parameter $k$, even if $p = 3$ and $tw(G) = 2$ [2].

[1] https://core.ac.uk/download/pdf/77298274.pdf

[2] http://drops.dagstuhl.de/opus/volltexte/2015/4911/pdf/11.pdf

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.