اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA local constant factor approximation for the minimum dominating set problem on bounded genus graphs
86
0
0.0
(
0
)
نشر من قبل
Saeed Akhoondian Amiri
تاريخ النشر
2016
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The Minimum Dominating Set (MDS) problem is not only one of the most fundamental problems in distributed computing, it is also one of the most challenging ones. While it is well-known that minimum dominating sets cannot be approximated locally on general graphs, over the last years, several breakthroughs have been made on computing local approximations on sparse graphs. This paper presents a deterministic and local constant factor approximation for minimum dominating sets on bounded genus graphs, a very large family of sparse graphs. Our main technical contribution is a new analysis of a slightly modified, first-order definable variant of an existing algorithm by Lenzen et al. Interestingly, unlike existing proofs for planar graphs, our analysis does not rely on any topological arguments. We believe that our techniques can be useful for the study of local problems on sparse graphs beyond the scope of this paper.
قيم البحث
اقرأ أيضاً
We show that there is no deterministic local algorithm (constant-time distributed graph algorithm) that finds a $(7-epsilon)$-approximation of a minimum dominating set on planar graphs, for any positive constant $epsilon$. In prior work, the best low
er bound on the approximation ratio has been $5-epsilon$; there is also an upper bound of $52$.
We show that there is a deterministic local algorithm (constant-time distributed graph algorithm) that finds a 5-approximation of a minimum dominating set on outerplanar graphs. We show there is no such algorithm that finds a $(5-varepsilon)$-approxi
mation, for any $varepsilon>0$. Our algorithm only requires knowledge of the degree of a vertex and of its neighbors, so that large messages and unique identifiers are not needed.
Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by us
ing this compiler, every linear-time algorithm for deciding the membership to some fixed graph class can be translated into a $mathsf{dMAM}(O(log n))$ protocol for this class, that is, a distributed interactive protocol with $O(log n)$-bit proof size in $n$-node graphs, and three interactions between the (centralizer) computationally-unbounded but non-trustable prover Merlin, and the (decentralized) randomized computationally-limited verifier Arthur. As a corollary, there is a $mathsf{dMAM}(O(log n))$ protocol for the class of planar graphs, as well as for the class of graphs with bounded genus. We show that there exists a distributed interactive protocol for the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of $O(log n)$ bits. This result also holds for the class of graphs with bounded demi-genus, that is, graphs that can be embedded on a non-orientable surface of bounded genus. The interactive protocols described in this paper are actually proof-labeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schemes do not require any randomization from the verifier, and the proofs may often be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent proof-labeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded demigenus.
We give a constant factor approximation algorithm for the asymmetric traveling salesman problem when the support graph of the solution of the Held-Karp linear programming relaxation has bounded orientable genus.
We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
