<figure><img src="image_1.png" /></figure>

HAL
open science

# A polynomial algorithm for deciding the validity of an electrical distribution tree

Dominique Barth, Thierry Mautor, Dimitri Watel, Marc-Antoine Weisser

► To cite this version:

Dominique Barth, Thierry Mautor, Dimitri Watel, Marc-Antoine Weisser. A polynomial algorithm for deciding the validity of an electrical distribution tree. Information Processing Letters, 2022, 176, pp.106249. 10.1016/j.ipl.2022.106249. hal-04113551

HAL Id: hal-04113551

https://hal.science/hal-04113551

Submitted on 1 Jun 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A polynomial algorithm for deciding the validity of an electrical distribution tree

Dominique Barthª, Thierry Mautorª, Dimitri Watelᵇ,ᶜ,*, Marc-Antoine Weisserᵈ

ªDAVID, University of Versailles-St Quentin, Paris-Saclay University, 45 avenue des États-Unis, 78035, Versailles, France

ᵇENSIIE, 1 square de la Résistance, 91000, Evry, France

ᶜSAMOVAR, Telecom SudParis, 9 Rue Charles Fourier, 91000, Evry, France

ᵈLISN, CentraleSupelec, Paris-Saclay University, Rue Noetzlin, 91190, Gif-sur-Yvette, France

## Abstract

We consider power distribution networks containing source nodes producing electricity and nodes representing electricity consumers interconnected by a switched network. Configuring this network consists in deciding which switches are activated and the orientation of the links between these switches, so as to obtain a directed graph from the producer nodes to the consumer nodes. This graph is valid if the electric flow it induces satisfies the demand of each consumer without exceeding the production capacity of each source and the flow capacity of each switch. We show that deciding if such a valid configuration exists is polynomial in a tree.

**Keywords:** Complexity, Electrical network flow, Dynamic programming

## 1. Introduction

As the world becomes more and more electrical and the grids themselves more and more distributed, reliability and resilience are critical for consumers and grid managers. Especially, a grid needs to be in a configuration that can handle an outage. The configuration consists in deciding which components (lines, sources, switches) should be activated or not. Reliability can be defined as the capacity of the electrical system to supply electricity in quantity and with the quality requested by the users. Thus, to guarantee reliability, the objective here is to find the configuration satisfying the consumer demands [7, 10].

Configuration problems with reliability and resilience objectives are often considered through a graph theory point of view [1, 8]. Thus, some solutions seek

<footnote>*Corresponding author
Email addresses: dominique.barth@uvsq.fr (Dominique Barth), thierry.mautor@uvsq.fr (Thierry Mautor), dimitri.watel@ensiie.fr (Dimitri Watel), marc-antoine.weisser@centralesupelec.fr (Marc-Antoine Weisser)</footnote>
balanced configurations in terms of load power [9] and other ones to configure
the network in disjoint balanced subnetworks [10, 4, 5], in particular in the form
of spanning trees or sub-DAGS [6].

But, as the electric flow in a network is a direct consequence of the chosen
configuration [9], the objective is more to determine if there exists a configu-
ration satisfying the production and capacity constraints and the consumption
demands than to compute an electric flow in a graph (such as in [3]). Moreover,
the reliability of a network can be guaranteed by the existence of a configura-
tion which does not use all the capacity of each link and each switch in order to
contain the impact of the snowball effect during breakdowns. So given a desired
maximum percentage s, the problem we solve allows to determine if there is a
network configuration using each switch and each link at most s percent of its
capacity. In [2] we show that this existence problem is NP-complete for general
network topologies. In this article, we show that this problem is polynomial if
the network to be configured is a tree.

The paper is organized as follows. First, we define our model of power grid and the related computational problems. Then, we prove that the problem of finding a configuration is polynomial when the given network is a tree.

## 2. Model

