Eternal Dominating Set Problem - Benchmark Instances, by A. Braga, C. C. de Souza and O. Lee

Citing this page:

    Use the BibTeX entry:

    @Misc{edsp-instances-page,
     author = {Andrei Braga and Cid C. de Souza and Orlando Lee},
     title = {Eternal Dominating Set Problem -- Benchmark Instances},
     year = {2019},
     note = {{\sl www.ic.unicamp.br/$\sim$cid/Problem-instances/Eternal-Dominating-Set}}
    }

Problem Description

Consider the following problem of graph protection. Place guards on some vertices of a graph \(G\). An attack to \(G\) occurs at a vertex, and, to defend an attack at \(v\), the guards must move so that one guard occupies \(v\). In this movement, a guard can stay at the same vertex or go to an adjacent one. All guards are allowed to move during a defense, but multiple guards may not occupy a single vertex. We are asked to determine the minimum number of guards that can eternally defend \(G\), namely, that can eternally perform the task of defending any attack to \(G\).

As simple examples, this minimum number of guards is 2 for the 6-vertex cycle \(C_6\) and 3 for the 5-vertex path \(P_5\) – see the illustrations of Fig. 1 and Fig. 2.

Before the attack

The attack

After defending the attack

Figure 1: Two guards can eternally defend \(C_6\)

Before the first
attack

The first attack

After defending the
first attack

The second attack

The second attack
cannot be defended

Figure 2: Two guards cannot eternally defend \(P_5\) (but three guards can)


The problem above is called the m-eternal dominating set problem and has its origin back in Constantine's approach to defend the Roman Empire, known as Roman domination. Consider guards eternally defending \(G\), that is, eternally performing the task of defending any attack to \(G\). Note that these guards must occupy, initially and after responding to each attack, a dominating set of \(G\) (a set \(S\) of vertices of \(G\) such that every vertex of \(G\) that is not in \(S\) has a neighbor in \(S\)). The problem's name captures the idea of a set of vertices that can be eternally modified yet remaining a dominating set.

The decision version of the m-eternal dominating set problem was proved to be NP-hard [1, Chapter 4]. For additional results on the problem, the reader is pointed to the thorough survey of Klostermeyer and Mynhardt [2].

Input Instances

Our instance set consists of 750 Erdös-Rényi random graphs forced to be connected and divided into 25 groups of 30 graphs. These groups can be described as follows:

    • First 20 groups:
      Each group is characterized by a pair of intervals, one restricting the order of the graphs and the other, their density. The order intervals are [10, 20], [21, 30], [31, 40], and [41, 50], while the density intervals are (0%, 20%], (20%, 40%], (40%, 60%], (60%, 80%], and (80%, 100%].
    • Remaining 5 groups:
      Groups composed of graphs having density at most 20% and order in the intervals [51,60], [61,70], [71,80], [81,90], and [91,100].

The instance files follow the DIMACS format specified here.

Download: instances.zip (620KB).

Results

We implemented two heuristic methods, which employ integer and constraint programming models to compute several bounds on the optimum of the problem. Our code was written in C/C++ using IBM CPLEX 12.5.1, Gurobi 5.6.3, SCIP 3.2.0, and IBM CP 12.5.1 to solve the integer and constraint programming models – see [1, Chapter 4] for more details. All computational tests were conducted on an Intel Quad-Core 3.4GHz machine with 8 GB of RAM.

Our results are given in two CSV files, one for each implemented heuristic method. These files contain a row for each input instance. The columns of the files indicate the name of the instance; the number of vertices, the number of edges, the density, and the minimum size of a dominating set of the input graph; the optimum of the problem; and the upper and lower bound obtained.

Download:

Solution Files

For each input instance, there is a corresponding solution file. A solution is given by a neocolonization setup – for a definition of this concept and an analysis of our results, see [1, Chapter 4]. Each solution file, from the third line onward, contains the following:

    • A line with the weight of the solution;
    • A line with the number of clique parts and the number of non-clique parts of the solution;
    • For each clique part:
      • A line with the number q of vertices of the clique part;
      • A sequence of q lines with the indexes of the vertices of the clique part;
    • For each non-clique part:
      • A line with the number of vertices and the weight of the non-clique part;
      • For each vertex of the non-clique part:
        • A line with the index of the vertex followed by 0 or 1 indicating that the vertex, respectively, belongs or not to the connected dominating set associated with the non-clique part.

Download: solutions.zip (222KB).

Acknowledgments

This work was supported by grants #141964/2013-8, #311373/2015-1, #425340/2016-3, and #306454/2018-1 from Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq, Brazil) and by grant #2015/11937-9 from Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP, Brazil).

References

Address

Andrei Braga, Cid C. de Souza, and Orlando Lee
Universidade Estadual de Campinas
Instituto de Computação
Avenida Albert Einstein, 1251
13083-852 Campinas, SP, Brasil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail: