<p>I deleted my previous answer because there were some inaccuracies. Also I am going to assume that either, you are looking for the longest walk, with any nodes as endpoints, or you are looking for a walk between two specified nodes <span class="math-container">$s$</span> and <span class="math-container">$t$</span> and for all nodes <span class="math-container">$v$</span> in the graph, there exists a directed path from <span class="math-container">$v$</span> to <span class="math-container">$t$</span>.</p>
<p>Your question number (2) can be solved in polynomial time. By negating the costs, the longest walk becomes the shortest walk. The Bellman-Ford algorithm will return the shortest walk between two nodes <span class="math-container">$s$</span> and <span class="math-container">$t$</span> or determine that the problem is unbounded and provide a negatively weighted dicycle (which is a positively weighted in the original graph). If you don't have specified endpoints, you can simply run the algorithm for each (ordered) pair of nodes.</p>
<p>As for your question number (1) even with non-negative weights, the problem is NP-complete if <span class="math-container">$k\geq 2$</span> via a reduction from the Partition Problem: Given a finite multiset of positive integers <span class="math-container">$S =\{a_1,\ldots,a_n\}$</span> determine if there exists <span class="math-container">$I \subseteq \{1,\ldots,n\}$</span> such that <span class="math-container">$\sum_{i \in I} a_i = \sum_{i \not\in I} a_i$</span>.</p>
<p>The reduction works as follows: The graph is obtained by taking a path with <span class="math-container">$n$</span> directed edges, and creating a parallel copy of each edge. Label the vertices <span class="math-container">$v_0, v_1, \ldots, v_n$</span>. For each <span class="math-container">$i \in \{1,\ldots,n\}$</span> a weight of <span class="math-container">$(a_i ,0)$</span> is placed on one of the arcs from <span class="math-container">$v_{i-1}$</span> to <span class="math-container">$v_i$</span> and a weight of <span class="math-container">$(0, a_i)$</span> is placed on the other. Now the Partition Problem can be solved by determining if this graph has a walk of length greater than or equal to <span class="math-container">$$\left(\frac{1}{2}\sum_{i=1}^n a_i,\, \frac{1}{2}\sum_{i=1}^n a_i\right)$$</span></p>

CC BY-SA 4.0
2024-03-18T18:18:35.573Z
very helpful answer, thank you
user1868607
CC BY-SA 4.0
2024-03-18T22:38:05.863Z
One doesn't need Bellman-Ford for finding the longest walk in a directed graph with non-negative edge-lengths. One can do it by computing the strong connected components and the associated DAG in total linear time.
Chandra Chekuri
CC BY-SA 4.0
2024-03-19T15:25:01.920Z
@ChandraChekuri part (2) of the original question does not constrain the edge-lengths to be non-negative.
NaturalLogZ
CC BY-SA 4.0
2024-03-19T15:34:12.060Z
I see, my mistake, got confused by part 1. Thanks. It is still useful to know that if one has non-negative lengths then the problem is still interesting and can be solved faster.
Chandra Chekuri
CC BY-SA 4.0
2024-03-18T16:35:48.057Z
2024-03-18T16:35:48.057Z
NaturalLogZ
<p>I want to know if the following variants of the longest path problem over directed graphs have polynomial time algorithm.</p>
<p>As I understand it, the longest path problem doesn't allow repetition of edges. However, in my problems I want to decide whether my weighted graph has a &quot;walk&quot;, i.e. I allow repeating edges.</p>
<p>I was wondering if the decision version of the longest walk problem have polynomial time algorithms when:</p>
<ol>
<li><p>The weights are in <span class="math-container">$\mathbb{Q_0^+}^k$</span>, that is they are tuple of non-negative rational numbers. The goal is to see whether there is a walk between two nodes such that the length of the walk <span class="math-container">$\vec{c}$</span> is larger than a vector <span class="math-container">$\vec{o}$</span>. Here the comparison between the two vectors is done componentwise.</p>
</li>
<li><p>What happens if the weights are in <span class="math-container">$\mathbb{Q}$</span>? That is, if they have only one dimension but they can be arbitrary rationals.</p>
</li>
</ol>
<p>Part of the problem is that I haven't seen this &quot;longest walk problem&quot; discussed in the literature. So any references are welcome.</p>

