Acta Informatica Компьютерные сети и коммуникации

Directed capacity-preserving subgraphs: hardness and exact polynomial algorithms

Markus Chimani, Max Ilsen
Springer Nature · 2025-01-28 · DOI 10.1007/s00236-024-00475-7

Аннотация

Abstract We introduce and discuss the problem: given a directed graph with edge capacities $$\textit{cap} $$ cap and a retention ratio $$\alpha \in (0,1)$$ α ∈ ( 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 is NP-hard already on a restricted set of directed acyclic graphs (DAGs) with unit edge capacities. 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 two algorithms that solve optimally on directed series-parallel graphs (DSPs): a simple linear-time algorithm for the special case of unit edge capacities and a cubic-time dynamic programming algorithm for the general case of non-uniform edge capacities. Further, we introduce the family of laminar series-parallel graphs (LSPs), a generalization of DSPs that also includes cyclic and very dense graphs. Their properties allow us to solve on LSPs by employing our DSP-algorithms as subroutines. In addition, we give a separate quadratic-time algorithm for on LSPs with unit edge capacities that also yields straightforward quadratic time algorithms for several related problems such as and on LSPs.

Читать у издателя →