# minimising Longest-Path in DAG

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

Define the number of edges as \$E.

Given $$0:

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.