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)

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.

  • $\begingroup$ 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." 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 cs.stackexchange.com? $\endgroup$
    – J..y B..y
    Jul 17, 2023 at 9:42
  • $\begingroup$ @J..yB..y highly unlikely this is an undergraduate programming exercise.. $\endgroup$ Jul 17, 2023 at 14:06
  • $\begingroup$ @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... $\endgroup$
    – sally
    Jul 18, 2023 at 9:47
  • 2
    $\begingroup$ Not a full answer, but it might be NP-hard considering this paper $\endgroup$ Jul 18, 2023 at 20:30


Your Answer

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

Browse other questions tagged or ask your own question.