Variants of plane diameter completion

DOI10.4230/LIPICS.IPEC.2015.30zbMATH Open1378.68078arXiv1509.00757OpenAlexW2962937409MaRDI QIDQ5363757FDOQ5363757

Authors: Petr A. Golovach, Clément Requilé, Dimitrios M. Thilikos 

Publication date: 29 September 2017

Abstract: The {sc Plane Diameter Completion} problem asks, given a plane graph $G$ and a positive integer $d$, if it is a spanning subgraph of a plane graph $H$ that has diameter at most $d$. We examine two variants of this problem where the input comes with another parameter $k$. In the first variant, called BPDC, $k$ upper bounds the total number of edges to be added and in the second, called BFPDC, $k$ upper bounds the number of additional edges per face. We prove that both problems are {sf NP}-complete, the first even for 3-connected graphs of face-degree at most 4 and the second even when $k=1$ on 3-connected graphs of face-degree at most 5. In this paper we give parameterized algorithms for both problems that run in $O(n^3)+2^{2^{O((kd{)}^{2}logd)}}cdotn$ steps.

Full work available at URL: https://arxiv.org/abs/1509.00757

Recommendations

• Planar disjoint-paths completion
• Planar disjoint-paths completion
• FPT algorithms for plane completion problems
• scientific article; zbMATH DE number 1156599
• A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem

zbMATH Keywords

dynamic programmingplanar graphsparameterized algorithmsgraph modification problemsbranchwidth

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cited In (5)

• A survey of parameterized algorithms and the complexity of edge modification
• Planar disjoint-paths completion
• FPT algorithms for plane completion problems
• Planar disjoint-paths completion
• A strongly-uniform slicewise polynomial-time algorithm for the embedded planar diameter improvement problem

This page was built for publication: Variants of plane diameter completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363757)