[1] That paper brings back memories! Back in 2011, I was chatting with Nick about admixture and graph theory when it dawned on me that he was effectively trying to solve the Steiner tree problem. Knowing that his formulation of the problem was intractable provided a little nudge in the right direction.
It's also worth mentioning that (long) before joining David Reich's lab, Nick Patterson worked at GCHQ where he was famously mentor to Clifford Cocks. The story goes that Nick threw an unsolved asymmetric cryptography problem at Cocks and he came back in the morning having invented RSA.