The $st$-Planar Edge Completion Problem is Fixed-Parameter Tractable
Lists
Only you see this
Abstract
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'$.
BibTeX
@inproceedings{khazaliya2023st,
author = {Liana Khazaliya and Philipp Kindermann and Giuseppe Liotta and Fabrizio Montecchiani and Kirill Simonov},
title = {{The $st$-Planar Edge Completion Problem is Fixed-Parameter Tractable}},
booktitle = {ISAAC},
year = {2023},
url = {https://openreview.net/forum?id=PvQxJzBsZ0},
}Loading related content...