English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We revisit the minimum dominating set problem on graphs with arboricitybounded by $\alpha$. Bansal and Umboh [BU17] gave an $O(\alpha)$-approximationLP rounding algorithm, which also translates into a near-linear time algorithmusing general-purpose approximation results for explicit mixed packing andcovering or pure covering LPs [KY14, You14, AZO19, Qua10]. Moreover, [BU17]showed that it is NP-hard to achieve an asymptotic improvement for theapproximation factor. On the other hand, the previous two non-LP-basedalgorithms, 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 is an$O(\log^2 n)$-round LP-based $O(\alpha)$-approximation algorithm implied in[KMW06], the best non-LP-based algorithm by Lenzen and Wattenhofer [LW10] is animplementation of their centralized algorithm, providing an$O(\alpha^2)$-approximation within $O(\log n)$ rounds.  We address the questions of whether one can achieve an$O(\alpha)$-approximation algorithm that is not LP-based, either in thecentralized setting or in the distributed setting. We resolve both questions inthe affirmative, and en route achieve algorithms that are faster than thestate-of-the-art LP-based algorithms. More specifically, our contribution istwo-fold: 1. In the centralized setting, we provide a surprisingly simplecombinatorial algorithm that is asymptotically optimal in terms of bothapproximation factor and running time: an $O(\alpha)$-approximation in lineartime. 2. Based on our centralized algorithm, we design a distributedcombinatorial $O(\alpha)$-approximation algorithm in the CONGEST model thatruns in $O(\alpha\log n )$ rounds with high probability.

Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial