{"ID":6138349,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-11T16:11:27.930961336Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07600","arxiv_id":"2607.07600","title":"Approximability of Electrical Distribution Network Reconfiguration for General Graphs","abstract":"Electrical distribution networks are regional, medium- and low-voltage power grids connecting energy sources to individual households and businesses with given power demands. While these networks contain redundant power lines for reliability, they are typically operated in a radial (spanning tree) configuration by opening and closing switches on the lines. The challenge is to find a spanning tree that minimizes the sum of the resistive power losses: The power loss of a line $e$ is its resistance $r(e)$ times the squared current $f(e)^2$ flowing across the line. We study approximation algorithms for this problem, known as Distribution Network Reconfiguration (DNR). We give an $n$-approximation algorithm and, via a new NP-hardness for planar Balanced Connected Partition with a fixed number of parts, show that no $n^{1-\\varepsilon}$-approximation is possible even on planar graphs unless P $=$ NP, for any $\\varepsilon\u003e0$. Since the approximation hardness holds only if there are many sources, we focus on $k$-DNR with $k$ sources; this is motivated by traditional distribution networks, where oftentimes $k = 1$. For $2$-DNR, we give an approximation lower bound of $Ω(\\log^2 n)$ conditioned on P $\\neq$ NP. For $1$-DNR, which is equivalent to finding an uncapacitated confluent flow minimizing the squared Euclidean norm, we prove APX-hardness and give an $\\mathcal{O}(\\sqrt{n})$-approximation for uniform line resistances, answering an open question by Gupta et al. [Math. Program. 2022].","short_abstract":"Electrical distribution networks are regional, medium- and low-voltage power grids connecting energy sources to individual households and businesses with given power demands. While these networks contain redundant power lines for reliability, they are typically operated in a radial (spanning tree) configuration by open...","url_abs":"https://arxiv.org/abs/2607.07600","url_pdf":"https://arxiv.org/pdf/2607.07600v1","authors":"[\"Christian Wallisch\",\"Andrea Benigni\",\"Carsten Hartmann\",\"Leon Kellerhals\"]","published":"2026-07-08T16:18:17Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"eess.SY\"]","methods":"[]","has_code":false}