The electrical distribution network is represented by a graph $G = (V, E)$
in which there are three types of vertices $S$, $W$ and $P$. $S$ represents the set
of *electrical sources* of the network; each vertex $s \in S$ is characterized by a
maximum production capacity denoted $Prod(s) > 0$. $W$ corresponds to the set
of *switches*; each vertex $w \in W$ has a maximum flow capacity $Cap(w)$. And
$P$ represents the set of *consumers*; each consumer $p \in P$ is characterized by a
called power $Pow(p)$. Edges in $E$ are the connections between these nodes. In
the following, we focus on graphs $G$ being trees.

An **orientation** $O$ of $G$ is a function associating each edge $[u, v] \in E$ with a couple $(u, v)$ or $(v, u)$ corresponding to the orientation of this edge. Note that for a given orientation, a switch is only activated if it belongs to at least one induced path from a source to a consumer. The activation of the switches can therefore be seen as a consequence of the orientation of the edges.

Given an orientation $O$, the network $G$ becomes a flow network with capacity on the switches only, with several sources and several sinks. Such a flow network can be made compatible with the one used in [3], but the fundamental difference lies in the constraints satisfied by the flow. In addition to the classical conservation and capacity constraints, the (electric) flow entering each switch of $W$ must be distributed equitably over all its incoming arcs (i.e., the arcs are considered equivalent to resistors with same resistance value). Consequently, the goal here is then not to determine a maximum flow since the flow is unique and set by the orientation: we can calculate it by going up from $P$. Our objective is to know if there exists an orientation for which the implied flow network from $G$ admits a unique flow satisfying the called powers of the consumers, respecting the production capacities of the sources and the flow capacities of the switches.
**Definition 1.** Let $\Gamma^+(v)$ and $\Gamma^-(v)$ be the sets of successors and predecessors of $v$, the flow $F(u, v)$ of an arc $(u, v)$ is

$$ \text{if} \qquad v \in W, \qquad v \in S, \qquad v \in P $$

$$ F(u, v) = \frac{\sum_{w \in \Gamma^+(v)} F(v, w)}{|\Gamma^-(v)|}, \quad \frac{\sum_{w \in \Gamma^+(v)} F(v, w)}{|\Gamma^-(v)| + 1}, \quad \frac{\sum_{w \in \Gamma^+(v)} F(v, w) + \text{Pow}(v)}{|\Gamma^-(v)|} $$

O satisfies the demand constraint if, for every consumer $p \in P$, there exists a path from any source to $p$. It satisfies the capacity constraint if $\sum_{w \in \Gamma^+(v)} F(v, w) \le \text{Cap}(v)$ for $v \in W$ and $\sum_{w \in \Gamma^+(v)} F(v, w) / (|\Gamma^-(v)| + 1) \le \text{Prod}(v)$ for $v \in S$. Note that the capacity constraint includes a production capacity constraint.

Determining if, for a given electrical network, there exists a feasible orientation (satisfying the demand and the capacity constraints) leads to the following decision problem, shown to be NP-complete for general graphs in [2].

**Problem 1 (VALID).** Given a graph $G = (V, E)$, three functions $\text{Prod}, \text{Cap}$ and $\text{Pow}$, does there exist an orientation $\mathcal{O}$ of $G$ satisfying the demand and the capacity constraints.

### 3. VALID is polynomial for trees

Let $\mathcal{I} = (T, \text{Cap}, \text{Prod}, \text{Pow})$ be a VALID instance where $T = (S \cup W \cup P, E)$ is a tree with $n$ nodes. We show in this section that there exists an algorithm solving that instance in time $O(n^4 \log(n))$. Given an edge $[u, v]$ of $T$, we write $T_u$ and $T_v$ as the two subtrees of $T$ in which this edge is removed.

#### 3.1. Minimum called power, maximum producible power

