A gráfelmélet és elméleti számítógép-tudomány , a probléma a minimális fedezeti csúcsainak (vagy problémája a minimális keresztirányú , Vertex Cover angolul) egy klasszikus algoritmikus probléma. Grafikon alapján abból áll, hogy megtalálja az összes szélét lefedő minimális csúcskészletet.
A döntési probléma ezzel kapcsolatos optimalizálási probléma az, NP-teljes , és az egyik a Karp a 21 NP-teljes problémák . A komplexitáselméletben gyakran használják annak bizonyítására, hogy más bonyolultabb problémák NP-hiányosak.
A vertex vagy keresztirányú lefedettség egy gráf G halmaza C csúcsok úgy, hogy mindegyik éle G = ( V , E ) van az eset, hogy legalább egyik csúcsa C , azaz egy részhalmaza csúcsok úgy, hogy minden egyes éle az egyik, vagy . A C halmaz lefedi-e G éleit . Az alábbi ábra két grafikon csúcsainak lefedettségét mutatja be (a C halmazt a vörös csúcsok alkotják).
A minimális csúcsfedél a minimális méretű csúcsok fedele. Az alábbi ábra a minimális csúcsfedésekre mutat példákat ugyanazon grafikonokon, mint fent.
Ha egy sor csúcsok egy keresztirányú, a komplement egy stabil (vagy független halmazt ). Tehát egy n csúcsú gráfnak akkor és akkor csak akkor van k keresztirányú keresztiránya, ha stabil az n - k méretű . Azonnal levezetjük a következő eredményt:
Gallai „s tétel (1959) - Mindenesetre grafikon , α (G) + τ (G) = n.
ahol α (G) a maximális stabilitás méretét , τ (G) a minimális keresztirányú méretét és .
Az optimalizálási probléma, amelyet minimális csúcsfedezeti problémának hívunk, a következő:
Bemenet: egy G grafikon Kérdés: mi az a legkisebb egész szám, k , például, hogy van egy csúcs lefedettség G méretű k ?és a döntési probléma:
Bemenet: egy G grafikon és egy k egész szám Kérdés: van-e lefedettség egy k méretű G csúcsonként ?A hozzá tartozó egész lineáris optimalizálási program :
minimalizálni | (minimalizálja a teljes költséget) | |||
mint például | mindenért | (minden éle be van fedve) | ||
mindenre . | (minden csúcs a takaróban van, vagy sem) |
Ennek a rendszernek a lineáris relaxációja a maximális kapcsolás problémájának optimalizálási programjának relaxációja .
A döntési probléma ezzel kapcsolatos optimalizálási probléma az, NP-teljes , és az egyik a Karp a 21 NP-teljes problémák . NP-keménységét a klikkprobléma csökkentése mutatja . A csúcsfedés problémáját gyakran használják a komplexitáselméletben annak bizonyítására, hogy más bonyolultabb problémák NP-hiányosak.
A probléma még mindig NP-teljes, ha korlátozzuk magunkat köbös grafikonok vagy síkgráfok a foka legfeljebb 3. páros gráfok, akkor polinomiális időben megoldható egy maximális kapcsolási algoritmust , alkalmazásával a tétel származó Kőnig .
A következő közelítő algoritmus legfeljebb kétszer akkora megoldást ad, mint az optimális: számítson ki egy maximális csatolást, és tegye az egyes csúcspárokat a megoldásba.
Ha feltételezzük, hogy P különbözik az NP-től , akkor a problémát nem lehet jobb arányban megközelíteni, mint 1,3606. Ha egyedi játékok sejtését feltételezzük , akkor a problémát nem lehet 2-nél jobb arányban megközelíteni .