A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem

Authors Daniel Lokshtanov, Mateus de Oliveira Oliveira, Saket Saurabh



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.25.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Daniel Lokshtanov
  • Department of Informatics - University of Bergen, Bergen, Norway
Mateus de Oliveira Oliveira
  • Department of Informatics - University of Bergen, Bergen, Norway
Saket Saurabh
  • Department of Informatics - University of Bergen, Bergen, Norway

Cite AsGet BibTex

Daniel Lokshtanov, Mateus de Oliveira Oliveira, and Saket Saurabh. A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.IPEC.2018.25

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Embedded Planar Diameter Improvement
  • Constructive Algorithms
  • Nooses

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Isolde Adler, Martin Grohe, and Stephan Kreutzer. Computing excluded minors. In Proc. of SODA 2008, pages 641-650. SIAM, 2008. Google Scholar
  2. Vincent Bouchitté, Frédéric Mazoit, and Ioan Todinca. Chordal embeddings of planar graphs. Discrete Mathematics, 273(1):85-102, 2003. Google Scholar
  3. Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM Journal on Computing, 31(1):212-232, 2001. Google Scholar
  4. Nathann Cohen, Daniel Gonçalves, Eun Jung Kim, Christophe Paul, Ignasi Sau, Dimitrios M Thilikos, and Mathias Weller. A polynomial-time algorithm for outerplanar diameter improvement. Journal of Computer and System Sciences, 2017. Google Scholar
  5. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  6. Mateus de Oliveira Oliveira. On Supergraphs satisfying CMSO properties. In Proc. of the 26th Conference on Computer Science Logic (CSL 2017). To appear., volume 82 of LIPIcs, 2017. Google Scholar
  7. Frederic Dorn, Eelko Penninkx, Hans L Bodlaender, and Fedor V Fomin. Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions. Algorithmica, 58(3):790-810, 2010. Google Scholar
  8. Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. Google Scholar
  9. Michael R. Fellows and Rodney G. Downey. Parameterized Computational Feasibility. Feasible Mathematics II, 13:219-244, 1995. Google Scholar
  10. Michael R Fellows and Michael A Langston. On search decision and the efficiency of polynomial-time algorithms. In Proc. of STOC 1989, pages 501-512. ACM, 1989. Google Scholar
  11. Fedor V Fomin and Dimitrios M Thilikos. A simple and fast approach for solving problems on planar graphs. In STACS, volume 2996, pages 56-67. Springer, 2004. Google Scholar
  12. Fedor V Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM Journal on Computing, 44(1):54-87, 2015. Google Scholar
  13. Neil Robertson and Paul D Seymour. Graph minors. XI. Circuits on a surface. Journal of Combinatorial Theory, Series B, 60(1):72-106, 1994. Google Scholar
  14. Neil Robertson and Paul D Seymour. Graph minors. XIII. The disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65-110, 1995. Google Scholar
  15. Neil Robertson and Paul D Seymour. Graph minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325-357, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail