mardi 31 mars 2026

par BUTEL Nathalie

Amadeus Reinald, chercheur postdoral à l'Université de Varsovie, Pologne, donnera un séminaire au Centre Inria d'Université Côte d'Azur le mardi 31 mars 2026 à 10h30 dans le bâtiment Byron, salle Y106.

 

TITLE :

Plane Strong Connectivity Augmentation 

ABSTRACT : 

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.