Iterativ komprimering

Iterativ komprimering är en algoritmisk teknik för att utveckla fast-parametriskt lösbara algoritmer . I den här tekniken, vid varje steg , läggs ett element (som en grafvertex ) till problemet , och innan du lägger till det hittas en liten lösning på problemet.

Historik

Tekniken utvecklades av Reed, Smith och Wetta [1] för att visa att problemet med att ta bort udda cykler är lösbart i tid för grafer med n hörn, m kanter och k antal hörn som ska tas bort . Problemet med borttagning av udda cykel är problemet med att hitta den minsta uppsättningen av hörn som inkluderar minst en hörn från vilken som helst udda cykel. Den parametriska komplexiteten i detta problem förblev öppen under lång tid [2] [3] . Senare blev denna teknik mycket användbar för att bevisa resultat på lösbarhet med fasta parametrar . Nu anses denna teknik vara en av de grundläggande inom området parametriserade algoritmer. $O(3^{k}kmn)$

Iterativ komprimering har framgångsrikt använts i många problem, såsom att ta bort udda cykler (se nedan) och ta bort kanter för att erhålla tvådelad , hitta cykelskärande hörn , ta bort klusterpunkten och hitta skärande hörn i orienterad cykel [4] . Metoden har också framgångsrikt använts för exakta exponentiella tidsalgoritmer för att hitta en oberoende uppsättning [5] .

Teknik

Iterativ komprimering är tillämplig, till exempel för parametriserade problem på grafer , vars indata är en graf G =( V , E ) och ett naturligt tal k , och problemet ställs som en kontroll för att det finns en lösning (en uppsättning av hörn) av storlek . Antag att problemet är stängt under genererade subgrafer (om det finns en lösning för en given graf, så finns en lösning av denna storlek eller mindre för alla genererade subgrafer) och att det finns en effektiv procedur som avgör om en lösning av storlek Y kan vara krympt till en mindre lösning av storlek k . $\leqslant k$ $\leqslant k$ $k+1$

Om detta antagande håller, kan problemet lösas genom att lägga till hörn en i taget och hitta en lösning för den genererade subgrafen enligt följande:

Vi börjar med en subgraf som genereras av en uppsättning hörn S med storleken k och en lösning X som är lika med S själv .
För tillfället tar vi följande steg: $S\neq V$
- Låt v vara vilken vertex som helst , lägg till v till S $V\backslash S$
- Vi kontrollerar om lösningen med ( k + 1) hörn Y = X ∪ {x } för S kan komprimeras till en lösning med k hörn.
- Om lösningen inte kan komprimeras avslutar vi algoritmen - ingångsgrafen har ingen lösning med k hörn.
- Annars antar vi att X är en ny komprimerad lösning och återgår till början av loopen.

Denna algoritm kallar komprimeringsrutinen ett linjärt antal gånger. Därför, om en variant av komprimeringsproceduren körs under en fast-parametriskt lösbar tid, det vill säga för någon konstant c, så löper den iterativa komprimeringsproceduren för att lösa hela problemet i tid . Samma teknik kan användas för att hitta kantuppsättningar för egenskaper hos grafer som är stängda under subgrafer (andra än en genererad subgraf) eller andra egenskaper inom grafteorin. När värdet på parametern k är okänt kan det hittas med en exponentiell sökning på yttre nivå eller en linjär sökning efter det optimala valet av k , med en sökning vid varje steg, baserat på samma iterativa komprimeringsalgoritm. ${\displaystyle f(k)\cdot n^{c))$ $f(k)\cdot n^{c+1}$

Applikationer

