(one of the paper coauthors here)

While diamond dependencies are indeed one of the big complicating factors, the implementation and engineering details that remain matter a lot too. Section 4 covers the spectrum of quality-of-life features that do introduce subtleties: for example the order of resolution, peer dependencies, depops/features. These are all important for the ergonomics of package constraint expressions, irrespective of whether diamond dependencies are present or not.

The engineering details also flow from the practical implementation constraints: it makes a big difference if solving can done in linear time or if there's a noticeable pause or (worse) you need a big centralised solver. The determinism also guides the implementation of chains of trust.