Graafiteoriassa graafin G = ( V , E ) reunadominoiva joukko (tai reunadominoiva joukko ) on D ⊆ E :n osajoukko siten, että mikä tahansa reuna, joka ei ole D :ssä, on vähintään yhden D :n reunan vieressä . Kuvissa (a)–(d) on esimerkkejä hallitsevista reunajoukoista (punaiset reunat).
Pienin hallitseva reunajoukko on pienin hallitseva reunajoukko. Kuvat (a) ja (b) esittävät esimerkkejä pienimmistä hallitsevista reunajoukoista (voidaan tarkistaa, ettei annetulle graafille ole hallitsevaa kahden reunan joukkoa).
Graafin G hallitseva reunajoukko on viivagraafin L ( G ) hallitseva joukko ja päinvastoin.
Mikä tahansa maksimaalinen yhteensopivuus on aina reunaa hallitseva joukko. Kuviot (b) ja (d) esittävät esimerkkejä maksimaalisista vastaavuuksista.
Lisäksi pienimmän hallitsevan reunajoukon koko on yhtä suuri kuin pienimmän enimmäissovituksen koko . Pienin maksimaalinen yhteensopivuus on pienin hallitseva reunajoukko. Kuvassa (b) on esimerkki pienimmästä maksimivastaavuudesta. Pienin hallitseva reunajoukko ei välttämättä ole pienin maksimisovitus, kuten kuva (a) osoittaa. Kuitenkin, kun otetaan huomioon pienin hallitseva reunajoukko D , on helppo löytää pienin maksimiyhteensopivuus | D | reunat (katso esimerkiksi Michalis Giannakakisin ja Fanica Gavrilan artikkeli [1] ).
Sen määrittäminen, onko tietylle graafille tietyn kokoinen hallitseva reunajoukko, on NP-täydellinen (siis pienimmän hallitsevan reunajoukon löytäminen on NP-kova ). Michalis Giannakakis ja Fanica Gavril [1] osoittivat, että ongelma on NP-täydellinen jopa kaksiosaiselle graafille , jonka huippupisteaste on enintään 3, ja myös tasograafille , jonka huippupisteaste on enintään 3.
On olemassa yksinkertainen polynomiajan approksimaatioalgoritmi , jonka approksimaatiokerroin on 2 - löydämme maksimiyhteensopivuuden. Suurin vastaavuus on hallitseva reunojen joukko. Lisäksi maksimisovitus M voi olla kaksinkertainen pienimmän maksimisovituksen kokoon ja pienin maksimisovitus on samankokoinen kuin pienin hallitseva reunajoukko.
On myös mahdollista arvioida kertoimella 2 tehtävän reunapainotettua versiota, mutta algoritmi on paljon monimutkaisempi [2] .
Hlebikov ja Khlebikova [3] osoittivat, että haku parhaalla kertoimella (7/6) on NP-kova ongelma.