Polynomial-time solvability of Directed Plane Strong Connectivity Augmentation

About 1 year old · traced to

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 X⊆V(D)2X\subseteq V(D)^2 with ∣X∣≤k|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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.