Vi presenterar en deterministisk algoritm som beräknar edge-connektivity av en graf i nära-lineär tid. Detta är för en enkel oriktad oviktad graf G med n hörn och m kanter. Detta är den första o(mn) tid deterministiska algoritmen för problemet. Vår algoritm är lätt att utöka för att hitta en betong minsta kantklippning. I själva verket kan vi konstruera den klassiska kaktus representation av alla minimala nedskärningar i nära-linjär tid. Den tidigare snabbast deterministiska algoritmen av Gabow från STOC'91 tog O (m + λ 2 n), där λ är kantanslutningen, men λ kan vara så stor som n − 1. Karger presenterade en randomiserad nästan linjär tid Monte Carlo algoritm för minsta skär problemet vid STOC'96, men den returnerade snittet är bara minimum med hög sannolikhet. Vårt huvudsakliga tekniska bidrag är en nära-linjär tid algoritm som avtalar vertex uppsättningar av en enkel ingång graf G med minimal grad δ, producerar en multigraph G med O (m/δ ) kanter, som bevarar alla minsta skärningar av G med minst två hörn på varje sida. I vår deterministiska näralinjära tidsalgoritm, kommer vi att bryta ner problemet via low-conductance nedskärningar som hittats med PageRank a la Brin och Page (1998), som analyserats av Andersson, Chung, och Lang på FOCS'06. Normalt, sådana algoritmer för low-conductance skär är randomiserade Monte Carlo algoritmer, eftersom de förlitar sig på att gissa en bra start vertex. Men i vårt fall har vi så mycket struktur att det inte behövs några gissningar. En preliminär version [22] presenterades vid det 47:e ACM-symposiet om datateorin (STOC 2015). Deterministic Edge Connectivity in Near-Linear Time 4:3 268-269] diskuterar också multigraphs med en något sämre gräns av O (m + λ 2 n log n). En linjär tid (2 + ε)-uppskattning av egg-anslutningen presenterades av Matula [24]. Alla ovan nämnda algoritmer har varit deterministiska. Studien av randomiserade algoritmer för det globala minimala skärproblemet initierades av Karger [17]. Vi skiljer mellan Las Vegas algoritmer med garanterade korrekta svar men förväntade körtider, och Monte Carlo algoritmer med begränsad körtid men några små sannolikhet för felaktiga svar. Las Vegas algoritmer kan konverteras till Monte Carlo algoritmer (gör ett fel om algoritmen inte slutar inom en viss tid bunden), så Las Vegas är generellt sett att föredra. Om vi har ett sätt att intyga korrekta svar, då kan vi också konvertera Monte Carlo till Las Vegas genom att köra om certifieringen misslyckas. Karger [17] presenterade Las Vegas algoritmer med en (1 + o(1)) approximation till den globala minimisänkningen i O (m) förväntad tid och en exakt global minimisänkning i O (m λ) förväntad tid. Karger och Stein [20] visade att slumpmässig kantkontraktion fungerar bra för det globala minimala skärproblemet, vilket leder till en Monte Carlo-algoritm som körs i O (n 2 log 3 n) tid. Slutligen gav Karger [18] en randomiserad O (m log 3 n)-algoritm för det globala minimala skärproblemet. Karger [18] påpekar att vi saknar ett motsvarande effektivt sätt att intyga att den returnerade skärningen är minimal. För mer detaljerad historia för det globala minimala skärproblemet hänvisar vi läsaren till boken av Schrijver [29]. Vi noterar att en deterministisk nästan linjär tid min-cut algoritm är känd för planar grafer [4]. I den här artikeln presenterar vi en deterministisk nästan linjär tidsalgoritm för beräkning av kantkonnektivitet och en global minsta skärning för en enkel graf. Med nästan linjär tid menar vi O (m) tid där O döljer loggfaktorer. Detta är den första o(mn) tid deterministiska algoritmen för problemet. Det tidigare bästa O (m + λ 2 n) tidsbundet av Gabow [9] är bra om λ är liten, men vi kan ha λ =  på (n). Vi noterar att vi i den här artikeln inte försöker minimera antalet loggfaktorer som döljs i O-notationen, inte heller räknar vi dem explicit, t.ex., vi kommer att fritt använda minskningar som O (f (n)) O ( ska(n)) = O (f (n)](n)). I slutet kommer vi att löst uppskatta antalet till 12, vilket uppskattar körtiden för vår algoritm till O (m log 12 n). Syftet med denna uppskattning är bara att uppmuntra andra forskare att komma ner till ett mer rimligt antal loggfaktorer, vilket ger dem en konkret skyldighet att förbättra sig. Ja, Henzinger m.fl. [14] har nyligen förbättrat viktiga delar av vår konstruktion med den totala körtiden ner till O (m(log n) 2 (log log n) 2 ). På nästan linjär tid kan vi också beräkna kaktusrepresentationen av alla globala miniminedskärningar som införts i referens [5]. För att göra det involverar vi Gabows tidigare snabbaste O (λm) tidsalgoritm [10] som en svart låda. Vi noterar här att Karger och Panigrahi [19] har presenterat en nästan linjär tid Monte Carlo algoritm för att bygga kaktus datastruktur. Hädanefter överväger vi bara oviktade grafer. Vi får en enkel graf, och vi vill hitta en min-cut i nästan linjär tid. Vi kan anta att minimigraden δ är minst polylogaritmisk; för annars kan vi bara använda Gabow's [9], algoritm för att hitta min-cut i O (λm) = O (δm) = O (m) tid. För våra syften räcker det att anta δ ≥ log 6 n. Med en trivial snitt menar vi ett snitt där en sida består av en enda vertex. Vi noterar att minimigraden δ är en övre gräns på kanten-anslutning λ, eftersom det är den minsta storleken av en trivial snitt. Att hitta δ är trivialt, men vi kunde ha λ < δ. Vad som gör enkla grafer speciellt är att om du har en icke-trivial klippa i en enkel graf, då varje sida behöver ha minst δ hörn. Denna iakttagelse och dess samband med ledning kommer att diskuteras nedan i avsnitt 1.4. Genom att teckna en vertex uppsättning U  på V, menar vi identifiera hörnen i U samtidigt ta bort kanterna mellan dem. Vi kanske inte kontrollerar att U är ansluten, så detta kanske inte motsvarar kant kontraktioner. Namnen på de kanter som inte avlägsnats bevaras, och ett snitt bevaras om alla kanterna bevaras. Den grundläggande idén i vår min-cut algoritm är att göra sammandragningar i grafen samtidigt bevara alla icke-triviala min-cuts, fortsätter tills grafen är så liten att Gabow algoritm kan avsluta i O (m) tid, där m är antalet kanter i den ursprungliga enkla inmatningskurvan. Sammandragningarna kan införa parallella kanter, så internt, algoritmen fungerar med en multigraph. Vårt huvudsakliga tekniska bidrag är att bevisa följande teorem: Theorem 1.1. Med tanke på en enkel ingång graf G med n hörn, m kanter, och minimal grad δ, i nära-linjär tid, kan vi kontrakt vertex uppsättningar som producerar en multigraph G, som endast har m (m/δ ) kanter, men som bevarar alla icke-triviala min-cuts av G. Från Theorem 1.1, vi lätt få vår nära-linjära min-cut algoritm: Corollary 1.2. Vi kan hitta en minsta skärning av en enkel graf G i nästan linjär tid. Bevis. Låt δ vara den minsta graden av G. Vi tillämpar Theorem 1.1 till G producerar grafen G. Vi kör nu Gabow min-cut algoritm [9] på G, ber det att misslyckas om kant-anslutningen är över δ. Detta tar O (δm) = O (m) tid, och nu jämför vi produktionen med den minsta graden δ. På samma sätt kan vi inom nästan linjär tid få kaktus representation av alla globala minimala nedskärningar från referens [5] genom att tillämpa kaktusalgoritmen Gabow [10] till G. Efter att ha producerat kaktus C av G, behöver vi bara lägga till min-graders hörn som extra nålar för att få kaktusarna i inmatningskurvan G. En beskrivning av detta inklusive definitionen av min-cut kaktus ges i Avsnitt 8. Vi noterar att Theorem 1.1 inte kan hålla om inmatningsgrafen är en multigraf. För att se detta, överväga en cykel av längd n ≥ 4, men där varje kant ersätts av k = (log n)  på (1) parallella kanter. Nu är varje kant involverad i en icke-trivial min-cut där varje sida består av minst två på varandra följande hörn, och därför kan inga kanter dras ihop. Detta visar att sammandragningarna av Theorem 1.1 är mycket specifika för enkla grafer. Dessutom kan de bara bevara icke-triviala min-cuts, för om vi till exempel tar en komplett graf, då varje kant är i en trivial min-cut. Dock kan en komplett graf kontrakteras till en enda vertex, eftersom den inte har någon icke-trivial min-cut. Ytterligare resultat. Även om minskningen i Theorem 1.1 av antalet kanter ser ut som en typisk sparifiering, är det inte, för kanterna är kontrakterade, inte borttagna, och den resulterande G kommer att ha mycket färre hörn än G. I själva verket, kombinera med tekniker Nagamochi och Ibaraki [27], kan vi se till att antalet hörn kvar efter sammandragningarna är O (n/δ ). Eftersom antalet min-cuts i någon multigraph är som mest kvadratisk, en trevlig konsekvens är att antalet min-cuts i en enkel graf med n hörn och minimum grad δ är som mest n + O ((n/δ ) 2 ). Vi är inte medvetna om någon annan som har observerat att en stor minimigrad i en enkel graf innebär några minimala nedskärningar, även om det verkar som om detta faktum också kan härledas från kaktus representation [5]. Vår sammandragningsteknik kan stärkas för att även bevara ungefärliga min-snitt. Mer exakt, med min-grad δ och kant anslutning λ, kommer vi att stärka Theorem 1.1 till
Denna teknik introducerades av Kawarabayashi och Thorup REF, som uppnår nästan linjär deterministisk tid (uppskattas vara O(m log 12 n)).
Deterministic Edge Connectivity in Near-Linear Time
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}