Graph metric repair and random weighted graphs
Speaker: Anna GilbertDate of Talk: May 15, 2025
Upstream link: Distinguished Lecture Series
Bad news: Fan et al. showed in 2022 that both the general metric repair and increase-only metric repair problems are APX complete. Assuming the unique games conjecture, it can’t even be approximated within a constant factor. What do these fancy words mean? (I’m very curious, how do people in computation theory show problems are “hard”?)
There are several really troll ways to get around the problem of hardness:
- Assume some structure on your graph (constructed out of which data points are comparable to each other), e.g. by assuming you have a complete graph or a chordal graph.
- Shoot for an approximation rather than an optimum.
- Use some kind of randomisation (e.g. Cohen-Addad’s pivot algorithm) to get a good approximation most of the time.
Some strategies use a mix of several of these ideas.
It’s conjectured that the (increasing) metric repair problem is NP-complete for planar graph, but doable for outer-planar graphs. Somehow this places a topological constraint on the “sparseness” of the graph, but I don’t see why intuitively that this should make the problem easier. (Loosely, metric repair closely resembles graph theory problems that are hard on planar graphs but easy on outer-planar graphs.)
What do you mean, “random”?
“Excellent Terry, you’re my plant.”
Rather than studying the worst-case scenarios for the metric repair problem, instead one wishes to consider the average-case scenario. But what does one mean by “random weighted graph”? (Or “weighted random graph”?)
Given a natural number \(n\) and a parameter \(0 \leq p \leq 1\), construct a random graph on \(n\) vertices by giving any edge \(e\) a weight of \(k\) with probability \(p^k(1-p)\). (\(k=0\) corresponds to a missing edge.) These are weighted cousins of the Erdős–Rényi graphs.
Lots of Experiments
Something I appreciated about this DLS was the presence of many experimental forays instead of hard-and-fast theory. There were a lot of pretty figures that gave a lot of experimental backing to heuristics and claims that the speaker was making. Papers ought to include these too, but perhaps I’ve not been exposed to this field very much…