Complexity of the Failure Indicator Allocation Problem

Faults are inherent in power distribution systems, and fault indicators (FIs) play a crucial role in self-healing smart distribution systems, aiding in fault localization. However, the effectiveness of these devices depends on their quantity and proper placement throughout the distribution system, giving rise to the Fault Indicator Allocation Problem (PAIF).

Previous works have addressed this problem through metaheuristics, genetic algorithms and quadratic programming formulations, leaving open the question of whether an exact polynomial-time algorithm exists. In this paper, we answer this question negatively, except if P = NP: we present an NP-hardness proof for the problem, obtained through a reduction from the SUBSET-SUM problem.