CC BY-SA 4.0
2024-03-18T15:01:09.647Z
These are not research level questions. Can be answered via topics taught in a beginning graduate level algorithms class (or a strong undergrad algorithms class). The problem is NP-Complete if k \ge 2 and is in P for k=1.
Chandra Chekuri
CC BY-SA 4.0
2024-03-18T15:12:53.800Z
@ChandraChekuri you mean problem 1) is NP-complete for $k \ge 2$? (note the non-negative weights). I don't think reduction from knapsack works here.
user1868607
<ds.algorithms><graph-theory><np-hardness><shortest-path>
Polynomial time algorihtms for two variants of the decision version of longest walk problem
user1868607
# Polynomial time algorihtms for two variants of the decision version of longest walk problem

(Asked by: username_0 on 2024-03-18)

I want to know if the following variants of the longest path problem over directed graphs have polynomial time algorithm.

As I understand it, the longest path problem doesn't allow repetition of edges. However, in my problems I want to decide whether my weighted graph has a "walk", i.e. I allow repeating edges.

I was wondering if the decision version of the longest walk problem have polynomial time algorithms when:

1. The weights are in $\mathbb{Q\_0^+}^k$, that is they are tuple of non-negative rational numbers. The goal is to see whether there is a walk between two nodes such that the length of the walk $\vec{c}$ is larger than a vector $\vec{o}$. Here the comparison between the two vectors is done componentwise.
2. What happens if the weights are in $\mathbb{Q}$? That is, if they have only one dimension but they can be arbitrary rationals.

Part of the problem is that I haven't seen this "longest walk problem" discussed in the literature. So any references are welcome.

**Tags:** ds.algorithms, graph-theory, np-hardness, shortest-path

> **Comments:**
> **username_1**: These are not research level questions. Can be answered via topics taught in a beginning graduate level algorithms class (or a strong undergrad algorithms class). The problem is NP-Complete if k \ge 2 and is in P for k=1.  
> **username_0**: @ChandraChekuri you mean problem 1) is NP-complete for $k \ge 2$? (note the non-negative weights). I don't think reduction from knapsack works here.  

---

## 1 answers

### Answer by username_2 on 2024-03-18. Score: 4 | Accepted answer

I deleted my previous answer because there were some inaccuracies. Also I am going to assume that either, you are looking for the longest walk, with any nodes as endpoints, or you are looking for a walk between two specified nodes $s$ and $t$ and for all nodes $v$ in the graph, there exists a directed path from $v$ to $t$.

Your question number (2) can be solved in polynomial time. By negating the costs, the longest walk becomes the shortest walk. The Bellman-Ford algorithm will return the shortest walk between two nodes $s$ and $t$ or determine that the problem is unbounded and provide a negatively weighted dicycle (which is a positively weighted in the original graph). If you don't have specified endpoints, you can simply run the algorithm for each (ordered) pair of nodes.

As for your question number (1) even with non-negative weights, the problem is NP-complete if $k\geq 2$ via a reduction from the Partition Problem: Given a finite multiset of positive integers $S =\{a\_1,\ldots,a\_n\}$ determine if there exists $I \subseteq \{1,\ldots,n\}$ such that $\sum\_{i \in I} a\_i = \sum\_{i \not\in I} a\_i$.

The reduction works as follows: The graph is obtained by taking a path with $n$ directed edges, and creating a parallel copy of each edge. Label the vertices $v\_0, v\_1, \ldots, v\_n$. For each $i \in \{1,\ldots,n\}$ a weight of $(a\_i ,0)$ is placed on one of the arcs from $v\_{i-1}$ to $v\_i$ and a weight of $(0, a\_i)$ is placed on the other. Now the Partition Problem can be solved by determining if this graph has a walk of length greater than or equal to $$\left(\frac{1}{2}\sum\_{i=1}^n a\_i,\, \frac{1}{2}\sum\_{i=1}^n a\_i\right)$$

> **Comments:**
> **username_0**: very helpful answer, thank you  
> **username_1**: One doesn't need Bellman-Ford for finding the longest walk in a directed graph with non-negative edge-lengths. One can do it by computing the strong connected components and the associated DAG in total linear time.  
> **username_2**: @ChandraChekuri part (2) of the original question does not constrain the edge-lengths to be non-negative.  
> **username_1**: I see, my mistake, got confused by part 1. Thanks. It is still useful to know that if one has non-negative lengths then the problem is still interesting and can be solved faster.  

---

