Deleting Vertices To Bound Path Length.pdf

Deleting Vertices To Bound Path Length Doowon Paik+ Sudhakar Reddy++ Sartaj Sahni+ University of Florida University of Iowa University of Florida Abstract 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. Keywords And Phrases Vertex deletion, directed acyclic graphs, rooted trees, series-parallel graphs, NP-hard __________________ + Research supported, in part, by the National Science Foundation under grants DCR-84-20935 and MIPS-86-17374. ++ Research supported, in part, by SDIO/IST Contract No. N00014-90-J-1793 managed by US Office of Naval Research. 1 21 Introduction A variety of vertex deletion problems formulated on graphs and digraphs are known to be NP- hard [KRIS79]. In this paper, we propose a new formulation of the vertex deletion problem that is applicable to edge weighted directed acyclic graphs (wdag). In this formulation, we are interested in deleting the smallest number of vertices from the wdag such that the resulting wdag has no path of length δ where δ is an input to the problem. This problem is a natural variant of the vertex splitting problem for weighted wdags that we studied in [PAIK90]. In the vertex splitting problem, we are split the fewest number of vertices so that the resulting wdag has no path of length δ. When a vertex is split, two vertices are created. The incoming edges of the original vertex are attached to one of these and the outgoing edges to the other. The vertex splitting problem can be used to model several VLSI design prob- lems such as the selection of flip-flops for scan paths in partial scan designs and the placement of signal boosters in lossy circuits. The vertex deletion