I den ursprungliga artikeln visade Reed, Smith och Wetta hur man gör en graf tvådelad genom att ta bort högst k hörn i tiden . Senare gav Lokshtanov, Saurabh och Sikdar en enklare algoritm, som också använde iterativ komprimering [6] . För att komprimera den borttagna uppsättningen Y av storleken k + 1 till en uppsättning X av storleken k kontrollerar deras algoritm alla partitioner av uppsättningen Y i tre delmängder - en delmängd av uppsättningen Y som hör till den nya borttagna uppsättningen, och två delmängder av mängden Y som hör till två delar av den tvådelade grafen som återstår efter att ha tagit bort mängden X . När dessa tre uppsättningar har valts, kan de återstående hörnen av uppsättningen X som ska tas bort (om en sådan finns) hittas från dem med hjälp av Ford-Fulkerson-algoritmen . $O(3^{k}kmn)$ $3^{k+1}$

Vertextäckning är ett annat exempel för vilket iterativ komprimering kan tillämpas. Problemet med vertextäckning ges en graf och ett naturligt tal k som inmatning , och algoritmen måste avgöra om det finns en uppsättning X med k hörn så att vilken kant som helst faller in mot en vertex i X. I komprimeringsvarianten är ingången en uppsättning Y med hörn som faller in mot alla kanter på grafen, och algoritmen måste hitta en uppsättning X av storlek k med samma egenskap, om en sådan finns. Ett sätt att göra detta är att testa alla alternativ med vilka uppsättningen Y tas bort från täckningen och infogas tillbaka i grafen. En sådan iteration kan bara fungera om inte två hörn som ska tas bort är intill varandra, och för varje sådan variant måste subrutinen inkludera i täckningen alla hörn utanför Y som faller samman med kanten som blir avslöjad genom denna borttagning. Användningen av en sådan subrutin i en iterativ komprimeringsalgoritm ger en enkel algoritm över tiden för vertextäckning. $G=(V,E)$ $k+1$ $2^{k+1}$ $O(2^{k}n^{2})$

Se även

Parametrisk reduktion , en annan teknik för algoritmer som kan avgöras med fasta parametrar

Anteckningar

↑ Reed, Smith, Vetta, 2004 , sid. 299–301.
↑ Niedermeier, 2006 , sid. 184.
↑ Cygan, Fomin, Kowalik et al., 2015 , sid. 555.
↑ Guo, Moser, Niedermeier, 2009 , sid. 65–80.
↑ Fomin, Gaspers, Kratsch et al., 2010 , sid. 1045–1053.
↑ Lokshtanov, Saurabh, Sikdar, 2009 , sid. 380–384.

Litteratur

Bruce Reed, Kaleigh Smith, Adrian Vetta. Hitta udda cykeltransversaler // Operations Research Letters. - 2004. - T. 32 , nr. 4 . - doi : 10.1016/j.orl.2003.10.009 .
Rolf Niedermeier. Inbjudan till algoritmer med fasta parametrar. - Oxford University Press, 2006. - V. 31. - (Oxford föreläsningsserie i matematik och dess tillämpningar). — ISBN 9780198566076 .
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh. Parameteriserade algoritmer. - Springer, 2015. - ISBN 978-3-319-21274-6 .
Jiong Guo, Hannes Moser, Rolf Niedermeier. Iterativ komprimering för att exakt lösa NP-hårda minimeringsproblem // Algoritmik för stora och komplexa nätverk. - Springer, 2009. - T. 5515. - S. 65–80. — (Föreläsningsanteckningar i datavetenskap). - ISBN 978-3-642-02093-3 . - doi : 10.1007/978-3-642-02094-0_4 .
Fedor Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh. Iterativ komprimering och exakta algoritmer // Teoretisk datavetenskap. - 2010. - T. 411 , nr. 7 . — S. 1045–1053 . - doi : 10.1016/j.tcs.2009.11.012 .
Daniel Lokshtanov, Saket Saurabh, Somnath Sikdar. Enklare parametriserad algoritm för OCT // 20th International Workshop on Combinatorial Algorithms, IWOCA 2009, Hradec nad Moravicí, Tjeckien, 28 juni–2 juli 2009, Revised Selected Papers. - Springer, 2009. - T. 5874. - S. 380-384. — (Föreläsningsanteckningar i datavetenskap). - ISBN 978-3-642-10216-5 . - doi : 10.1007/978-3-642-10217-2_37 .