0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Mar 18 at 15:01
  • $\begingroup$ @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. $\endgroup$ Mar 18 at 15:12

1 Answer 1

4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ very helpful answer, thank you $\endgroup$ Mar 18 at 18:18
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 18 at 22:38
  • $\begingroup$ @ChandraChekuri part (2) of the original question does not constrain the edge-lengths to be non-negative. $\endgroup$ Mar 19 at 15:25
  • $\begingroup$ 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. $\endgroup$ Mar 19 at 15:34

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.