In 1971 he co-developed with Jack Edmonds the Edmonds–Karp algorithm for solving the maximum flow problem on networks, and in 1972 he published a landmark paper in complexity theory, "Reducibility Among Combinatorial Problems", in which he proved 21 problems to be NP-complete.
În 1971 a dezvoltat împreună cu Jack Edmonds algoritmul Edmonds–Karp de rezolvare a problemei debitului maxim în rețele, iar în 1972 a publicat o lucrare esențială în teoria complexității, "Reducibility Among Combinatorial Problems", în care a demonstrat că 21 de probleme sunt NP-complete.