文章基本信息

标题：A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem
本地全文：下载
作者：Daniel Lokshtanov ; Mateus de Oliveira Oliveira ; Saket Saurabh 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：115
页码：1-13
DOI：10.4230/LIPIcs.IPEC.2018.25
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In the embedded planar diameter improvement problem (EPDI) we are given a graph G embedded in the plane and a positive integer d. The goal is to determine whether one can add edges to the planar embedding of G in such a way that planarity is preserved and in such a way that the resulting graph has diameter at most d. Using non-constructive techniques derived from Robertson and Seymour's graph minor theory, together with the effectivization by self-reduction technique introduced by Fellows and Langston, one can show that EPDI can be solved in time f(d)* |V(G)|^{O(1)} for some function f(d). The caveat is that this algorithm is not strongly uniform in the sense that the function f(d) is not known to be computable. On the other hand, even the problem of determining whether EPDI can be solved in time f_1(d)* |V(G)|^{f_2(d)} for computable functions f_1 and f_2 has been open for more than two decades [Cohen at. al. Journal of Computer and System Sciences, 2017]. In this work we settle this later problem by showing that EPDI can be solved in time f(d)* |V(G)|^{O(d)} for some computable function f. Our techniques can also be used to show that the embedded k-outerplanar diameter improvement problem (k-EOPDI), a variant of EPDI where the resulting graph is required to be k-outerplanar instead of planar, can be solved in time f(d)* |V(G)|^{O(k)} for some computable function f. This shows that for each fixed k, the problem k-EOPDI is strongly uniformly fixed parameter tractable with respect to the diameter parameter d.
关键词：Embedded Planar Diameter Improvement; Constructive Algorithms; Nooses