I detta papper presenterar vi en enkel men kraftfull subgraph provtagning primitiva som är tillämplig i en mängd olika beräkningsmodeller inklusive dynamiska grafströmmar (där indatagrafen definieras av en sekvens av kant/hyperedge tillägg och raderingar) och distribuerade system som MapReduce. När det gäller dynamiska grafströmmar använder vi denna primitiva för att bevisa följande resultat: • Matchning: Vårt huvudsakliga resultat för matchningar är att det finns añ O(k 2 ) rymdalgoritm som returnerar kanterna på en maximal matchning på antagandet att kardinaliteten är som mest k. Den bästa tidigare algoritmen som används Õ(kn) utrymme där n är antalet hörn i grafen och vi visar att vårt resultat är optimal upp till logaritmiska faktorer. Vår algoritm har Õ(1) uppdateringstid. Vi visar också att det finns en Õ(n 2 /α 3 ) rymdalgoritm som returnerar en α- approximation för matchningar av godtycklig storlek. I självständigt arbete, Assadi et al. (SODA 2016) bevisade att denna approximationsalgoritm är optimal och tillhandahöll en alternativ algoritm. Vi generaliserar våra exakta och ungefärliga algoritmer till viktad matchning. För grafer med låg arboricity liksom planar grafer, det utrymme som krävs för konstant approximation kan ytterligare minskas. Även om det har varit en betydande mängd arbete på ungefärlig matchning i infoga-bara grafströmmar, dessa är de första icke-triviala resultaten i den dynamiska inställningen. • Vertex Cover and Hitting Set: Det finns en Õ(k d ) rymdalgoritm som löser minsta träffuppsättningsproblem där d är kardinaliteten för inmatningsuppsättningarna och k är en övre gräns för storleken på den minsta träffuppsättningen. Vi bevisar att detta är optimalt upp till logaritmiska faktorer. Vår algoritm har Õ(1) uppdateringstid. Fallet d = 2 motsvarar minsta vertex-täckning. Slutligen anser vi att en större familj av parameteriserade problem (inklusive b-matchning, delningsvägar, vertex färgning bland andra) för vilka vår subgraf provtagning primitiv ger snabb, liten utrymme dynamisk graf ström algoritmer. Vi visar sedan lägre gränser för naturliga problem utanför denna familj.
Algoritmer för att bygga en maximal matchning på de flesta k kanter i en oviktad eller en viktad graf har också studerats under den dynamiska streaming modellen REF.
Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
{'venue': 'SODA', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}