1
$\begingroup$

We have a strongly connected directed graph where each edge has positive integer weights. We are also given a $B \in \mathbb{N}$. Does there exist a strongly connected subgraph where sum of edge weights $\leq B$?

I'm not sure what NP-Complete problem to use. I tried subset sum, but it takes exponential time to build the graph I had in mind (yes/no tree with edge cost being the numbers in subset sum problem, and a final edge to root at end of every decision sequence). Any ideas? Is there a better NP-Complete problem to use?

$\endgroup$
9
  • 1
    $\begingroup$ I don't think it's NP-hard. If there is a negative cycle, you are done. Otherwise, compute all pairwise distances $d(u,v)$. Now simply find if there is a pair of vertices such that $d(u,v)+d(v,u) \le B$. This cycle will be the required subgraph. $\endgroup$ – user114966 Apr 17 at 21:35
  • $\begingroup$ There is no requirement that each edge $(u,v)$ has a backwards edge $(v,u).$ $\endgroup$ – LTM Apr 17 at 21:41
  • $\begingroup$ $d(u,v)$ is a distance between $u$ and $v$, i.e. the weight of the shortest path from $u$ to $v$, not the weight of the edge between them. $\endgroup$ – user114966 Apr 17 at 21:52
  • $\begingroup$ @Dmitry The fact that the shortest (with minimal total weight) path from $u$ to $v$ may cross other vertices means that you must keep those vertices in the subgraph (and the corresponding edges). That may increase the total weight of the strongly connected subgraph you consider. $\endgroup$ – Nathaniel Apr 17 at 23:16
  • 1
    $\begingroup$ @Dmitry If the subgraph is induced, the problem is indeed NP-complete (proved by Yannakakis in 1978 researchgate.net/publication/…) $\endgroup$ – Nathaniel Apr 17 at 23:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.