Polynomial-time solvability of Directed Plane Strong Connectivity Augmentation

From papers

Let DD be a connected plane digraph and let kk be an integer. The Directed Plane Strong Connectivity Augmentation problem asks whether there is a set XV(D)2X\subseteq V(D)^2 with Xk|X|\leq k such that D+XD+X is strongly connected, directed, and plane for the same embedding of DD. Directed-PSCA conjecture. The Directed Plane Strong Connectivity Augmentation problem is polynomial-time solvable. The paper establishes fixed-parameter tractability for this problem, while polynomial-time solvability remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Stéphane Bessy, Daniel Gonçalves, Amadeus Reinald and Dimitrios M. Thilikos, “Plane Strong Connectivity Augmentation”, arXiv:2512.17904 (2025).

Solutions 0

No solutions have been posted yet.