Optimal Reduction of Two-Terminal Directed Acyclic Graphs
Wolfgang W. Bein, Jerzy Kamburowski, Matthias F. M. Stallmann · SIAM Journal on Computing · 1992
Algorithms for series-parallel graphs can be extended to arbitrary two-terminal dags if node reductions are used along with series and parallel reductions. A node reduction contracts a vertex with unit in-degree (out-degree) into its sole incoming (outgoing) neighbor. This paper gives an $O(n^{2.5} )$ algorithm for minimizing node reductions, based on vertex cover in a transitive auxiliary graph. Applications include the analysis of PERT networks, dynamic programming approaches to network problems, and network reliability. For NP-hard problems one can obtain algorithms that are exponential only in the minimum number of node reductions rather than the number of vertices. This gives improvements if the underlying graph is nearly series-parallel.