<p>I want to know whether the following problem is NP-complete;</p>
<blockquote>
<p>Given an undirected graph <span class="math-container">$G=(V,E)$</span> with weights on each edge <span class="math-container">$e\in E$</span>, and two vertices <span class="math-container">$s,t\in V$</span>, find two disjoint paths <span class="math-container">$P_1, P_2$</span> connecting <span class="math-container">$s,t$</span> such that the product <span class="math-container">$W(P_1)W(P_2)$</span> is minimum, where <span class="math-container">$W(P)$</span> is the sum of edge weights along the path <span class="math-container">$P$</span>.</p>
</blockquote>
<p>I have searched for such problems, and found that minimizing the sum <span class="math-container">$W(P_1)+W(P_2)$</span> can be done in polynomial time. (<a href="https://commons.wikimedia.org/wiki/File:Bhandari%27s_Shortest_Pair_of_Edge-Disjoint_Shortest_Paths_Algorithm.jpg" rel="nofollow noreferrer">Bhandari's Shortest Pair of Edge-Disjoint Shortest Paths Algorithm</a>)</p>
<p>But I cannot find any polynomial time algorithm minimizing the product. Also, I cannot figure out how to prove the problem stated above is NP-complete.
I appreciate any advice. Thank you in advance.</p>

CC BY-SA 4.0
2023-07-17T09:42:57.490Z
This question looks like an undergraduate programming exercise, which would not be adequate for cstheory SE ("a question and answer site for professional researchers in theoretical computer science and related fields." https://cstheory.stackexchange.com/tour). If it is not, sharing some information about where it comes from would motivate your peers to work on it. If it is, maybe you should ask on a more adequate stack exchange channel, like https://cs.stackexchange.com/?
J.y B.y
CC BY-SA 4.0
2023-07-17T14:06:14.530Z
@J..yB..y highly unlikely this is an undergraduate programming exercise..
user3508551
CC BY-SA 4.0
2023-07-18T09:47:48.400Z
@J..yB..y I'm sorry if the question isn't qualified for this site. I came up with the problem and couldn't find any resource about similar problem. I agree with user3508551 about the difficulty...
sally
CC BY-SA 4.0
2023-07-18T20:30:53.427Z
Not a full answer, but it might be NP-hard considering [this paper](https://link.springer.com/chapter/10.1007/3-540-62559-3_30)
Bernardo Subercaseaux
<graph-algorithms><np-complete>
Two disjoint paths with minimum product of weights -NP-completeness
sally
# Two disjoint paths with minimum product of weights -NP-completeness

(Asked by: username_0 on 2023-07-12)

I want to know whether the following problem is NP-complete;

> Given an undirected graph $G=(V,E)$ with weights on each edge $e\in E$, and two vertices $s,t\in V$, find two disjoint paths $P\_1, P\_2$ connecting $s,t$ such that the product $W(P\_1)W(P\_2)$ is minimum, where $W(P)$ is the sum of edge weights along the path $P$.

I have searched for such problems, and found that minimizing the sum $W(P\_1)+W(P\_2)$ can be done in polynomial time. ([Bhandari's Shortest Pair of Edge-Disjoint Shortest Paths Algorithm](https://commons.wikimedia.org/wiki/File:Bhandari%27s_Shortest_Pair_of_Edge-Disjoint_Shortest_Paths_Algorithm.jpg))

But I cannot find any polynomial time algorithm minimizing the product. Also, I cannot figure out how to prove the problem stated above is NP-complete.
I appreciate any advice. Thank you in advance.

**Tags:** graph-algorithms, np-complete
> **Comments:**
> **username_1**: This question looks like an undergraduate programming exercise, which would not be adequate for cstheory SE ("a question and answer site for professional researchers in theoretical computer science and related fields." https://cstheory.stackexchange.com/tour). If it is not, sharing some information about where it comes from would motivate your peers to work on it. If it is, maybe you should ask on a more adequate stack exchange channel, like https://cs.stackexchange.com/?  
> **username_2**: @J..yB..y highly unlikely this is an undergraduate programming exercise..  
> **username_0**: @J..yB..y I'm sorry if the question isn't qualified for this site. I came up with the problem and couldn't find any resource about similar problem. I agree with user3508551 about the difficulty...  
> **username_3**: Not a full answer, but it might be NP-hard considering [this paper](https://link.springer.com/chapter/10.1007/3-540-62559-3_30)  

---

## 0 answers

