Abstract
Graph packing and partitioning problems have been studied in many contexts, including from the algorithmic complexity perspective. Consider the packing problem of determining whether a graph contains a spanning tree and a cycle that do not share edges. Bernáth and Király proved that this decision problem is NP-complete and asked if the same result holds when restricting to planar graphs. Similarly, they showed that the packing problem with a spanning tree and a path between two distinguished vertices is NP-complete. They also established the NP-completeness of the partitioning problem of determining whether the edge set of a graph can be partitioned into a spanning tree and a (not-necessarily spanning) tree. We prove that all three problems remain NP-complete even when restricted to planar graphs.
Recommended Citation
Yang, Jed
(2022)
"Some NP-complete Edge Packing and Partitioning Problems in Planar Graphs,"
Communications on Number Theory and Combinatorial Theory: Vol. 3, Article 2.
Available at:
https://research.library.kutztown.edu/contact/vol3/iss1/2