# 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