The NP-Completeness of Some Edge-Partition Problems

1981/11/01 by Ian Holyer · 5 citations
Computer Science · Engineering · #Advanced Graph Theory Research #graph theory and CDMA systems #Interconnection Networks and Systems

paper · doi:10.1137/0210054

openalex publication_date 1981/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

We show that for each fixed n \geqq 3 it is NP-complete to determine whether an arbitrary graph can be edge-partitioned into subgraphs isomorphic to the complete graph K_n . The NP-completeness of a number of other edge-partition problems follows immediately.

Cited by

• The complexity of completing partial Latin squares
• Complexity of Token Swapping and its Variants
• Minimum Weakly Fundamental Cycle Bases Are Hard To Find
• Graph factors and factorization: 1985–2003: A survey
• P versus NP problem [wikipedia]