Assuming there exists a feasible orientation $\mathcal{O}$ of the edges, where $\mathcal{O}([u, v]) = (u, v)$, it means some power (maybe a null power) goes from $u$ to $v$. We try, in this part, to bound that power with two values, written $i(u, v)$ and $o(u, v)$ which are, respectively, the minimum input value that can be called by $v$ to feed all the customers in $T_v$ and the maximum output value that can be produced and sent through $u$ by all the sources in $T_u$. Figure 1 gives two examples.

**Definition 2.** Let $[u, v]$ be an edge of $T$, and let $T'_u$ be the tree where we replace $T_v$ by a fictive sink $v'$. The maximum producible power from $u$ to $v$, written $o(u, v)$, is the maximum value that can be assigned to $\text{Pow}(v')$ so that $T'_u$ remains valid. If the instance is not valid, even with $\text{Pow}(v') = 0$ then $o(u, v) = -\infty$.

**Definition 3.** Let $[u, v]$ be an edge of $T$, and let $T'_v$ be the tree where we replace $T_u$ by a fictive source $u'$. The minimum called power from $v$ to $u$, written $i(u, v)$, is the minimum value that can be assigned to $\text{Prod}(u')$ so that $T'_v$ remains valid. If the instance is not valid, even with $\text{Prod}(u') = +\infty$ then $i(u, v) = +\infty$.

Figure 2 illustrates those definitions. Note that, for each edge, there are four values $o(u, v)$, $o(v, u)$, $i(u, v)$ and $i(v, u)$. In Figure 1, on the left instance, we have $o(u, v) = 3$, and on the two instances, we have $i(u, v) = 2$.
<figure><img src="image_3.png" /><figcaption>Figure 1: The sources, switches and customers are respectively depicted by triangles, circles and squares. Each number alongside a node is either a production, a capacity or a called power depending on the type of the node. The instance on the left is valid and the other is not. In the two instances, we consider a solution where $[u, v]$ is directed toward $v$. In any feasible solution, $[v, p_v]$ is directed from $v$, otherwise no power goes to $p_v$. Depending whether $[s_v, v]$ is directed from or toward $s_v$, a power of 2 or 4 is called from $v$ to $u$: thus the power going from $u$ to $v$ should be at least 2. On the left part, we can see that $u$ receives power from $s_u$. A part of that power, of value 5 is needed to feed $p_u$. As no more than 8 can go through $u$, on the left instance $s_u$ cannot send a power greater than 3 to $v$ through $u$ and on the right instance $s_u$ cannot send a power greater than 1. Thus, on the right instance, no feasible solution with $[u, v]$ directed toward $v$, and, on the left instance, such an orientation remains conceivable.</figcaption></figure>

## 3.2. Usage of the functions i and o

Assuming there exists a polynomial algorithm $\mathcal{A}$ that computes $i(u, v)$, $o(u, v)$, $o(v, u)$ for every edge $[u, v]$ of $T$, we show hereinafter that determining if the instance $\mathcal{I}$ is VALID can be done in constant time.

**Lemma 1.** Let $[u, v] \in T$, let $\mathcal{O}$ be a feasible orientation such that $\mathcal{O}([u, v]) = (u, v)$ and let $F$ be the associated flow, then $i(u, v) \le F(u, v) \le o(u, v)$

*Proof.* Let $T_v'$ be the tree where we replace $T_u$ by a source $u'$ with production $F(u, v)$ and $O_v$ be $\mathcal{O}$ restricted to $T_v$. Then the flow on $T_v$ coincides with $F$ meaning that $O_v \cup \{[u', v] \to (u', v)\}$ is feasible. Thus $F(u, v) \ge i(u, v)$. Similarly, let $T_u'$ be the tree where we replace $T_v$ by a sink $v'$ with power $F(u, v)$ and $O_u$ be $\mathcal{O}$ restricted to $T_u$. Then the flow on $T_u$ coincides with $F$ meaning that $O_u \cup \{[u, v'] \to (u, v')\}$ is feasible. Thus $F(u, v) \le o(u, v)$. $\square$

**Lemma 2.** Let $[u, v]$ be any edge of $T$. The instance $\mathcal{I}$ is valid if and only if $i(u, v) \le o(u, v)$ or $i(v, u) \le o(v, u)$.

*Proof.* It is quite natural that an instance is not valid if somewhere the maximum value that can be produced ($o(u, v)$) is not sufficient to satisfy the minimum called value ($i(u, v)$). But, more formally, Lemma 1 proves that if $\mathcal{I}$ is valid then $i(u, v) \le o(u, v)$ or $i(v, u) \le o(v, u)$. We now assume that, without loss of generality, $i(u, v) \le o(u, v)$. According to Definition 3, if we replace $T_u$ by a

<figure><img src="image_4.png" /><figcaption>Figure 2: Illustration of Definitions 2 and 3.</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 3: The three subfigures depict a same instance on which all the values $o(u, v)$, $o(v, u)$, $i(u, v)$ and $i(v, u)$ are progressively computed for each edge $[u, v]$. The values $o(u, v)$ (respectively $i(u, v)$) are written $\le o$ (respectively $\ge i$) near $u$ (respectively $v$) on the arc $(u, v)$. A dotted arc represents an invalid orientation. The values $o(u, v)$ when $u$ is a leaf and $i(u, v)$ when $v$ is a leaf may be easily computed which is done on the left subfigure. For instance $i(w_2, s_2) = 0$: no power is called in $s_2$ and $o(s_2, w_2) = 22$: production of $s_2$. Then the neighbors of the leaves are considered, that is done on the middle subfigure. For instance, $o(p_2, w_3) = -\infty$: even if $s_3$ and $s_4$ are both directed to $p_2$, it is not enough to satisfy the called power $(2*8 < 18)$. And $i(w_3, p_2) = 6$: if we replace $w_3$ by a source, it should have a production of value at minimum 6 to feed $p_2$ ($J = \{s_3, s_4\}$ in the following Lemma 4). At the next step, a problem is detected on edge $[w_3, w_1]$ (subfigure on the right part). $o(w_3, w_1) = -\infty$ and $i(w_1, w_3) = 6$ (from $[p_2, w_3]$). And $o(w_1, w_3) = 5$: the most favorable case is given by the orientations $w_2 > w_1$ and $w_1 > s_1$ ($J = \{w_2\}$ in the following Lemma 3). According to Lemma 2, this makes the instance not valid.</figcaption></figure>

source $u'$ with production $i(u, v)$, there exists an orientation $O_v$ of $T_v$ such that the orientation $O_v \cup \{[u', v] \to (u', v)\}$ of $\{u'\} \cup T_v$ is feasible. Let $F_v$ be the flow in $T_v$ and let $f = F_v(u', v)$. Note that $f \le i(u, v)$. In addition, according to Definition 2, if we replace $T_v$ by a sink $v'$ with power $o(u, v)$, there exists an orientation $O_u$ of $T_u$ such that the orientation $O_u \cup \{[u, v'] \to (u, v')\}$ of $\{v'\} \cup T_u$ is feasible. Note that it is still feasible if we reduce the power of $v'$. As $f \le i(u, v) \le o(u, v)$, we can reduce it to $f$. Let $F_u$ be the flow in $T_u$.

We finally build the orientation $O = O_u \cup O_v \cup \{[u, v] \to (u, v)\}$. The flow $F$ coincides with $F_v$ on $T_v$. Thus, $F(u, v) = f$ and, then, the flow also coincides with $F_u$ on $T_u$. As a consequence, $O$ is feasible. $\square$

Figure 3 gives an example of the calculations of $i(u, v)$ and $o(u, v)$ and concludes that the instance is not valid.

### 3.3. Compute $i$ and $o$

In this section, we show that, for all $[u, v] \in E$, $i(u, v)$, $o(u, v)$, $i(v, u)$ and $o(v, u)$ can be computed in polynomial time. According to the definitions of $i$ and $o$, the value $i(u, v)$ (respectively $o(u, v)$) depends only on the nodes in $T_v$ (respectively $T_u$). The main idea of the algorithm is, as it is done in Figure 3, to use a bottom-up calculation from the leaves. We denote in this part the integer interval $\{a, a+1, \dots, b\}$ by $\llbracket a; b \rrbracket$.
<figure><img src="image_6.png" /><figcaption>Figure 4: Illustrations of Lemmas 3 and 4.</figcaption></figure>

**Lemma 3.** Let $(u_1, u_2, \dots, u_p)$ be the $p$ neighbors of $u$ in $T_u$. We set $o_j = o(u_j, u)$ and $i_j = i(u, u_j)$ and, for $J \subset [1; p]$.

$$C(J) = \mathrm{Cap}(u) \quad \text{and} \quad O(J) = |J| \cdot \min_{j \in J} o_j \quad \text{if } u \in W$$

$$C(J) = (|J| + 1) \cdot \mathrm{Prod}(u) \quad \text{and} \quad O(J) = (|J| + 1) \cdot \min_{j \in J} o_j \quad \text{if } u \in S$$

$$C(J) = +\infty \quad \text{and} \quad O(J) = |J| \cdot \min_{j \in J} o_j - \mathrm{Pow}(v) \quad \text{if } u \in P$$

$$\text{then } o(u, v) = \max_{J \subset [1; p]} \left( \min(C(J), O(J)) - \sum_{j \notin J} i_j \right)$$

If $J$ is empty, then we set $\min_{j \in J} o_j = 0$. If the calculation returns a negative value then $o(u, v) = -\infty$.

**Remark (Intuition).** The left part of Figure 4 illustrates Lemma 3. Given a subset $J$, the value $C(J)$ corresponds to the maximum flow that can go through $u$ (according to Definition 1) and $O(J)$ is the maximum value that can be equitably distributed over all the input arcs of $u$ corresponding to $J$ (and $u$ if it is a source). As the value requested by the neighbors directed from $u$ is at least $\sum_{j \notin J} i_j$, the maximum value that can go from $u$ to $v$ is $\min(C(J), O(J)) - \sum_{j \notin J} i_j$.

*Proof.* We first assume that $o(u, v) \neq -\infty$ then $o(u, v) \ge 0$. Without loss of generality, we assume that $u \in W$, the cases where $u \in S$ and $u \in P$ are similar. There exists a feasible orientation $O$ in the tree $T'_u$ where $T_v$ is replaced by a sink $v'$ with power $o(u, v)$. Let $F$ be the associated flow and $J = \{j \in [1; p] | O([u, u_j]) = (u_j, u)\}$ given by this orientation. Let $l(u) = o(u, v) + \sum_{j \notin J} F(u, u_j)$ be the output flow of $u$. Then $l(u) \le \mathrm{Cap}(u) = C(J)$ because $O$ is feasible. In addition, for every $j \in J$, $l(u) = |J| \cdot F(u, u_j)$. Moreover, by Lemma 1, for every $j \in J$, $o_j \ge F(u_j, u)$, and for every $j \notin J$, $i_j \le F(u, u_j)$. Consequently $o(u, v) + \sum_{j \notin J} i_j \le l(u) \le |J| \cdot \min_{j \in J} o_j = O(J)$. This implies that

$$o(u, v) \le \min(C(J), O(J)) - \sum_{j \notin J} i_j \le \max_{J \subset [1; p]} \min(C(J), O(J)) - \sum_{j \notin J} i_j$$

We now consider any $J \in [1; p]$ with $M(J) = \min(C(J), O(J)) - \sum_{j \notin J} i_j$. We want to show that $M(J) \le o(u, v)$. If $M(J) \le 0$, this is true as $o(u, v) \ge 0$. If
$M(J) \ge 0$, we set $Pow(v') = M(J)$. For every $j \in J$, $o_j \ne -\infty$ and for every $j \notin J$, $i_j \ne +\infty$, otherwise $M(J)$ would be negative. Thus, for every $j \in J$ (resp. $j \notin J$), there exists a feasible orientation $O_j$ of the tree $T'_{u_j}$ containing $T_{u_j}$ and a sink $u'$ with called power $o_j$ where $[u', u_j]$ is directed toward $u'$ (resp. a source $u'$ with production $i_j$ where $[u_j, u']$ is directed toward $u_j$). Let $O$ be the union of all those orientations to which we add $O([u, v']) = (u, v')$. By showing that $O$ is feasible for $T'_u$ if $Pow(v') = M(J)$, we prove the $M(J) \le o(u, v)$. Let $F$ be the associated flow. As $O$ coincides with $O_j$ in $T'_{u_j}$, then, firstly, for every $j \notin J$, $F(u, u_j) = i_j$, secondly, for $j \in J$, $|J| \cdot F(u_j, u) = M(J) + \sum_{j \notin J} i_j$ and, thirdly, this orientation is feasible if the capacity constraint is satisfied for $u$ and if $F(u_j, u) \le o_j$ for every $j \in J$. By definition of $M(J)$, we have $M(J) + \sum_{j \notin J} i_j \le C(J) = Cap(u)$: the capacity constraint of $u$ is satisfied. In addition, $M(J) + \sum_{j \notin J} i_j \le O(J) = |J| \min o_j$. This means that the flow $F(u_j, u) \le o_j$ if $j \in J$. This concludes the proof. Note that this last part also proves that, if $o(u, v) = -\infty$, then for all sets $J$, $M(J) < 0$. $\square$

**Lemma 4.** Let $(v_1, v_2, \dots, v_p)$ be the $p$ neighbors of $v$ in $T_v$. We set $o_j = o(v_j, v)$ and $i_j = i(v, v_j)$ and, for $J \subset \llbracket 1; p \rrbracket$.

$$D(J) = \frac{1}{|J| + 1} \cdot Cap(v) \quad \text{and} \quad I(J) = \frac{1}{|J| + 1} \sum_{j \notin J} i_j \quad \text{if } v \in W$$

$$D(J) = \mathrm{Prod}(v) \quad \text{and} \quad I(J) = \frac{1}{|J| + 2} \sum_{j \notin J} i_j \quad \text{if } v \in S$$

$$D(J) = +\infty \quad \text{and} \quad I(J) = \frac{1}{|J| + 1} \left( \sum_{j \notin J} i_j + \mathrm{Pow}(v) \right) \quad \text{if } v \in P$$

$$\text{then, } i(u, v) = \min_{J \subset \llbracket 1; p \rrbracket} \left( I(J) \text{ such that } I(J) \le \min(D(J), \min_{j \in J} o_j) \right)$$

If $J$ is empty then $\min_{j \in J} o_j = +\infty$. If there is no $J$ satisfying the inequality, then $i(u, v) = +\infty$.

**Remark (Intuition).** Figure 4 illustrates Lemma 4. Given a subset $J$, the values $\min(D(J), \min_{j \in J} o_j)$ and $I(J)$ corresponds to the maximum and minimum flows that can be equally distributed over all the input arcs of $v$ (and $v$ if it is a source). As $(u, v)$ enters $v$, the minimum value requested to $u$ by $v$ is $I(J)$.

*Proof.* We first assume that $i(u, v) \ne +\infty$. Without loss of generality, we assume that $v \in W$, the cases where $v \in S$ and $v \in P$ are similar. There exists a feasible orientation $O$ in the tree $T'_v$ where $T_u$ is replaced by a source $u'$ with production $i(u, v)$. Let $F$ be the associated flow and $J = \{j \in \llbracket 1; p \rrbracket | O([v, v_j]) = (v_j, v)\}$ given by this orientation. Let $l(v) = \sum_{j \notin J} F(v, v_j)$ be the output flow of $v$. Then $l(v) \le Cap(v)$ because $O$ is feasible. In addition, for every $j \in J$, $l(v) = (|J| + 1) \cdot F(v_j, v) = (|J| + 1) \cdot F(u', v) \le (|J| + 1) \cdot i(u, v)$. Moreover, by Lemma 1, for every $j \in J$, $o_j \ge F(v_j, v)$, and for every $j \notin J$, $i_j \le F(v, v_j)$.
Consequently $\sum_{j \notin J} i_j \le l(v)$, thus, firstly, $I(J) = \frac{1}{|J|+1} \sum_{j \notin J} i_j \le \frac{1}{|J|+1} l(v) \le \frac{1}{|J|+1} Cap(v) = D(J)$, secondly, for every $j \in J$, $I(J) \le \frac{1}{|J|+1} l(v) \le o_j$ and, thirdly, $I(J) \le \frac{1}{|J|+1} l(v) \le i(u, v)$. This implies that

$$i(u, v) \ge I(J) \ge \min_{J \subseteq [1; p]} \left( I(J) \text{ such that } I(J) \le \min(D(J), \min_{j \in J} o_j) \right)$$

We now consider any $J \in [1; p]$ such that $I(J) \le \min(D(J), \min_{j \in J} o_j)$. We want to show that $I(J) \ge i(u, v)$. We set $Prod(u') = I(J)$. For every $j \in J$, $o_j \ne -\infty$ and for every $j \notin J$, $i_j \ne +\infty$, otherwise $I(J)$ would be greater than $\min_{j \in J} o_j$. Consequently, for every $j \in J$ (respectively $j \notin J$), there exists a feasible orientation $O_j$ of the tree $T'_{v_j}$ containing $T_{v_j}$ and a sink $v'$ with called power $o_j$ where $[v', v_j]$ is directed toward $v'$ (respectively a source $v'$ with production $i_j$ where $[v_j, v']$ is directed toward $v_j$). Let $O$ be the union of all those orientations to which we add $O([u', v]) = (u', v)$. By showing that $O$ is feasible for $T'_v$ if $Prod(v') = I(J)$, we prove the $I(J) \ge i(u, v)$. Let $F$ be the associated flow. As $O$ coincides with $O_j$ in $T'_{v_j}$, then, firstly, for every $j \notin J$, $F(v, v_j) = i_j$, which means that, for every $j \in J$, $F(u', v) = F(v_j, v) = \frac{1}{|J|+1} \sum_{j \notin J} i_j = I(J)$ and secondly, this orientation is feasible if the capacity constraint is satisfied for $v$, if $F(v_j, v) \le o_j$ for every $j \in J$ and if $F(u', v) \le Prod(u')$. As $I(J) \le D(J)$, we have $\sum_{j \notin J} i_j \le Cap(v)$: the capacity constraint of $v$ is satisfied. In addition, for every $j \in J$, $F(v_j, v) \le I(J) \le o_j$, and $F(u', v) = I(J) = Prod(u')$. This concludes the proof. Note that this last part also proves that, if $i(u, v) = +\infty$, then no set $J$ satisfies $I(J) \le \min(D(J), \min_{j \in J} o_j)$. $\square$

**Lemma 5.** *Assuming $o_j = o(u_j, u)$ and $i_j = i(u, u_j)$ are given for every neighbor $u_j$ of $u$ in $T_u$, then $o(u, v)$ and $i(v, u)$ can be computed in time $O(n^3 \log(n))$.*

*Proof.* We first explain how to compute $o(u, v)$. We renumber the neighbors $u_j$ by increasing order of $o_j$ in time $O(p \log p)$. Let $d \in [0; p]$, we compute the set $J_d$ width $|J_d| = d$ maximizing $V(J_d) = \min(C(J_d), O(J_d)) - \sum_{j \notin J_d} i_j$. If $d = 0$, then $J_d = \emptyset$. Otherwise, for each $k \in [1; p-d+1]$; it is possible to compute the set $J_{dk}$, with $\min(J) = k$ maximizing $V(J_{dk})$ by adding to $J_{dk}$ the value $k$ and the $d-1$ indexes $j > k$ such that $i_j$ is maximum. This can be done in time $O(p \log p)$. Finally, as $V(J_d) = \max_{k \in [1; p-d+1]} V(J_{dk})$, as $o(u, v) = \max_{d \in [0; p]} V(J_d)$ and $p \le n$, the lemma follows. We compute $i(v, u)$ with the same technique. $\square$

**Theorem 1.** (*VALID*) can be solved in time $O(n^4 \log(n))$ in a tree.

*Proof.* Lemma 2 shows that computing $i(u, v)$, $o(u, v)$, $i(v, u)$ and $o(v, u)$ for a single edge $[u, v]$ in $T$ is sufficient to determine whether the instance is valid or not. Note that, due to the recursive formula given in Lemmas 3 and 4, computing those values requires to compute functions $i$ and $o$ for all the edges.

The values $i(u, v)$ and $o(v, u)$ can be computed in constant time if $v$ is a leaf. Using Lemma 5, one can compute step by step the values from the leaves. At each iteration, a new value is evaluated in time $O(n^3 \log(n))$. Thus, all the values are computed in time $O(n^4 \log(n))$. $\square$
4. Conclusion

In this paper, we have proposed a polynomial algorithm to check if there
exists a valid configuration of an electrical network if that network is a tree.
Using this decision problem, it is possible to find the minimum value *s* for
which each switch and each source is used with at most *s* percent of its capacities
which improves the resilience and the reliability of the network. Further work
is needed firstly to improve the algorithm complexity, and secondly to adapt
this algorithm to more complex networks in order to find where is located the
barrier between the general NP-Complete case and the tree case.

References

[1] ATKINS, K., CHEN, J., KUMAR, V. A., AND MARATHE, A. The structure of electrical networks: a graph theory based analysis. *International Journal of Critical Infrastructures* 5, 3 (2009), 265.

[2] BARTH, D., MAUTOR, T., DE MOISSAC, A., WATEL, D., AND WEISSER, M.-A. Optimisation of electrical network configuration: Complexity and algorithms for ring topologies. *Theoretical Computer Science* (2021).

[3] CHRISTIANO, P., KELNER, J. A., MADRY, A., SPIELMAN, D. A., AND TENG, S.-H. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In *Proceedings of the 43rd annual ACM symposium on Theory of computing* (2011), ACM Press, p. 273.

[4] GUO, J., HUG, G., AND TONGUZ, O. K. Intelligent partitioning in distributed optimization of electric power systems. *IEEE Transactions on Smart Grid* 7, 3 (2015), 1249–1258.

[5] LI, J. *Reconfiguration of power networks based on graph-theoretic algorithms*. PhD thesis, Iowa State University, Digital Repository, Ames, 2010.

[6] LI, J., MA, X.-Y., LIU, C.-C., AND SCHNEIDER, K. P. Distribution System Restoration With Microgrids Using Spanning Tree Search. *IEEE Transactions on Power Systems* 29, 6 (2014), 3021–3029.

[7] MOSLEHI, K., AND KUMAR, R. A Reliability Perspective of the Smart Grid. *IEEE Transactions on Smart Grid* 1, 1 (2010), 57–64.

[8] QUIROS-TORTOS, J., AND TERZIJA, V. A graph theory based new approach for power system restoration. In *IEEE Grenoble Conf.* (2013), pp. 1–6.

[9] SHEN, T., LI, Y., XIANG, J., SHEN, T., LI, Y., AND XIANG, J. A Graph-Based Power Flow Method for Balanced Distribution Systems. *Energies* 11, 3 (2018), 511.

[10] TANG, L., YANG, F., AND MA, J. A survey on distribution system feeder reconfiguration: Objectives and solutions. In *IEEE Innovative Smart Grid Technologies - Asia* (2014), IEEE, pp. 62–67.