12
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Commented Jan 27, 2015 at 22:48
  • 2
    $\begingroup$ 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. $\endgroup$
    – Saeed
    Commented Jan 27, 2015 at 22:57

3 Answers 3

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

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.