Graph-Sparsifikation durch effektive Widerstände

Wir präsentieren einen nahezu linearen Algorithmus, der hochwertige Sparsifizierer für gewichtete Graphen erzeugt. Gegeben ist ein gewichteter Graph G = (V, E, w) und ein Parameter ε > 0, produzieren wir einen gewichteten Teilgraphen H = (V, ~E, ~w) von G, so dass |~E| = O(n log n/ε²) und für alle Vektoren x in Rᵛ. (1-ε) ∑uv ∈ E (x(u) - x(v))²wuv ≤ ∑uv in ~E (x(u) - x(v))²~wuv ≤ (1+ε) ∑uv ∈ E (x(u) - x(v))²wuv. Dies verbessert die von Spielman und Teng konstruierten Sparsifizierer, die O(n logc n) Kanten für eine große Konstante c hatten, sowie die von Benczur und Karger, die (1) nur für x in 0, 1ᵛ erfüllten. Wir vermuten die Existenz von Sparsifizierern mit O(n) Kanten und bemerken, dass diese das Konzept der Expandergraphen verallgemeinern würden, die konstantgradige Sparsifizierer für den kompletten Graphen sind. Ein entscheidender Bestandteil unseres Algorithmus ist eine von unabhängigem Interesse: ein nahezu linearer Algorithmus, der eine Datenstruktur aufbaut, aus der wir den approximativen effektiven Widerstand zwischen beliebigen zwei Knoten in einem Graphen in O(log n) Zeit abfragen können.