Vi utvecklar ett ramverk för graf sparifiering och skissning, baserat på ett nytt verktyg, kort cykel sönderdelningen av en oviktad graf i en kant-delad samling av korta cykler, plus ett litet antal extra kanter. En enkel observation ger att varje graf G på n hörn med m kan brytas ned i O (mn) tid i cykler av längd högst 2 log n, och högst 2n extra kanter. Vi ger en m 1+o(1) tid algoritm för att konstruera en kort cykel sönderdelning, med cykler av längd n o(1), och n 1+o(1) extra kanter. Både existentiella och algoritmiska varianter av denna nedbrytning gör det möjligt för oss att göra framsteg på flera öppna problem i randomiserade grafalgoritmer. 1) Vi presenterar en algoritm som löper i tiden m 1+o(1) ε −1,5 och återgår (1 ± ε)-tillnärmelse till effektiva motstånd av alla kanter, förbättra över det tidigare bästa av O(min{mε −2, n 2 ε −1 }). Denna rutin ger i sin tur en algoritm för att approximera bestämningsfaktorn för en graf Laplacian upp till en faktor (1 ± ε) i m 1+o(1) + n 15/8+o(1) ε −7/4 tid. 2) Vi visar existens och effektiva algoritmer för att konstruera grafiska spektralskisser - en fördelning över grafer H med ungefär nε −1 kanter så att för en fast vektor x, Vi har x LH x = (1 ± ε)x LGx och x L + H x = (1±ε)x L + G x med hög sannolikhet, där L är grafen Laplacian och L + är dess pseudoinvers. Detta innebär att det finns motståndssparsifierare med ungefär nε −1 kanter som bevarar det effektiva motståndet mellan varje par hörn upp till (1 ± ε). 3) Genom att kombinera korta cykel sönderdelningar med kända verktyg i graf sparifiering, visar vi förekomsten av nästan-linjär storlek-bevarande spektral sparifierare, samt betydligt glesare approximationer av Eulerska riktade grafer. Det senare är avgörande för de senaste genombrotten på snabbare algoritmer för att lösa linjära system i regisserade Laplacians. Löptiden och utgångsegenskaperna hos våra spektralskisser och gradbevarande (direkta) sparifieringsalgoritmer begränsas av effektiviteten i våra rutiner för att konstruera korta cykeldekompositioner. Förbättrade algoritmer för korta cyklers nedbrytningar kommer att leda till förbättringar för var och en av dessa algoritmer. På grund av utrymmesbegränsningar skjuts de flesta bevisen upp till den fullständiga versionen [1] som finns på http://arxiv.org/abs/1805.12051. Begränsa ovanstående definition endast till vektorer x  på {±1} V, man får skära sparifierare. För en graf G med n hörn och m kanter, Spielman och Teng gav den första algoritmen för att bygga spektral sparifierare med O (nε −2 ) kanter 1. Spielman och Srivastava [15] visade att man kunde konstruera en glesare för G genom oberoende provtagning O(nε −2 log n) kanter med sannolikheter som står i proportion till deras hävstångspoäng i G. Slutligen bevisade Batson, Spielman och Srivastava [16] 1 O(·) notation döljer poly(log n) faktorer.
REF presenterar en algoritm som beräknar de effektiva motstånden från alla kanter till (1 ± )-fel i O(m 1+o(1) –1,5 ) tid.
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
{'venue': '2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}