  We introduce and discuss the Minimum Capacity-Preserving Subgraph (MCPS)
problem: given a directed graph and a retention ratio $\alpha \in (0,1)$, find
the smallest subgraph that, for each pair of vertices $(u,v)$, preserves at
least a fraction $\alpha$ of a maximum $u$-$v$-flow's value. This problem
originates from the practical setting of reducing the power consumption in a
computer network: it models turning off as many links as possible while
retaining the ability to transmit at least $\alpha$ times the traffic compared
to the original network.
  First we prove that MCPS is NP-hard already on directed acyclic graphs
(DAGs). Our reduction also shows that a closely related problem (which only
considers the arguably most complicated core of the problem in the objective
function) is NP-hard to approximate within a sublogarithmic factor already on
DAGs. In terms of positive results, we present a simple linear time algorithm
that solves MCPS optimally on directed series-parallel graphs (DSPs). Further,
we introduce the family of laminar series-parallel graphs (LSPs), a
generalization of DSPs that also includes cyclic and very dense graphs. Not
only are we able to solve MCPS on LSPs in quadratic time, but our approach also
yields straightforward quadratic time algorithms for several related problems
such as Minimum Equivalent Digraph and Directed Hamiltonian Cycle on LSPs.
