2026-09-08T01:21:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26416 2026-09-05T19:42:53Z ddc:004 open_access

Plane Strong Connectivity Augmentation Bessy, Stéphane Gonçalves, Daniel Reinald, Amadeus Thilikos, Dimitrios M. Connectivity augmentation Directed graphs Parameterized complexity We investigate the problem of strong connectivity augmentation within plane oriented graphs. We show that deciding whether a plane oriented graph D can be augmented with (any number of) arcs X such that D+X is strongly connected, but still plane and oriented, is NP-hard. The hardness also holds for the planar variant. This question becomes trivial within plane (or planar) digraphs, like most connectivity augmentation problems without a budget constraint. The budgeted variant, Plane Strong Connectivity Augmentation (PSCA) considers a plane oriented graph D along with some integer k, and asks for an X of size at most k ensuring that D+X is strongly connected, while remaining plane and oriented. Our main result is a fixed-parameter tractable algorithm for PSCA, running in time 2^O(k) n² log n. The cornerstone of our procedure is a structural result showing that, for any fixed k, each face admits a bounded number of partial solutions "dominating" all others. Then, our algorithm for PSCA combines face-wise branching with a randomized reduction to the polynomial Minimum Dijoin problem, yielding a Monte-Carlo FPT algorithm, which we derandomize. To the best of our knowledge, this is the first FPT algorithm for a (hard) connectivity augmentation problem constrained by planarity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stéphane Bessy and Daniel Gonçalves and Amadeus Reinald and Dimitrios M. Thilikos 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.27 urn:nbn:de:0030-drops-264163 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.27 eng https://creativecommons.org/licenses/by/4.0/legalcode