# Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?

Following the equivalent questions regarding NP-Completeness (see the weight question and the directed question), 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?

• 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. Commented Jan 27, 2015 at 22:48
• 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. Commented Jan 27, 2015 at 22:57

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).
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.