اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA complexity dichotomy for the dominating set problem
182
0
0.0
(
0
)
نشر من قبل
Dmitriy Malyshev Sergeevich
تاريخ النشر
2015
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
تأليف
D.S. Malyshev
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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.
Let $G$ be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of $k$ colors. Suppose that we are given two list edge-colorings $f_0$ and $f_r$ of $G$, and asked whether the
re exists a sequence of list edge-colorings of $G$ between $f_0$ and $f_r$ such that each list edge-coloring can be obtained from the previous one by changing a color assignment of exactly one edge. This problem is known to be PSPACE-complete for every integer $k ge 6$ and planar graphs of maximum degree three, but any complexity hardness was unknown for the non-list variant. In this paper, we first improve the known result by proving that, for every integer $k ge 4$, the problem remains PSPACE-complete even if an input graph is planar, bounded bandwidth, and of maximum degree three. We then give the first complexity hardness result for the non-list variant: for every integer $k ge 5$, we prove that the non-list variant is PSPACE-complete even if an input graph is planar, of bandwidth linear in $k$, and of maximum degree $k$.
The extension complexity $mathsf{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that affinely projects to $P$. Let $G$ be a bipartite graph with $n$ vertices, $m$ edges, and no isolated vertices. Let $mathsf{STAB}(G)$ be the
convex hull of the stable sets of $G$. It is easy to see that $n leqslant mathsf{xc} (mathsf{STAB}(G)) leqslant n+m$. We improve both of these bounds. For the upper bound, we show that $mathsf{xc} (mathsf{STAB}(G))$ is $O(frac{n^2}{log n})$, which is an improvement when $G$ has quadratically many edges. For the lower bound, we prove that $mathsf{xc} (mathsf{STAB}(G))$ is $Omega(n log n)$ when $G$ is the incidence graph of a finite projective plane. We also provide examples of $3$-regular bipartite graphs $G$ such that the edge vs stable set matrix of $G$ has a fooling set of size $|E(G)|$.
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 gen
eral 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.
This paper is devoted to the online dominating set problem and its variants. We believe the paper represents the first systematic study of the effect of two limitations of online algorithms: making irrevocable decisions while not knowing the future,
and being incremental, i.e., having to maintain solutions to all prefixes of the input. This is quantified through competitive analyses of online algorithms against two optimal algorithms, both knowing the entire input, but only one having to be incremental. We also consider the competitive ratio of the weaker of the two optimal algorithms against the other. We consider important graph classes, distinguishing between connected and not necessarily connected graphs. For the classic graph classes of trees, bipartite, planar, and general graphs, we obtain tight results in almost all cases. We also derive upper and lower bounds for the class of bounded-degree graphs. From these analyses, we get detailed information regarding the significance of the necessary requirement that online algorithms be incremental. In some cases, having to be incremental fully accounts for the online algorithms disadvantage.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
