License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2018.25
URN: urn:nbn:de:0030-drops-102265
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10226/
Lokshtanov, Daniel ;
de Oliveira Oliveira, Mateus ;
Saurabh, Saket
A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem
Abstract
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.
BibTeX - Entry
@InProceedings{lokshtanov_et_al:LIPIcs:2019:10226,
author = {Daniel Lokshtanov and Mateus de Oliveira Oliveira and Saket Saurabh},
title = {{A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem}},
booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
pages = {25:1--25:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-084-2},
ISSN = {1868-8969},
year = {2019},
volume = {115},
editor = {Christophe Paul and Michal Pilipczuk},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10226},
URN = {urn:nbn:de:0030-drops-102265},
doi = {10.4230/LIPIcs.IPEC.2018.25},
annote = {Keywords: Embedded Planar Diameter Improvement, Constructive Algorithms, Nooses}
}
|
Keywords: |
|
Embedded Planar Diameter Improvement, Constructive Algorithms, Nooses |
|
Collection: |
|
13th International Symposium on Parameterized and Exact Computation (IPEC 2018) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
05.02.2019 |
