Vertex Cover Problem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 8 maj 2020; kontroller kräver 3 redigeringar .

Problemet med vertextäckning är ett NP-komplett datavetenskapligt problem inom området grafteori . Används ofta i komplexitetsteori för att bevisa NP-fullständighet av mer komplexa problem.

Definition

Hönstäcket för en oriktad graf är uppsättningen av dess hörn , så att, för varje kant av grafen, åtminstone en av ändarna går in i vertexen från . $G=(V,E)$ $S$ $S$

Storleken på ett vertexskydd är antalet hörn som det innehåller.

Exempel: Grafen till höger har ett vertextäcke av storlek 4. Detta är dock inte det minsta vertextäcket, eftersom det finns mindre vertextäckare, som och . $\{1,3,5,6\}$ $\{2,4,5\}$ $\{1,2,4\}$

Problemet med vertextäcket är att hitta den minsta storleken på vertextäcket för en given graf (denna storlek kallas grafens vertextäckningsnummer ).

Entré: Räkna .

G=(V,E)

Resultat: uppsättningen är det minsta vertextäcket i grafen .

C\subseteq V

G

Frågan kan också ställas som ett likvärdigt lösningsproblem :

Indata: En graf och ett positivt heltal .

G

k

Fråga: Finns det ett vertexskydd för en graf med högst storlek ?

C

G

k

Problemet med vertextäckning liknar problemet med oberoende uppsättningar . Eftersom en uppsättning av hörn är ett vertextäcke om och endast om dess komplement är en oberoende uppsättning, minskar problemen till varandra. $C$ $V\setminus C$

NP-komplett

Eftersom vertextäckningsproblemet är NP-komplett , så finns det tyvärr inga kända algoritmer för att lösa det i polynomtid. Det finns dock approximationsalgoritmer som ger en "ungefärlig" lösning på detta problem i polynomtid - du kan hitta ett vertextäcke där antalet hörn inte är mer än dubbelt så mycket som möjligt.

En av de första metoderna för att lösa problemet som kommer att tänka på är approximation genom den giriga algoritmen : Det är nödvändigt att lägga till hörn med det maximala antalet grannar till vertextäcket tills problemet är löst, men en sådan lösning har ingen -approximation för någon konstant . $\rho$ $\rho$

En annan lösning är att hitta den maximala matchningen på den givna grafen och välja uppsättningen som vertextäcke . Riktigheten av en sådan algoritm bevisas genom motsägelse: If är inte ett vertextäcke (inte nödvändigtvis det minsta), d.v.s. , då är det inte en maximal matchning. Approximationsfaktorn bevisas enligt följande: Låt , där är grafens oberoende nummer , och är den största matchningen av grafen . Då är approximationsfaktorn . $M\in E$ $G=(V,E)$ $C=\bigcup _{e\in M}e$ $C$ $\exists e\colon e\cap C=\emptyset$ $M$ $\tau (G)=|V|-\alpha (G)$ $\alfa (G)$ $G$ $M_{max}(G)$ $G$ ${\frac {2\cdot |M|}{\tau (G)))\leqslant {\frac {2\cdot |M_{max}(G)|}{\tau (G)))\ leqslant {\frac {2\cdot |M_{max}(G)|}{|M_{max}(G)|}}=2$

Generellt kan problemet med vertextäckning approximeras med en faktor . $2-{\frac {\log \log n}{2\cdot \log n))$

Problemet med vertextäckning i tvådelade grafer

I tvådelade grafer är vertextäckningsproblemet lösbart i polynomtid, eftersom det reduceras till det största matchningsproblemet ( Königs sats ).

Länkar

Litteratur

Thomas H. Kormen et al Kapitel 36. NP-Fullständighet // Algoritmer: Konstruktion och analys = INTRODUKTION TILL ALGORITHMER. - 1:a uppl. - M. : Moskvas centrum för kontinuerlig matematisk utbildning, 2001. - S. 866.

NP-kompletta problem
Maximeringsproblem med stapling (packning)	Förpackning i behållare tvådimensionell packning linjär packning packning efter vikt förpackning efter värde Ryggsäcksproblemet
grafteori mängdteori	Vertex Cover Problem Klicka problem Problemet med en oberoende uppsättning (uppsättning) Ställtäckningsproblem Steiners problem Problemet med resande säljare Generaliserat resandeförsäljarproblem
Algoritmiska problem	Tillfredsställelseproblem för booleska formler (i konjunktiv normal form)
Logiska spel och pussel	Generaliserade taggar (spel i N 2 -1) kortaste lösningen problem Problem vars lösningar tillämpas i Tetris Generaliserat Sudoku problem Latinsk kvadrat fyllningsproblem Kakuros uppgift
Svårighetsklasser Operationsforskning Optimering Kombinatorisk optimering Tillämpad matematik Teori om algoritmer Dynamisk programmering 21 NP-komplett Karp-problem