Udda cykel tvärgående

En graf med en udda cykeltransversal av storlek 2: borttagning av de två blå bottenpunkten lämnar en tvådelad graf.

I grafteorin är en udda cykel tvärgående av en oriktad graf en uppsättning hörn av grafen som har en icke-tom skärningspunkt med varje udda cykel i grafen. Att ta bort hörnen för en udda cykel transversal från en graf lämnar en tvådelad graf som den återstående inducerade subgrafen .

Förhållande till vertextäcke

En given $n$ -vertexgraf $G$ har en udda cykeltransversal av storleken $k$ , om och endast om den kartesiska produkten av graferna $G\square K_{2}$ (en graf som består av två kopior av $G$ , med motsvarande hörn av varje kopia sammankopplade med kanterna på en perfekt matchning ) har ett vertextäcke av storleken $n+k$ . Den udda cykeltransversalen kan omvandlas till ett vertexskydd genom att inkludera båda kopiorna av varje vertex från transversalen och en kopia av varje återstående vertex, vald från de två kopiorna enligt vilken sida av bipartitionen som innehåller den. I den andra riktningen kan ett vertexomslag av $G\square K_{2}$ omvandlas till en udda cykel tvärgående genom att endast behålla de hörn för vilka båda kopiorna finns i omslaget. Topparna utanför den resulterande transversalen kan delas upp i två delar beroende på vilken kopia av vertexen som användes i omslaget.

Algoritmer och komplexitet

Problemet med att hitta den minsta udda cykel transversal, eller motsvarande den största bipartite inducerade subgrafen, kallas också udda cykel transversal, och förkortas som OCT. Det är NP-svårt , som ett specialfall av problemet med att hitta den största inducerade subgrafen med en ärftlig egenskap (eftersom egenskapen att vara tvådelad är ärftlig). Alla sådana problem för icke-triviala egenskaper är NP-hårda.

Ekvivalensen mellan transversal- och vertextäckproblemen med udda cykel har använts för att utveckla algoritmer med fasta parametrar för transversal udda cykel, vilket innebär att det finns en algoritm vars körtid kan begränsas av en polynomfunktion av grafens storlek multiplicerad med en större funktion av $k$ . Utvecklingen av dessa algoritmer ledde till metoden för iterativ komprimering , ett mer allmänt verktyg för många andra parametriserade algoritmer. De parametriserade algoritmerna som är kända för dessa problem tar nästan linjär tid för varje fast värde på $k$ . Alternativt, med polynomberoende av grafstorleken, kan beroendet av $k$ göras så litet som $2,3146^{k}$ . Däremot tillåter det analoga problemet för riktade grafer inte en algoritm med fasta parametrar under standardkomplexitetsteoretiska antaganden.

Se även

• Maximalt snitt , motsvarar att begära en minsta uppsättning kanter vars borttagning lämnar en tvådelad graf