We examine the vertex deletion problem for weighted directed acyclic graphs (wdags). The objective is to delete the fewest number of vertices so that the resulting wdag has no path of length > δ. Several simplified versions of this problem are shown to be NP-hard. However, the problem is solved in linear time when the wdag is a rooted tree and in quadratic time when the wdag is a series-parallel graph.
For the vertex deletion version of DED(k), Paik et al. REF gave linear time and quadratic time algorithms for rooted trees and series-parallel graphs respectively.
Deleting Vertices to Bound Path Length
IEEE Trans. Computers
Mathematics Computer Science