Maximal matchning och minimal vertex omslag är bland de mest grundläggande grafoptimering problem. Nyligen infördes randomiserade komposerbara kärnor som en effektiv teknik för att lösa dessa problem i olika modeller av beräkning på massiva grafer. I denna teknik, en partitionerar kanterna på en ingång graf slumpmässigt i flera bitar, komprimerar varje bit i en mindre subgraf, nämligen en coreset, och löser problemet på föreningen av dessa kärnor för att hitta den slutliga lösningen. Genom att designa små slumpmässiga komposerbara kärnor kan man få effektiva algoritmer, på ett svart-box sätt, i flera beräkningsmodeller inklusive streaming, distribuerad kommunikation, och den massiva parallella beräkning (MPC) modellen. Vi utvecklar slumpmässiga komposerbara kärnor av storlek O(n) som för varje konstant ε > 0, ger en (3/2 + ε)-uppskattning till matchning och en (3 + ε)-uppskattning till vertex-täckning. Våra kärnor förbättras på den tidigare bästa approximationen förhållandet av O(1) för matchning och O(log n) för vertex cover. Framför allt, vårt resultat för matchning går utöver en 2- approximation, vilket är en naturlig barriär för maximal matchning i många modeller av beräkningar. Våra kärnuppsättningar leder till förbättrade algoritmer för den samtidiga kommunikationsmodellen med slumpmässigt partitionerad ingång, den strömmande modellen när inmatningen anländer i en slumpmässig ordning, och MPC-modellen med O(n ε n) minne per maskin och endast två MPC rundor. Dessutom, inspirerat av det senaste arbetet av Czumaj et al. (arXiv 2017), studerar vi algoritmer för matchning och vertex cover i MPC-modellen med endast O(n) minne per maskin. Med utgångspunkt i våra coresetkonstruktioner utvecklar vi parallella algoritmer som ger en O(1)-approximering till både matchande och vertex-täckning i endast O(log log n) MPC rundor och O(n) minne per maskin. Vi förbättrar ytterligare approximationen av vår matchande algoritm till (1 + ε) för alla konstant ε > 0. Våra resultat avgör flera öppna frågor från Czumaj et al. En viktig teknisk ingrediens i vårt papper är en ny tillämpning av kantgrader begränsade subgrafer (EDCS) som tidigare infördes i samband med att bibehålla matchningar i dynamiska grafer. I hjärtat av våra bevis finns nya strukturella egenskaper hos EDCS som identifierar dessa subgrafer som glesa certifikat för stora matchningar och små vertex-överdrag som är ganska robusta för provtagning och komposition. * sassadi@cis.upenn.edu.
Arbetet av Assadi et al. REF tar också upp dessa två problem, och ger ett sätt att konstruera en (1 + ε) ungefärlig maximal matchning och en O(1)-ungefärlig minsta vertex täcka i O(log log n) rundor när utrymmet per maskin är Õ(n).
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}