<p>The disjoint paths problem: given $G$ and $k$ pairs of nodes, are there node disjoint paths connecting the given pairs. Parameterized by $k$, in FPT when $G$ is undirected from the seminal work of Robertson and Seymour. NP-Hard for $k=2$ when $G$ is directed - from work of Fortune, Hopcroft and Wylie (1980).</p>

CC BY-SA 3.0
2015-01-27T02:33:20.233Z
2015-01-28T00:57:55.020Z
2015-01-28T00:57:55.020Z
Chandra Chekuri
<p>Computing tree-width and tree decomposition in undirected graphs is FPT w.r.t width parameter. Many digraph width measures (or their corresponding game) are equivalent to tree-width in undirected graphs. Exact complexity class of many of them are not known but recently shown that <a href="http://arxiv.org/abs/1411.2438" rel="nofollow">DAG-Width is PSPACE-complete</a>. </p>

CC BY-SA 3.0
2015-01-28T09:29:36.823Z
2015-01-28T09:29:36.823Z
Saeed
<p>Steiner tree parameterized by clique-width is solvable in single exponential running time <span class="math-container">$c^k\operatorname{poly}(n)$</span> (also the vertex-weighted version).</p>
<p>However, the edge-weighted version is NP-hard even for <span class="math-container">$cw=2$</span> (and hence, probably not in XP), since you can reduce the general unweighted version of this problem to the edge-weighted version on a clique by assigning weight 0 to existing edges and weight 1 to the rest.</p>
<p>This phenomenon is common for edge-weighted problems parameterized by clique-width.</p>

CC BY-SA 4.0
2024-07-03T13:23:08.630Z
2024-07-03T13:23:08.630Z
Narek Bojikian
<p>Following the equivalent questions regarding NP-Completeness (see the <a href="https://cstheory.stackexchange.com/questions/21130/problems-that-are-easy-on-unweighted-graphs-but-hard-for-weighted-graphs">weight question</a> and the <a href="https://cstheory.stackexchange.com/questions/20989/graph-problems-which-are-np-complete-on-directed-graphs-but-polynomial-on-undire">directed question</a>), I was wondering how parameterized problems are affected by these attributes.</p>

<blockquote>
  <ul>
  <li><strong>Which $NP$-hard graph problems are $W[1]$-Hard on directed graphs, but fixed parameter tractable on undirected graphs?</strong></li>
  </ul>
</blockquote>

<hr>

<blockquote>
  <ul>
  <li><strong>Which $NP$-hard graph problems are $W[1]$-Hard on weighted graphs, but fixed parameter tractable on unweighted graphs?</strong></li>
  </ul>
</blockquote>

<hr>

<p>OK, so we have problems which becomes harder on the directed version. What about weights? Can they make parameterized problem harder?</p>

CC BY-SA 3.0
2015-01-27T22:48:36.890Z
There are some cases which are not exactly same and not known. e.g computing tree width in undirected graphs is fpt but computing directed tree width is not known if is fpt. but in the johnson etal work there is an fpt 3 approximation.
Saeed
CC BY-SA 3.0
2015-01-27T22:57:50.190Z
Or another case if we play DAG width game in undirected graphs we obtain a tree decomposition. But computing tree width is FPT but computing dag width is [PSPACE-complete](http://arxiv.org/abs/1411.2438).
Saeed
<cc.complexity-theory><graph-algorithms><parameterized-complexity><fixed-parameter-tractable>
Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?
R B
# Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?

(Asked by: username_0 on 2015-01-26)

Following the equivalent questions regarding NP-Completeness (see the [weight question](https://cstheory.stackexchange.com/questions/21130/problems-that-are-easy-on-unweighted-graphs-but-hard-for-weighted-graphs) and the [directed question](https://cstheory.stackexchange.com/questions/20989/graph-problems-which-are-np-complete-on-directed-graphs-but-polynomial-on-undire)), I was wondering how parameterized problems are affected by these attributes.

> * **Which $NP$-hard graph problems are $W[1]$-Hard on directed graphs, but fixed parameter tractable on undirected graphs?**

---

> * **Which $NP$-hard graph problems are $W[1]$-Hard on weighted graphs, but fixed parameter tractable on unweighted graphs?**

---

OK, so we have problems which becomes harder on the directed version. What about weights? Can they make parameterized problem harder?

**Tags:** cc.complexity-theory, graph-algorithms, parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: There are some cases which are not exactly same and not known. e.g computing tree width in undirected graphs is fpt but computing directed tree width is not known if is fpt. but in the johnson etal work there is an fpt 3 approximation.  
> **username_1**: Or another case if we play DAG width game in undirected graphs we obtain a tree decomposition. But computing tree width is FPT but computing dag width is [PSPACE-complete](http://arxiv.org/abs/1411.2438).  

---

## 3 answers

### Answer by username_2 on 2015-01-27. Score: 9

The disjoint paths problem: given $G$ and $k$ pairs of nodes, are there node disjoint paths connecting the given pairs. Parameterized by $k$, in FPT when $G$ is undirected from the seminal work of Robertson and Seymour. NP-Hard for $k=2$ when $G$ is directed - from work of Fortune, Hopcroft and Wylie (1980).


---

### Answer by username_1 on 2015-01-28. Score: 3

Computing tree-width and tree decomposition in undirected graphs is FPT w.r.t width parameter. Many digraph width measures (or their corresponding game) are equivalent to tree-width in undirected graphs. Exact complexity class of many of them are not known but recently shown that [DAG-Width is PSPACE-complete](http://arxiv.org/abs/1411.2438).


---

### Answer by username_3 on 2024-07-03. Score: 0

Steiner tree parameterized by clique-width is solvable in single exponential running time $c^k\operatorname{poly}(n)$ (also the vertex-weighted version).

However, the edge-weighted version is NP-hard even for $cw=2$ (and hence, probably not in XP), since you can reduce the general unweighted version of this problem to the edge-weighted version on a clique by assigning weight 0 to existing edges and weight 1 to the rest.

This phenomenon is common for edge-weighted problems parameterized by clique-width.


---

