The $st$-Planar Edge Completion Problem is Fixed-Parameter Tractable
Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta, Fabrizio Montecchiani, Kirill Simonov · arXiv (Cornell University) · 2023
The problem of deciding whether a biconnected planar digraph $G=(V,E)$ can be augmented to become an $st$-planar graph by adding a set of oriented edges $E' \subseteq V \times V$ is known to be NP-complete. We show that the problem is fixed-parameter tractable when parameterized by the size of the set $E'$.