Partition into Perfect Matchings

Input

Graph $G = (V, E)$, positive integer $K \leq |V|$.

Question

Can the vertices of $G$ be partitioned into $k \leq K$ disjoint sets $V_1, V_2, \dots, V_k$ such that, for $1 \leq i \leq k$, the subgraph induced by $V_i$ is a perfect matching (consists entirely of vertices with degree one)?

Classes

• NP-complete

Comments

Remains NP-complete for $K = 2$ and for planar cubic graphs.

Proofs

NP-complete

Transformation from Not-All-Equal 3SAT (Schaefer, 1978).

Reducible from

• Not-All-Equal 3SAT

References

• Schaefer, T. J. (1978). The complexity of satisfiability problems. Proceedings of the Tenth Annual ACM Symposium on Theory of Computing - STOC ’78. https://doi.org/10.1145/800133.804350