Directed Capacity-Preserving Subgraphs: Hardness and Exact Polynomial Algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912230042238976 |
|---|---|
| author | Chimani, Markus Ilsen, Max |
| author_facet | Chimani, Markus Ilsen, Max |
| contents | We introduce and discuss the Minimum Capacity-Preserving Subgraph (MCPS) problem: given a directed graph and a retention ratio $α\in (0,1)$, find the smallest subgraph that, for each pair of vertices $(u,v)$, preserves at least a fraction $α$ 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 $α$ times the traffic compared to the original network.
First we prove that MCPS 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 MCPS 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 MCPS on LSPs by employing our DSP-algorithms as subroutines. In addition, we give a separate quadratic-time algorithm for MCPS on LSPs with unit edge capacities that also yields straightforward quadratic time algorithms for several related problems such as Minimum Equivalent Digraph and Directed Hamiltonian Cycle on LSPs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_17274 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Directed Capacity-Preserving Subgraphs: Hardness and Exact Polynomial Algorithms Chimani, Markus Ilsen, Max Data Structures and Algorithms Discrete Mathematics 05C21 (Primary) 68R10, 05C20 (Secondary) G.2.2; F.2.2 We introduce and discuss the Minimum Capacity-Preserving Subgraph (MCPS) problem: given a directed graph and a retention ratio $α\in (0,1)$, find the smallest subgraph that, for each pair of vertices $(u,v)$, preserves at least a fraction $α$ 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 $α$ times the traffic compared to the original network. First we prove that MCPS 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 MCPS 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 MCPS on LSPs by employing our DSP-algorithms as subroutines. In addition, we give a separate quadratic-time algorithm for MCPS on LSPs with unit edge capacities that also yields straightforward quadratic time algorithms for several related problems such as Minimum Equivalent Digraph and Directed Hamiltonian Cycle on LSPs. |
| title | Directed Capacity-Preserving Subgraphs: Hardness and Exact Polynomial Algorithms |
| topic | Data Structures and Algorithms Discrete Mathematics 05C21 (Primary) 68R10, 05C20 (Secondary) G.2.2; F.2.2 |
| url | https://arxiv.org/abs/2303.17274 |