# Approximate max weight path in directed graph

## Context

This question is related to the fact one can't use Bellman-Ford to find max weight paths in directed graphs with cycles. The reason is that giving a new graph $$\tilde{G}$$ with negative weights (e.g. $$\tilde{w}_{ij} = - w_{ij}$$) will result in cycles with negative sum, thus no minimum cost walk exists in $$\tilde{G}$$.

## General question

How well can we approximate the maximum weight path between $$i$$ and $$j$$ in $$G$$, using the shortest path algorithm on a graph $$\tilde{G}$$ with transformed weights $$\tilde{w}_{ij}$$ ? In my case, one has $$w_{ij}\in\mathbb{N}\setminus\{0\}$$. The transformed weights $$\tilde{w}_{ij}$$ can be obtained using any function, but I assume a decreasing function $$f$$ is well adapted so that $$w < w' \iff f(w) > f(w')$$.

## My approach

I am currently trying to use $$f(w) = \dfrac{1}{w}$$, in this context we have two important paths given a fixed path length $$L$$.

Denote a path $$p = (i_0i_1, i_1i_2, i_2i_3, \dots i_{L-1}i_L$$) with weights $$W = (w^{(1)}, w^{(2)}, w^{(3)}, \dots, w^{(L)})$$,

denote the maximum weight path of length $$L$$ by $$p^*$$ with weights $$W^*$$ achieving $$W^* = \arg\max_W\{\mathtt{Cost}(W)\} = \arg\max_W \sum_{k=1}^L w^{(k)}$$ and the path $$p_*$$ achieving minimum transformed cost with weights $$W_*$$ $$W_* = \arg\min_W \sum_{k=1}^L \tilde{w}^{(k)} = \arg\min_W \sum_{k=1}^L f(w^{(k)}) = \arg\min_W \sum_{k=1}^L \dfrac{1}{w^{(k)}}$$

## Specific question

In this specific context, do we have the approximation $$\mathtt{Cost}(W^*) \approx \mathtt{Cost}(W_*)$$ ?

Or is it "very wrong" to replace $$W^*$$ by $$W_*$$ ? What would be the distribution of the relative error defined as $$E_r = \dfrac{\lvert\mathtt{Cost}(W^*) - \mathtt{Cost}(W_*)\rvert}{\mathtt{Cost}(W^*)}$$

## Statistical analysis

I have tried a quick statistical analysis as follows:

• Letting $$L\in\{3,4,5,6,7,8\}$$
• sampling $$w \sim \mathrm{Uniform}(1,w_{\max})$$
• The value for $$w_{\max}$$ was also picked from the set $$\{50, 100, 150, 200, 500\}$$
• for each combination of $$L,w_{\max}$$ I computed $$10^5$$ values of $$W^*, W_*$$ using $$10^3$$ candidate weights $$W_i$$

The results:

• In $$80.8\%$$ of cases we have $$\mathtt{Cost}(W^*) = \mathtt{Cost}(W_*)$$ and even better $$W^*=W_*$$
• When computing the relative error $$E_r$$ one finds that $$82.6\%$$ of error values are less than $$0.001$$, $$89.7\%$$ less than $$0.01$$ and $$99.9\%$$ less than $$0.1$$

The histogram for $$E_r > 0$$ is as follows

• I can provide the python code for the test if anyone wishes to further the statistical study. – ArnoV Jan 16 at 13:16

## 1 Answer

You can't. That approach is a dead end. Finding the maximum (simple) path is NP-hard, by reduction from Hamiltonian cycle. See, e.g., How to prove NP-hardness of a longest-path problem?, How is the Longest Path Problem NP complete?, Longest cycle in a digraph, https://en.wikipedia.org/wiki/Longest_path_problem. It is also known to be hard to approximate, so you shouldn't expect any such simple approach to give a good approximation for all graphs.

• Do you know any other method of approximation? I really need to give an approximate answer to this problem, any idea is welcome ! – ArnoV Jan 17 at 11:35
• @user715586, "It is also known to be hard to approximate". If you have a practical problem, I suggest posting a new question with details of the problem, parameters, problem sizes, etc. – D.W. Jan 17 at 19:04
• My problem involves finding the most popular path using the count/frequency of the edges. There shouldn't more than 1000 nodes and a few thousand edges. Cycles are very common. I posted another question which uses another approach – ArnoV Jan 17 at 19:07