Med tanke på en graf G = (V, E) och ett heltal k  på N, studerar vi k-Vertex Separator (resp. k-Edge Separator), där målet är att ta bort minsta antal hörn (resp. kanter) så att varje ansluten komponent i den resulterande grafen har som mest k hörn. Vårt primära fokus ligger på fallet där k antingen är en konstant eller en långsamt växande funktion av n (t.ex. O(log n) eller n o(1) ). Våra problem kan tolkas som ett specialfall av tre generella klasser av problem som har studerats separat (balanserad grafpartitionering, Hypergraph Vertex Cover (HVC) och fast parameterdragbarhet (FPT)). Vårt huvudsakliga resultat är en O(log k)-tillnärmning algoritm för k-Vertex Separator som körs i tid 2, och en O(log k)-tillnärmning algoritm för k-Edge Separator som körs i tid n O(1). Vårt resultat på k-Edge Separator förbättrar den bästa tidigare grafpartitioneringsalgoritmen [KNS09] för liten k. Vårt resultat på k-Vertex Separator förbättrar den enkla (k + 1)-uppskattningen från HVC [BAMSN15]. När OPT > k, körtiden 2 O(k) n O(1) är snabbare än den nedre gränsen k  och (OPT) n  och (1) för exakta algoritmer som antar Exponential Time Hypotes [DDvH14]. Medan körtiden för 2 O(k) n O(1) för k-Vertex Separator verkar otillfredsställande, visar vi att det superpolynomiska beroendet av k kan behövas för att uppnå ett polylogaritmiskt approximationsförhållande, baserat på hårdheten hos Densest k-Subgraph. Vi studerar också k-Path Transversal, där målet är att ta bort det minsta antalet hörn så att det inte finns någon enkel väg av längd k. Med ytterligare idéer från FPT algoritmer och grafteori, presenterar vi en O (log k)-calimation algoritm för k-Path Transversal som körs i tid 2 O(k 3 log k) n O(1). Tidigare var förekomsten av till och med (1−δ)k-tillnärmningsalgoritm för fast δ > 0 öppen [Cam15].
Problemet har studerats i REF som k-path traversal problem som presenterar en log(k)- approximation algoritm för den oviktade versionen.
Partitioning a Graph into Small Pieces with Applications to Path Transversal
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}