Partitionability to two trees is NP-complete

2010/02/20 by Dömötör Pálvölgyi, Palvolgyi, Domotor · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1002.3937

openalex publication_date 2010/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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

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

Related

• Decomposition into two trees with orientation constraints
• Some NP-complete edge packing and partitioning problems in planar graphs
• Yet Another Graph Partitioning Problem is NP-Hard
• The Satisfactory Partition Problem
• NP-hardness results for partitioning graphs into disjoint cliques and a\n triangle-free subgraph