EPM-Problem, Problemstellung innerhalb der Graphentheorie.

Das exact-perfect-matching-Problem fragt danach, ob es in einem GraphenG zu einer vorgegebenen Teilmenge K ⊆ K(G) und einer gegebenen natürlichen Zahl p ein perfektes Matching M mit |M ∩ K| = p gibt.

Es ist bislang nicht bekannt, ob dieses Problem polynomial lösbar ist. F. Barahona und W.R. Pulleyblank konnten 1985 nachweisen, daß dies jedenfalls für planare Graphen gilt.