Variants of plane diameter completion

DOI10.4230/LIPICS.IPEC.2015.30MaRDI QIDQ5363757zbMATH OpenOpenAlexFDO

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

Publication date 29 September 2017

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

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)

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.

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

Cited in

(5)

• Planar disjoint-paths completion
• A survey of parameterized algorithms and the complexity of edge modification
• 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)