I haven't read the paper either ;] (just skimmed bibliography to get a sense, as I usually do first) but Arora (one of the authors) is an expert on probabilistic approximations, and they do cite 2001 paper by Feige which is standard ref. on approximations to dense subgraph. Also, what they reduce their model to is a "planted" hidden clique variant of dense subgraph, a problem which is hard "on average" and not only in worst case (propety used in crypto protocols also).
With poloynomial time problem reductions (which is what is usually used with showig a problem is NP complete, though I too haven't read the paper) equivilent just means something like "an exact solution in A translates to an exact solution in B." Unfortunatly, in general, an approxmimate solution to A doens't translate to an approxmiate solution to B.
Note: This part is me really guessing so please don't take it at face falue.
If I had to guess, I'd say that this is like densest subgraph in the sense that:
The mortgages are the nodes.
High correlation --> Edge connections.
So there might be a straightforward translation of approxmiate solutions. Like I said, just a guess.
I'd guess that even if you can't solve the problem exactly you could find a tractable probabilistic solution that works x% of the time and traders spend their time finding such solutions. The real problem is that for the (1-x)% of the time when it doesn't work it wrecks major havoc.
so he says that a buyer cannot determine that a CDO has been maliciously packed with bad assets because this is equivalent to finding the densest subgraph. Is there a reason why an approximate solution to the dense subgraph problem could not allow one to conclude that a CDO was more likely to have been stuffed with garbage?
clearly if the problem is truly like encryption as Appel says then an approximate solution is worthless (an approximate encryption key would still give you garbage)