Iterativ komprimering

Inom datavetenskap är iterativ komprimering en algoritmisk teknik för design av algoritmer som kan hanteras med fasta parametrar, där ett element (som t.ex. ett hörn på en graf ) läggs till problemet i varje steg, och en liten lösning för problemet före till tillägget används för att hjälpa till att hitta en liten lösning på problemet efter steget.

Tekniken uppfanns av Reed, Smith och Vetta för att visa att problemet med udda cykel transversal var lösbar i tiden   O (3 ^k kmn ) , för en graf med n hörn, m kanter och udda cykel transversal nummer k . Udda cykel transversal är problemet med att hitta den minsta uppsättningen av hörn i en graf som inkluderar minst en vertex från varje udda cykel; dess parameteriserade komplexitet var en långvarig öppen fråga. Denna teknik visade sig senare vara mycket användbar för att visa resultat med fasta parametrar . Det anses nu vara en av de grundläggande teknikerna inom området parametriserad algoritm.

Iterativ komprimering har använts framgångsrikt i många problem, t.ex. transversal udda cykel (se nedan) och kantbidelning , återkopplingsvertexuppsättning , klustervertexborttagning och riktad återkopplingsvertexuppsättning. Det har också använts framgångsrikt för exakta exponentiella tidsalgoritmer för oberoende uppsättning .

Metod

Iterativ komprimering gäller till exempel för parameteriserade grafproblem vars indata är en graf G = ( V , E ) och ett naturligt tal k , och där problemet är att testa förekomsten av en lösning (en uppsättning hörn) med storlek ≤ k . Antag att problemet är stängt under inducerade subgrafer (om en lösning av storlek ≤ k finns i en given graf, så finns en lösning av denna storlek eller mindre också i varje inducerad subgraf) och att det finns en effektiv subrutin som avgör om en lösning Y av storlek k + 1 kan komprimeras till en mindre lösning av storlek k .

Om dessa antaganden är uppfyllda kan problemet lösas genom att lägga till hörn i taget till en inducerad subgraf och hitta lösningen på den inducerade subgrafen, enligt följande:

1. Börja med en subgraf inducerad av en vertexuppsättning S av storleken k och en lösning X som är lika med S själv.
2. Medan S ≠ V utför du följande steg:
   • Låt v vara valfri hörn av V \ S och lägg till v till S
   • Testa om ( k + 1) -vertexlösningen Y = X ∪ {x } till S kan komprimeras till en k -vertexlösning.
   • Om den inte kan komprimeras, avbryt algoritmen: ingångsgrafen har ingen k -vertexlösning.
   • Ställ annars in X på den nya komprimerade lösningen och fortsätt slingan.

Denna algoritm anropar komprimeringssubrutinen ett linjärt antal gånger. Därför, om kompressionsvarianten är lösbar i lösbar tid med fasta parametrar, dvs ^{f +1 (} k ) · nc för någon konstant c , så körs den iterativa komprimeringsproceduren som löser hela problemet i f ( k ) · nc tid . Samma teknik kan användas för att hitta uppsättningar av kanter för grafegenskaper stängda under subgrafer (snarare än inducerad subgraf), eller för andra egenskaper utöver grafteorin. När värdet på parametern k är okänt kan det hittas genom att använda en yttre nivå av exponentiell sökning eller sekventiell sökning för det optimala valet av k , med varje steg i sökningen baserat på samma iterativa komprimeringsalgoritm.

Ansökningar

  I deras ursprungliga uppsats Reed et al. visade hur man gör en graf tvådelad genom att radera högst k hörn i tiden O (3 ^k kmn ). Senare gavs en enklare algoritm, även med iterativ komprimering, av Lokshstanov, Saurabh och Sikdar. För att komprimera en raderingsuppsättning Y med storleken k + 1 till en raderingsuppsättning X med storleken k , testar deras algoritm alla 3 ^{k +1} -partitionerna av Y i tre delmängder: delmängden av Y som hör till den nya raderingsuppsättningen , och de två delmängder av Y som hör till de två sidorna av den tvådelade grafen som finns kvar efter radering av X . När dessa tre uppsättningar har valts, kan de återstående hörnen av en raderingsuppsättning X (om den finns) hittas från dem genom att tillämpa en max-flow min-cut- algoritm.

Vertexskydd är ett annat exempel för vilket iterativ kompression kan användas. I vertextäckningsproblemet tas en graf G = ( V , E ) och ett naturligt tal k som indata och algoritmen måste avgöra om det finns en uppsättning X med k hörn så att varje kant faller in i en vertex i X . I komprimeringsvarianten av problemet är ingången en uppsättning Y av k + 1 hörn som faller in på alla kanter av grafen, och algoritmen måste hitta en uppsättning X av storlek k med samma egenskap, om den finns. Ett sätt att göra detta är att testa alla 2 ^{k + 1} val av vilken delmängd av Y som ska tas bort från omslaget och återinföras tillbaka i grafen. Ett sådant val kan bara fungera om inga två borttagna hörn är intill varandra, och för varje sådant val måste subrutinen inkludera i omslaget alla hörn utanför Y som faller in mot en kant som blir avslöjad genom detta avlägsnande. Att använda denna subrutin i en iterativ komprimeringsalgoritm ger en enkel   O (2 ^k n ² ) algoritm för vertextäckning.

Se även

• Kernelisering , en annan designteknik för algoritmer som kan hanteras med fasta parametrar