Assume we have weighted DAG (directed-acycle-graph), source s and target t.

Define the number of edges as $E$.

Given $0<\alpha<1$:

Choose $\alpha*E$ edges to cut their weight by half so that the longest path from s to t is minimized.

Personal note: We've been asked this question by our professor. I assume the problem is NP-Hard. We are looking for some heuristics that will gives us good results, not necessarily optimal.

Any suggestions will be welcome.

  • $\begingroup$ (Seems to "prefer" paths with not much more than $\alpha\times E$ costly edges.) $\endgroup$
    – greybeard
    Jun 8, 2021 at 21:53
  • $\begingroup$ What do you meet by that @greybeard? You have no control over the initial longest-paths $\endgroup$ Jun 8, 2021 at 22:17
  • $\begingroup$ It's just a musing about what difference $\alpha$ makes. Between paths with less than $\alpha\times E$ edges with weight>0: none. Path with most costly $\alpha\times E$ edges contributing less than half the cost: cost after halving greater than three quarters of the original. $\endgroup$
    – greybeard
    Jun 8, 2021 at 22: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.