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

<p>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$.</p>

<p>The corresponding Wikipedia article (<a href="https://en.wikipedia.org/wiki/Longest_path_problem#Parameterized_complexity" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Longest_path_problem#Parameterized_complexity</a>)  implies that it is possible: </p>

<blockquote>
  <p>the longest path problem is [...] fixed-parameter tractable when parameterized by the treewidth of the graph</p>
</blockquote>

<p>Sadly, my knowledge of treewidth-techniques is rather small.</p>

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

<ul>
<li><a href="https://people.csail.mit.edu/virgi/hybridsoda.pdf" rel="nofollow noreferrer">Confronting Hardness Using a Hybrid Approach</a>: Cites a paper of <a href="http://www.sciencedirect.com/science/article/pii/S0196677483710011" rel="nofollow noreferrer">Bodlaender</a> (in Section 2.2.1), where Theorem 2.2 states that the longest path problem is solvable in $O(2^k k! n)$ (assuming a treewidth decomposition is given)</li>
</ul>

<p>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$?</p>

<p>There is also a nice discussion <a href="https://cstheory.stackexchange.com/questions/34331/parametrized-complexity-of-the-2-long-paths-problem">here</a>, but it also seems to rely on undirected (?unweighted?) graphs.</p>

<p>Thank you!</p>

CC BY-SA 3.0
2017-04-14T17:03:42.730Z
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.
Gamow
CC BY-SA 3.0
2017-04-14T17:22:27.517Z
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?
cs_student_273
CC BY-SA 3.0
2017-04-14T17:31:07.963Z
Read the papers! The resulting algorithms are very simple; they just tabulate a lot of partial solutions and glue them together.
Gamow
<cc.complexity-theory><graph-algorithms><treewidth><fixed-parameter-tractable><dynamic-programming>
Paper regarding the complexity of the longest path problem on weighted directed graphs of bounded treewidth
cs_student_273
# Paper regarding the complexity of the longest path problem on weighted directed graphs of bounded treewidth

(Asked by: username_0 on 2017-04-14)

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:

* [Confronting Hardness Using a Hybrid Approach](https://people.csail.mit.edu/virgi/hybridsoda.pdf): Cites a paper of [Bodlaender](http://www.sciencedirect.com/science/article/pii/S0196677483710011) (in Section 2.2.1), where Theorem 2.2 states that the longest path problem is solvable in $O(2^k k! n)$ (assuming a treewidth decomposition is given)

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](https://cstheory.stackexchange.com/questions/34331/parametrized-complexity-of-the-2-long-paths-problem), but it also seems to rely on undirected (?unweighted?) graphs.

Thank you!

**Tags:** cc.complexity-theory, graph-algorithms, treewidth, fixed-parameter-tractable, dynamic-programming
> **Comments:**
> **username_1**: 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.  
> **username_0**: 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?  
> **username_1**: Read the papers! The resulting algorithms are very simple; they just tabulate a lot of partial solutions and glue them together.  

---

## 0 answers

