Minimum power assignment breaks connections in weighted graphs efficiently
An Exact Polynomial-Time Algorithm for the Minimum Shared-Power Edge Cut Problem
Data Structures and Algorithms
Summary
The paper solves a puzzle about cutting connections in a network while using the least total power. Previously, people only had ways to find approximate solutions quickly, but the exact best method was unknown. The authors discovered a new way to look at the problem using mathematics about matchings and submodular functions. This breakthrough means the perfect solution can now be found in a time that grows reasonably with the network size. Their work answers an open question about how hard this problem really is.
What this means in practice
- •For network reliability engineers: Compute exact minimum power configurations to disconnect critical node pairs in weighted network graphs.
- •For infrastructure security teams: Plan precise disruption strategies in weighted infrastructures where edge failures depend on vertex power assignments.
A theory result. No direct application yet.
Authors
Quanlong Niu, Wei Liang, Riheng Jia, Zhao Zhang
Abstract
The Minimum Shared-Power Edge Cut (MSPEC) problem seeks to disconnect two designated terminals with minimum total power by assigning powers to graph vertices and deleting every edge for which the sum of the powers at its endpoints reaches its edge weight. Previous work gave a fully polynomial-time approximation scheme for this problem, while its exact computational complexity remained open. We prove that general MSPEC with nonnegative edge weights can be solved exactly in polynomial time. Specifically, we first use linear programming duality for each fixed cut to reformulate MSPEC as minimizing the maximum terminal-relaxed matching weight over all $s$-$t$ cuts. Then, we construct a terminal-copy extended graph that transforms the maximum-weight matching model with unconstrained terminal capacities for a fixed cut into an equivalent ordinary maximum-weight matching model. Next, we extend the submodularity of the unweighted maximum-matching cut function to nonnegative edge weights and prove that the restriction obtained by fixing the terminal copies on prescribed sides remains submodular. Consequently, MSPEC reduces to exact submodular function minimization. Once an optimal cut is obtained, a corresponding optimal power assignment can be recovered. This result resolves the open question concerning the exact computational complexity of general MSPEC.