It was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems".
Acesta a fost una dintre cele 21 de probleme ale lui Richard Karp demonstrate a fi NP-complete în lucrarea sa „Reducibility Among Combinatorial Problems” din 1972.