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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.