10
$\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?

$\endgroup$
  • $\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 Jan 27 '15 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 Jan 27 '15 at 22:57
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).

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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