2015/10/24 by Yinglei Song, Song, Yinglei
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1510.07188
openalex publication_date 2015/10/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study the \sc Dominating Set problem in random graphs. In a random graph, each pair of vertices are joined by an edge with a probability of p, where p is a positive constant less than 1. We show that, given a random graph in n vertices, a minimum dominating set in the graph can be computed in expected 2^O(log22n) time. For the parameterized dominating set problem, we show that it cannot be solved in expected O(f(k)nc) time unless the minimum dominating set problem can be approximated within a ratio of o(log2n) in expected polynomial time, where f(k) is a function of the parameter k and c is a constant independent of n and k. In addition, we show that the parameterized dominating set problem can be solved in expected O(f(k)nc) time when the probability p depends on n and equals to (1)/(g(n)), where g(n)< n is a monotonously increasing function of n and its value approaches infinity when n approaches infinity.