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.