A professor I knew in grad school told me about asking his students to reduce an NP-Complete problem to another, then back to the original, then back again and then watching with amusement as the resulting reductions grew out of control. Eventually this led me to think that there should be some theory that could get a handle on the size introduced by reductions.
For example, what prevents us from taking a source NP-Complete problem (3-SAT, say) and adding a particular type of structure in the resulting NP-Complete problem (HAMILTONIAN CYCLE, say) such that reducing back to the original (3-SAT) would notice the structure and get back the original instance? Maybe the original problem would need to be 'pre-structured' so that this type of 'ping-ponging' between NP-Complete problems could occur.
In other words, what prevents us from adding some (polynomial amount of) structure to our NP-Complete problems so that reductions from one NP-Complete problem to another converge in size? The algorithms for reductions would need to notice the structure embedded in the instance and add their own if need. I could imagine the features to be indicators for the reduction algorithm so that subsequent reductions would be able to avoid instance inflation.
What do these reductions look like? What's our current best 'inflation factor'?
Surely I'm not the first to think of this. Does anyone have references that discuss this type of reduction? Barring that, does anyone have any ideas on what type of structure needs to be added to achieve this result? I would be surprised if such a method wasn't possible but I would happily hear about any references about impossibility of such a method.