1
$\begingroup$

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.

Improve this question
New contributor
Amran Tomer is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
3
  • $\begingroup$ (Seems to "prefer" paths with not much more than $\alpha\times E$ costly edges.) $\endgroup$ – greybeard Jun 8 at 21:53
  • $\begingroup$ What do you meet by that @greybeard? You have no control over the initial longest-paths $\endgroup$ – Amran Tomer Jun 8 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 at 22:29

Your Answer

Amran Tomer is a new contributor. Be nice, and check out our Code of Conduct.

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.