Vuonna Graafiteoria ja teoreettisen tietojenkäsittelyopin , The ongelma vähimmäis- kattavuus kärkipisteet (tai ongelma pienimmän poikittaisen , Vertex Cover Englanti) on klassinen algoritminen ongelma. Se koostuu kaaviosta, joka löytää vähimmäispistejoukon, joka peittää kaikki reunat.
Päätösongelmalla liittyy tähän optimointi ongelma on NP-täydellinen , ja se on yksi ja Karp n 21 NP-täydellisiä ongelmia . Sitä käytetään usein monimutkaisuusteoriassa todistamaan, että muut monimutkaisemmat ongelmat ovat NP-täydellisiä.
Kärki tai poikittainen kattavuus graafin G on joukko C solmuja siten, että kukin reuna G = ( V , E ) on tapaus ainakin yksi kärki C , eli osajoukon pisteiden siten, että kutakin reunaa ja yksi on tai . Peittääkö mainittu sarja C G: n reunat . Seuraava kuva esittää esimerkkejä kahden kuvaajan piikkien peittävyydestä (joukko C muodostuu punaisista kärjistä).
Vähintään kärki kansi on cover minimikoko huiput. Seuraava kuva esittää esimerkkejä piikkien vähimmäispeitteistä samoissa kaavioissa kuin yllä.
Jos pistejoukko on poikittainen, sen komplementti on vakaa (tai riippumaton joukko ). Joten kuvaajalla, jolla on n kärkeä, on poikkisuunnassa koko k vain ja vain, jos sillä on vakaa koko n - k . Johdamme välittömästi seuraavan tuloksen:
Gallai 's lause (1959) - Joka kaavio , α (G) + τ (G) = n.
jossa α (G) tarkoittaa maksimivakaajan kokoa , τ (G) tarkoittaa pienimmän poikittaisen kokoa ja .
Optimointiongelma, jota kutsutaan minimipisteiden kattavuusongelmaksi, on seuraava:
Syöttö: graafi G Kysymys: mikä on pienin kokonaisluku k , niin että G: n kärkipisteen koko on k- kokoinen ?ja päätösongelma:
Syöttö: graafi G ja kokonaisluku k Kysymys: onko k-k : n kattavuus G : n kärkeä kohti ?Liittyvä kokonaisluku lineaarinen optimointi -ohjelma on:
minimoida | (minimoi kokonaiskustannukset) | |||
kuten | kaikesta | (kaikki reunat on peitetty) | ||
kaikesta . | (jokainen kärki on huopassa vai ei) |
Tämän järjestelmän lineaarinen relaksaatio on kaksinkertainen optimointiohjelman relaksointiin maksimaalisen kytkemisen ongelmaan .
Päätösongelmalla liittyy tähän optimointi ongelma on NP-täydellinen , ja se on yksi ja Karp n 21 NP-täydellisiä ongelmia . Sen NP-kovuus osoitetaan vähentämällä klikki- ongelmaa siihen. Kärkipisteiden kattavuusongelmaa käytetään usein kompleksiteoriassa sen osoittamiseksi, että muut monimutkaisemmat ongelmat ovat NP-täydellisiä.
Ongelma on edelleen NP-täydellinen, jos rajoittaa itse kuutiometriä kaavioita tai tasomainen kaavioita on aste on korkeintaan 3. kaksiosainen kaavioita, se on ratkaistu polynomiajassa kanssa enintään kytkemällä algoritmi , soveltamalla lauseeseensa Kőnig .
Seuraavat approksimaatio algoritmi antaa ratkaisu korkeintaan kaksi kertaa niin suuri kuin optimaalinen: laskea enintään kytkentä ja laittaa kunkin parin pisteiden liuoksessa.
Jos oletetaan, että P on erilainen kuin NP , ongelmaa ei voida lähestyä paremmalla suhteella kuin 1,3606. Jos oletetaan ainutlaatuisten pelien arvelu , ongelmaa ei voida lähestyä paremmalla suhteella kuin 2.