1
$\begingroup$

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

relative_error distribution

$\endgroup$
1
  • $\begingroup$ I can provide the python code for the test if anyone wishes to further the statistical study. $\endgroup$
    – ArnoV
    Jan 16, 2021 at 13:16

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Do you know any other method of approximation? I really need to give an approximate answer to this problem, any idea is welcome ! $\endgroup$
    – ArnoV
    Jan 17, 2021 at 11:35
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Jan 17, 2021 at 19:04
  • $\begingroup$ 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 $\endgroup$
    – ArnoV
    Jan 17, 2021 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.