Some NP-complete edge packing and partitioning problems in planar graphs

Jed Yang

Published 2014-09-08Version 1

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\'ath and Kir\'aly 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.