Implicit method finds minimal sets observing entire power grids quickly
Implicit Hitting Set Enumeration for Power Dominating Sets
Data Structures and Algorithms
Summary
Finding minimal groups of points that can observe an entire network is important but hard when networks are huge or partly unknown. The authors worked on a new way to list all smallest such groups for power grids without needing full upfront knowledge of the network. They adapted an existing approach that treats the problem like asking questions to an oracle, which either confirms a candidate set works or points out missing information. Their method can efficiently find all these minimal groups and was tested on real power grid data, showing good performance.
What this means in practice
- •For power grid operators: Identify minimal monitoring sets for power grids without needing full network details in advance.
- •For network security teams: Determine minimal observation points in large or partially unknown network structures for efficient monitoring.
Authors
Thomas Bläsius, Max Göttlicher, Martin Schirneck
Abstract
The Transversal Hypergraph problem asks to enumerate (list) all inclusion-minimal hitting sets of a hypergraph. It usually assumes that the input is completely known and does not change over the course of the enumeration. In many applications, the underlying hypergraph is too large or expensive to compute. This motivated the implicit hitting set framework [Chandrasekaran, Karp, Moreno-Centeno, and Vempala, SODA 2011] for the corresponding optimization problem of finding a smallest hitting set. Access to the input is given by an oracle that either confirms that a query set $S$ is a hitting set, or reveals a new hyperedge disjoint from $S$. We adapt this framework to enumeration. We show for a general class of algorithms that they are able to find all hitting sets when given access to such an oracle, even if the hypergraph is a priori unknown. We also prove that the current fastest Transversal Hypergraph algorithm, Minimal-to-Maximal Conversion Search by Murakami and Uno [DAM 2014], belongs to this class. We then engineer an implicit hitting set algorithm for the enumeration of minimal power dominating sets in graphs. A power dominating set is a selection of vertices that "observe" all vertices by exhaustively applying two rules: if a vertex is dominated by the selection, it becomes observed; and if an observed vertex has a unique unobserved neighbor, this neighbor becomes observed as well. An experimental evaluation on a collection of power grid instances from the literature shows that our approach achieves very high throughput rates.