Optimal solution via ILP

To this end, we modified the existing integer linear programming (ILP) formulation of MCDS in undirected graphs [16] to determine a MCDS for directed graphs.

As before, the set V is the set of vertices and E is the set of edges in the input graph. For a set S⊆V, the set E(S) stands for all the edges connecting two vertices u,v with u,v∈S. The binary valued y_v variables indicate whether node v is selected to belong to the minimum connected dominating set. The binary variables x_e for the edges then yield a tree that contains all selected vertices and no vertex that was not selected. Thus, the selected vertices form a connected component. The first constraint guarantees that the number of edges is one unit less than the number of nodes. This is necessary for them to form a (spanning) tree but is not sufficient. The second constraint guarantees that the selected edges imply a tree. The third constraint guarantees that the set of selected nodes in the solution forms a dominating set of the graph. For dense undirected graphs, this formulation provides a quick solution, but in the case of sparse graphs, finding the optimal solution may take considerable running time [16].

The above IP formulation contains an exponential number of constraints since it has one constraint for each subset S⊆V. Therefore, already for relatively small instances it is impractical to generate all its inequalities. Instead, we used the following approach: we generate the first constraint and all constraints of the third type (i.e., ∑e∈Exe=∑i∈Vyi−1 and yu+∑v∈δ−(u)yv≥1 for each u∈V). Then we compute the optimal IP solution subject to these constraints. Then we check whether the found solution satisfies all constraints of the above IP (even those that we did not add to our formulation). This is the case if and only if the computed set of vertices yields a connected (dominating) set. If this is the case then we found the optimal solution and we stop. Otherwise, we add (violated) constraints of the second type (i.e., ∑e∈E(S)xe≤∑i∈S∖{j}yi for some subset V and some node j) to our formulation and compute the optimal IP solution to this stronger formulation and repeat. If the computed set of vertices has more than one connected component then we add such a constraint for each connected component S and for each vertex j∈S. In order to improve the running time of our procedure, we added some valid inequalities to our initial formulation. These inequalities discard all the solutions that select an edge e={u,v} (i.e., x_e=1) such that not both of its incident vertices were selected (i.e., not both y_u=1 and y_v=1). Formally, for each edge e={u,v} we added the inequalities

Despite adding these valid inequalities, some problem instances were not solved in appropriate time. To overcome this problem, we also considered a heuristic approach. It is known that an approximate MCDS can be found by heuristic approaches in polynomial time [17, 18]. For graphs with low node density and high node degree, the optimal ILP solution can be found at comparable running times as such heuristic solutions [17]. However, the heuristic solution outperforms the ILP for graphs with high node density and low node degree in terms of running time [17]. In this work, all computations were conducted on a single threaded Intel XEON CPU at 2.2 Ghz. We determine the ILP solution using the glpk solver version 4.35 [19]. In cases where the network is very sparse we used the heuristic algorithm (see next section).