I would like to cite a paper/report/etc that solves the following problem polynomially in $n$:

Given a weighted directed graph $G=(V,E)$, $|V|=n$, of bounded treewidth $k \in \mathbb{N}$ and a source-destination pair $s,t\in V$, find a longest path (not walk) from $s$ to $t$.

The corresponding Wikipedia article (https://en.wikipedia.org/wiki/Longest_path_problem#Parameterized_complexity) implies that it is possible:

the longest path problem is [...] fixed-parameter tractable when parameterized by the treewidth of the graph

Sadly, my knowledge of treewidth-techniques is rather small.

I found the following paper, but it is on undirected (?unweighted?) graphs:

Is it easy to see that this technique also extends to directed weighted graphs? What happens when the weights are encoded in binary, i.e., they can be exponential in $n$?

There is also a nice discussion here, but it also seems to rely on undirected (?unweighted?) graphs.

Thank you!

  • 2
    $\begingroup$ Yes: once you have read into the area and once you know the material, it is easy to see that longest weighted path problem can be handled by the same dynamic programming approach as the unweighted version. $\endgroup$
    – Gamow
    Apr 14 '17 at 17:03
  • $\begingroup$ Thank you, Gamow. Would you say that there is anything to look out for, that a novice might miss, that happens due to exponential weights or directed graphs? $\endgroup$ Apr 14 '17 at 17:22
  • 1
    $\begingroup$ Read the papers! The resulting algorithms are very simple; they just tabulate a lot of partial solutions and glue them together. $\endgroup$
    – Gamow
    Apr 14 '17 at 17:31

Your Answer

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

Browse other questions tagged or ask your own question.