Plane Strong Connectivity Augmentation

Prelegent(ci)

Amadeus Reinald

Język referatu

angielski

Termin

22 maja 2026 14:15

Pokój

p. 5060

Seminarium

Seminarium "Algorytmika"

---

Suppose you are given a non-crossing network of one-way roads between cities, but where some cities are not reachable from others. The problem we address in this talk is the following: "How to construct a set of new one-way roads ensuring that every city is reachable from every other, without introducing crossings or two-way roads?"
This can be formalized as the strong connectivity augmentation problem 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 budgeted version, Plane Strong Connectivity Augmentation (PSCA) asks for X to be of size at most k. Our main result is a fixed-parameter tractable algorithm for PSCA, running in time 2^O(k) n^O(1). The cornerstone of our procedure is a structural result, allowing for face-wise branching and a Monte-Carlo reduction to the polynomial Minimum Dijoin problem. To the best of our knowledge, this is the first FPT algorithm for a (hard) connectivity augmentation problem constrained by planarity.

---