Enumerating Minimal Power Dominating Sets

Abstract

Power Dominating Set Enumeration This repository contains the code and computational experiments accompanying the paper "Implicit Hitting Set Enumerating for Power Dominating Sets". A permanent record of the repository can be found at Zenodo. Background A power dominating set of a graph is a vertex set that marks the entire graph through a sequence of propagation steps. Initially, only the selected vertices and their neighbors are marked. Then, if a marked vertex has only one unmarked neighbor, that neighbor becomes marked as well. This process is repeated exhaustively. A hitting set or transversal of a hypergraph is a vertex set that intersects all hyperedges. Minimal power dominating sets can be characterized as hitting sets of the so-called fort neighborhoods of a graph, which are vertex sets that cannot be completely marked without selecting a vertex from the set. Method We use MMCS as a hitting set enumeration algorithm with adaptations for implicit hitting set enumeration. In the implicit setting, the full hypergraph is initially unknown and only incrementally revealed by an oracle that checks whether a given set is a hitting set. We adapt MMCS to this setting by invoking the oracle each time MMCS finds a minimal hitting set of the currently known hypergraph. If the oracle confirms that the set is a hitting set of the full hypergraph, we output it. Otherwise, we add the returned edges to the partial hyeprgraph and continue the enumeration. We use characterization of power dominating sets via fort neighborhoods to reduce the enumeration of power dominating sets to the enumeration of hitting sets. Whenever the enumeration finds a candidate power dominating set, we verify whether it is indeed a power dominating set and otherwise compute a fort neighborhood that is not hit by the candidate solution. Data We exported a number of standard power grid instances from the pandapower Python library. The instances can be found as adjacency lists in the experiments/instances directory. For each graph, we consider two enumeration variants: one where we enumerate all minimal power dominating sets and one where we require the vertices in the power dominating sets to have degree at least two. Repository Structure The repository contains the source code for the enumeration algorithm and the experiment instances. The source code is split into two parts. The general implementation of implicit hitting set MMCS is located in crates/hs-enum. The code for power dominating set enumeration and the experiment source code are located in src/ The experiment instances, run script and instances can be found in the experiments/ directory. You can find the original results used in the paper in the experiments/results directory. Experiments We run four separate experiment stages. This sequence is started by the runner script in experiments/run.sh. Experiment outputs are stored in the results/ directory. Enumerate all minimal power dominating sets of the instances starting with an empty partial hypergraph and collect the resulting (partial) fort hypergraphs. This is the main experiment Results are stored in results.csv, fort hypergraphs are stored in fort-cache/. Enumerate the minimal hitting sets of the (partial) fort hypergraph obtained in the first stage using vanilla MMCS. This is equivalent to enumerating the power dominating sets if and only if the instance terminates. Results are stored in results-mmcs.csv Enumerate all minimal power dominating sets starting with the previous partial fort hypergraph. Enumerate all minimal power dominating sets starting with an empty partial hypergraph and collect additional statistics during runtime. Separate run to avoid timing interference. Results are stored in results-series.csv as well as per-instance files in the series/ dubdirectory. Experiments within each stage can be run in parallel. The second and third stage depend on the partial hypergraph obtained in the first stage. We also run an evaluation pass to generate the figures and tables for the paper from the raw results. These are placed in the evaluation/ directory. The figures visualize the development of the enumeration tree over time. They are available as raw csv files in figures and as a rendered version in figures-extra. The tables directory contains the tables from the paper. Additional tables not used in the paper are available in tables-extra. Running the Experiments For convenience, we provide a Containerfile to run the experiments and evaluation. The container has two volumes /experiment/results and /experiment/evaluation for raw results and figures and tables, respectively, by default mounted to results and evaluation in the working directory. Use the provided compose file to build and run the container: docker compose up --build Alternatively, use docker or podman directly: docker build -t pds-enum . docker run -v ./results:/experiment/results -v ./evaluation:/experiment/evaluation -it pds-enum You can modify the timeout by setting the TIMEOUT build argument or environment variable. By default, all available threads are used. You can limit the number by passing the NUM_THREADS environment variable to the container.