Near-optimal distributed dominating set in bounded arboricity graphs

Area of Science:

• Distributed Algorithms
• Graph Theory
• Approximation Algorithms

Background:

• The minimum weighted dominating set problem is a fundamental problem in graph theory with applications in network design and facility location.
• Existing distributed algorithms for this problem have limitations in terms of approximation ratios or round complexity, especially for weighted graphs.

Purpose of the Study:

• To design a simple deterministic distributed algorithm for approximating the minimum weighted dominating set.
• To analyze the round complexity and approximation factor of the proposed algorithm.
• To establish lower bounds on the round complexity for this problem.

Main Methods:

• A deterministic distributed algorithm with a specific round complexity is presented.
• The algorithm's performance is analyzed for graphs with bounded arboricity.
• A reduction from the KMW lower bound for distributed vertex cover approximation is used to establish a lower bound for the dominating set problem.

Main Results:

• A deterministic O(log n) round distributed algorithm achieving an O(log Δ) approximation for minimum weighted dominating set on graphs with arboricity at most O(log n) is developed.
• A nearly optimal lower bound on the round complexity is proven, even for the unweighted case.
• The algorithm improves upon existing randomized and deterministic approximation algorithms in terms of round complexity and approximation factor.

Conclusions:

• The proposed deterministic algorithm offers a significant improvement in round complexity for approximating the minimum weighted dominating set.
• The established lower bound highlights the near-optimality of the algorithm's round complexity.
• Further research includes a randomized algorithm with an improved approximation factor, demonstrating tightness in the first order due to NP-hardness.