SIAM Journal on Computing · 1981 · 218 citations · 0 references
ComputingComputer ScienceMathematicsAlgorithmsDiscrete MathematicsTheory Of ComputationData PartitioningDirected Acyclic GraphsGraph AlgorithmsGraph TheoryComputational Complexity Of Graph AlgorithmsGraph DecompositionsGraph PartitioningPartitioning ProblemsSubgraph Isomorphism
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.