Randomized greedy algorithms for finding smallk-dominating sets of regular graphs

DOI10.1002/RSA.20082MaRDI QIDQ5704842zbMATH OpenOpenAlexFDO

Authors

Publication date 15 November 2005

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20082

differential equations method random regular graph

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80)

Review text

A \(k\)-dominating set in a graph \(G\) is a set \({\mathcal D}\) of vertices of \(G\) such that every vertex of \(G\) is either in \({\mathcal D}\) or at distance at most \(k\) from a vertex in \({\mathcal D}\). (For \(k=1\) this is the usual notion of a dominating set.) One would like to find \(k\)-dominating sets of small cardinality. In the paper under review, the authors investigate \(k\)-dominating sets of small cardinality in random \(d\)-regular graphs on the \(n\) labelled vertices \(\{1,2,\ldots n\}\), with all possible choices of such a graph being equally likely. (Of course \(nd\) is even.) The method used is to analyze the performance of a randomized greedy algorithm for constructing these \(k\)-dominating sets, the analysis of the algorithm being conducted using the differential equations method. More precisely: The authors consider \(k\)-dominating sets in random \(d\)-regular graphs, where \(k\geq 2\) and \(d\geq 3\) are fixed and \(n\rightarrow\infty\). We say that a property \(\wp\) holds a.a.s. if the limit, as \(n\rightarrow\infty\), of the probability that a random \(d\)-regular graph on \(n\) vertices has \(\wp\), is 1. Since any vertex of a \(d\)-regular graph \(k\)-dominates itself and at most \(d((d-1)^{k}-1)/(d-2)\) other vertices (just consider how many vertices can be within distance \(k\) of it) one can easily see that a minimum \(k\)-dominating set has order at least \[ | {\mathcal D} | \geq \frac{(d-2)n}{d(d-1)^{k}-2}. \] In the other direction, since a \(d\)-regular random graph for \(d\geq 3\) is a.a.s. Hamiltonian, we can, just by taking the vertices at distance \(2k+1\) from each other on such a cycle, get the upper bound \[ | {\mathcal D}|\leq \frac{n}{2k+1}. \] The main result of the paper under review is an improved upper bound: for a random \(d\)-regular graph on \(n\) vertices, with \(d\geq 3\), there are constants \({\mathcal C}_{u}^{k}(d)\) such that the size of a minimum \(k\)-dominating set is a.a.s. less than \({\mathcal C}_{u}^{k}(d)n\). Some explicit values of the upper bound constants \({\mathcal C}_{u}^{k}(d)\), accurate to five decimal places, are given, for \(2\leq k\leq 4\) and \(3\leq d\leq 10\): in all cases there is still a gap between these upper bounds and the lower bound mentioned in the second paragraph, but the improvement on the crude upper bound is substantial. The first algorithm considered is just to repeatedly choose a vertex of current maximum degree, removing it from the graph with the vertices it dominates and all edges incident with it. This algorithm, called MAX, tends to produce many isolated vertices towards the end of a run, so is not terribly good. The second algorithm MIN chooses instead vertices of current maximum degree amongst the neighbours of vertices of current minimum degree: this beats MAX for small \(d\) and \(k\), though not for large ones. Finally, the hybrid algorithm ML chooses at random a vertex \(u_{1}\) of current minimum positive degree: it selects at random a neighbour \(u_{2}\) of current maximum degree amongst the neighbours of \(u_{1}\) and deletes all edges incident with \(u_{1}\), then \(u_{3}\) at random amongst the vertices of current maximum degree among the neighbours of \(u_{2}\), and continues this up to \(k+1\) times: when \(u_{j}\) has been selected, all edges incident with vertices at distance at most \(j-2\) from \(u_{j-1}\) are deleted. This is the best algorithm and the one whose analysis leads to the new upper bounds in the previous paragraph. As usual, the random \(d\)-regular graphs are generated by the pairing method (with the pairs selected sequentially). The quantities to be analyzed are the \(Y_{i}\), the numbers of vertices of current degree \(i\). One can show that these random variables are close to their means, as is required for the differential equations method, and the means themselves can be estimated well enough by exploiting the fact that the subgraph induced by a vertex and all points at most constant distance from it is a.a.s a tree: this depends on the ubiquitous fact that random regular graphs have few short cycles. The authors refer to their paper [\textit{W. Duckworth} and \textit{B. Mans}, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science, (J. D. P. Rolim and S. P. Vadhan, eds.), Lect. Notes Comput. Sci. 2483, 126--138 (2002; Zbl 1028.68566)] for some details of the numerical calculations.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Randomized greedy algorithms for finding smallk-dominating sets of regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5704842)