We revisit the minimum dominating set problem on graphs with arboricity bounded by \alpha. In the (standard) centralized setting, Bansal and Umboh [BU17] gave an O(\alpha)-approximation LP rounding algorithm   . Moreover, [BU17] showed that it is NP-hard to achieve an asymptotic improvement  . On the other hand, the previous two non-LP-based algorithms, by Lenzen and Wattenhofer [LW10] , and Jones et al. [JLR+13], achieve an approximation factor of O(\alpha^2) in linear time. There is a similar situation in the distributed setting: While there are \text{poly}%DIFDELCMD < \logn%%% -round LP-based O(\alpha)-approximation algorithms [KMW06, DKM19], the best non-LP-based algorithm by Lenzen and Wattenhofer [LW10] is an implementation of their centralized algorithm, providing an O(\alpha^2)-approximation within O(\log n) rounds with high probability. We address the question of whether one can achieve a simple, elementary O(\alpha)-approximation algorithm  not based on any LP-based methods, either in the centralized setting or in the distributed setting. We resolve these questions in the affirmative . More specifically, our contribution is two-fold : 1. In the centralized setting, we provide a surprisingly simple combinatorial algorithm that is asymptotically optimal in terms of both approximation factor and running time : an O(\alpha)-approximation in linear time.  2. Based on our centralized algorithm, we design a distributed combinatorial O(\alpha)-approximation algorithm in the \mathsf{CONGEST} model that runs in O(\alpha\log n) rounds with high probability . Our round complexity outperforms the best LP-based distributed algorithm for a wide range of parameters .
We revisit the minimum dominating set problem on graphs with arboricity \alpha. In the (standard) centralized setting, Bansal and Umboh [BU17] gave an O(\alpha)-approximation LP rounding algorithm , which translates into a near-linear time algorithm using general-purpose approximation results for explicit covering LPs KY14, You14, AZO19, Qua20 . Moreover, [BU17] showed that it is NP-hard to achieve an asymptotic improvement for the approximation factor . On the other hand, the previous two non-LP-based algorithms, by Lenzen and Wattenhofer [LW10] and Jones et al. [JLR+13], achieve an approximation factor of O(\alpha^2) in linear time. There is a similar situation in the distributed setting: While there }%DIFDELCMD < \logn%%% is an O(\log^2 n)-round LP-based O(\alpha)-approximation algorithms [KMW06, DKM19], the best non-LP-based algorithm by Lenzen and Wattenhofer [LW10] is an implementation of their centralized algorithm, providing an O(\alpha^2)-approximation within O(\log n) rounds with high probability. We address the questions of whether one can achieve an O(\alpha)-approximation algorithm that is elementary, i.e., not based on any LP-based methods, either in the centralized setting or in the distributed setting. We resolve both questions in the affirmative , and en route achieve algorithms that are faster than the state-of-the-art LP-based algorithms : 1. In the centralized setting, we provide a surprisingly simple combinatorial algorithm that is asymptotically optimal in terms of both approximation factor and runtime : an O(\alpha)-approximation in linear time. The previous best O(\alpha)-approximation algorithms are LP-based and have super-linear running time. 2. Based on our centralized algorithm, we design a distributed combinatorial O(\alpha)-approximation algorithm in the \mathsf{CONGEST} model that runs in O(\alpha\log n) rounds with high probability .
D
bounded by
A
, which translates into a near-linear time algorithm using general-purpose approximation results for explicit covering LPs
A
KY14, You14, AZO19, Qua20
A
for the approximation factor
D
,
D
are \text{poly
R
-round
is an O(\log^2 n)-round
R
question
questions
R
a simple, elementary
an
A
that is elementary, i.e.,
R
these
both
R
. More specifically, our contribution is two-fold
, and en route achieve algorithms that are faster than the state-of-the-art LP-based algorithms
R
running time
runtime
A
The previous best O(\alpha)-approximation algorithms are LP-based and have super-linear running time.
D
. Our round complexity outperforms the best LP-based distributed algorithm for a wide range of parameters