# 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. – Saeed Jan 27 '15 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. – Saeed Jan 27 '15 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).