Capacity-preserving subgraphs of directed flow networks

DOI10.1007/978-3-031-34347-6_14arXiv2303.17274OpenAlexW4379117816MaRDI QIDQ6182901FDOQ6182901

Authors: Markus Chimani, Max Ilsen 

Publication date: 22 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We introduce and discuss the Minimum Capacity-Preserving Subgraph (MCPS) problem: given a directed graph and a retention ratio $alphain(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.

Full work available at URL: https://arxiv.org/abs/2303.17274

Recommendations

• An efficiently solvable case of the minimum weight equivalent subgraph problem
• scientific article; zbMATH DE number 4064732
• Minimum cost flows with minimum quantities
• scientific article; zbMATH DE number 1003248

zbMATH Keywords

inapproximabilitymaximum flowseries-parallel graphsminimum equivalent digraph

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Title not available (Why is that?)
• Reducibility among combinatorial problems
• A linear time \(\frac{5}{3}\)-approximation for the minimum strongly-connected spanning subgraph problem
• Approximating the minimum strongly connected subgraph via a matching lower bound
• Design of Survivable Networks: A survey
• The Transitive Reduction of a Directed Graph
• The Recognition of Series Parallel Digraphs
• On sparse spanners of weighted graphs
• An efficiently solvable case of the minimum weight equivalent subgraph problem
• Computationally Related Problems
• Analytical approach to parallel repetition
• Topology of series-parallel networks
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Approximating the Minimum Equivalent Digraph
• Telecommunications network design: Technology impacts and future directions
• Graph spanners: a tutorial review
• Title not available (Why is that?)
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• Directed Steiner problems with connectivity constraints

This page was built for publication: Capacity-preserving subgraphs of directed flow networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6182901)