Directed Capacity-Preserving Subgraphs: Hardness and Exact Polynomial Algorithms

Markus Chimani, Max Ilsen

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 ea…