Abstract Dominating set is a set of vertices of a graph such that all other vertices have a neighbour in the dominating set. We propose a new order-based randomised local search (RLS o ) algorithm to solve minimum dominating set problem in large graphs. Experimental evaluation is presented for multiple types of problem instances. These instances include unit disk graphs, which represent a model of wireless networks, random scale-free networks, as well as samples from two social networks and real-world graphs studied in network science. Our experiments indicate that RLS o performs better than both a classical greedy approximation algorithm and two metaheuristic algorithms based on ant colony optimisation and local search. The order-based algorithm is able to find small dominating sets for graphs with tens of thousands of vertices. In addition, we propose a multi-start variant of RLS o that is suitable for solving the minimum weight dominating set problem. The application of RLS o in graph mining is also briefly demonstrated.
Regarding the hardness of approximate MDS, approximation ratio @math , where @math is the maximum degree of a vertex, can be achieved by the greedy approximation algorithm. However, Feige showed that the logarithmic approximation is the best possible, unless the class NP contains some slightly superpolynomial algorithms @cite_34 . Recently, it has also been shown that MDS is hard to approximate within a better than logarithmic ratio for certain graphs with power law degree distribution @cite_28 .
@cite_28 @cite_34
2113647243 1965444148 1970421460 2832241482
The best approximation algorithm for Max Cut in graphs of maximum degree 3 uses semidefinite programming, has approximation ratio 0.9326, and its running time is @Q(n^3^.^5logn); but the best combinatorial algorithms have approximation ratio 4 5 only, achieved in O(n^2) time [J.A. Bondy, S.C. Locke, J. Graph Theory 10 (1986) 477-504; E. Halperin, et al, J. Algorithms 53 (2004) 169-185]. Here we present an improved combinatorial approximation, which is a 5 6-approximation algorithm that runs in O(n^2) time, perhaps improvable even to O(n). Our main tool is a new type of vertex decomposition for graphs of maximum degree 3. We present an improved semidefinite programming based approximation algorithm for the MAX CUT problem in graphs of maximum degree at most 3. The approximation ratio of the new algorithm is at least 0.9326. This improves, and also somewhat simplifies, a result of Feige, Karpinski and Langberg. We also observe that results of Hopkins and Staton and of Bondy and Locke yield a simple combinatorial 4 5-approximation algorithm for the problem. Finally, we present a combinatorial 22 27-approximation algorithm for the MAX CUT problem for regular cubic graphs. Feige and Rabinovich, in [Feige and Rabinovich, Rand. Struct. Algorithms 23(1) (2003) 1-22], gave a deterministic O(log4n) approximation for the time it takes a random walk to cover a given graph starting at a given vertex. This approximation algorithm was shown to work for arbitrary reversible Markov chains. We build on the results of [Feige and Rabinovich, Rand. Struct. Algorithms 23(1) (2003) 1-22], and show that the original algorithm gives a O(log2n) approximation as it is, and that it can be modified to give a O(log n(log log n)2) approximation. Moreover, we show that given any c(n)-approximation algorithm for the maximum cover time (maximized over all initial vertices) of a reversible Markov chain, we can give a corresponding algorithm for the general cover time (of a random walk or reversible Markov chain) with approximation ratio O(c(n) log n). We propose a generic transformation that can convert any nonbinary @math maximum distance separable (MDS) code into another @math MDS code over the same field such that: 1) some arbitrarily chosen @math nodes have the optimal repair bandwidth and the optimal rebuilding access; 2) for the remaining @math nodes, the normalized repair bandwidth and the normalized rebuilding access (over the file size) are preserved; and 3) the sub-packetization level is increased only by a factor of @math . Two immediate applications of this generic transformation are then presented. The first application is that we can transform any nonbinary MDS code with the optimal repair bandwidth or the optimal rebuilding access for the systematic nodes only, into a new MDS code which possesses the corresponding repair optimality for all nodes. The second application is that by applying the transformation multiple times, any nonbinary @math scalar MDS code can be converted into an @math MDS code with the optimal repair bandwidth and the optimal rebuilding access for all nodes, or only a subset of nodes, whose sub-packetization level is also optimal.