The NP-Completeness of Some Edge-Partition Problems

Ian Holyer

SIAM Journal on Computing · 1981 · 218 citations · 0 references

Concepts

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.