There are multiple results (Vassilevska and Williams STOC09, for instance) on computing efficiently minimal-weight triangles (or more generally patterns) in node-weighted graphs. Several of these results prove more efficient bounds when the graph is sparse.
We can show similar bounds on minimal weight triangles in a dense graph replacing the number of edges $m$ with number of missing edges $m'=n^2-m$, but is there a general argument (e.g., some kind of duality) that would allow to systematically translate bounds on sparse graphs into bounds on dense graphs for such weighted triangles and pattern problems?
Remark: of course I assume we are provided with the list of missing edges, in order to avoid the $n^2$ cost.
