Partitionability to two trees is NP-complete

Abstract

We show that P2T - the problem of deciding whether the edge set of a simple graph can be partitioned into two trees or not - is NP-complete.

Cited by in corpus (2)

• Some NP-complete edge packing and partitioning problems in planar graphs
• Rooted-tree Decompositions with Matroid Constraints and the Infinitesimal Rigidity of Frameworks with Boundaries