Thanks for the answer below.
Yes they need the entire tree. I have what I know of my family tree online at MyHeritage. I also have my DNA uploaded at MyHeritage. Other members of MyHeritage have done the same thing. When MyHeritage finds a partial match on DNA, they start with each person in the match and move backwards up each tree looking for a common ancestor. In addition, they use information from other peoples trees where necessary/possible. MyHeritage is constantly comparing profiles from different trees looking for pairs of profiles that have overlapping information. If there is "enough" of a match, the pair of profiles are flagged as a "smart match." They use these smart matches to look for paths from one tree to another. They will also use information from the various databases they have access to. When they find a potential path to a common relative they flag it as a "theory of family relativity." :-) So, yes it is partially guess work since smart matches are not 100 percent certain.
In this particular case, it took linking 4 different trees to find a path to a potential common relative. Now comes the hard part. If I want to verify this "theory", I need to find source information that actually confirms the linkages. Which is why I want to track Nils Nilsson's movements: so I can look for his descendants that MyHeritage says are in the path to my DNA match.