I grafteorin är den kantdominerande mängden (eller kantdominerande mängd ) av en graf G = ( V , E ) en delmängd av D ⊆ E så att vilken kant som helst som inte är i D ligger intill åtminstone en kant i D . Figurerna (a)–(d) visar exempel på dominerande kantuppsättningar (röda kanter).
Den minsta dominerande kantuppsättningen är den minsta dominerande kantuppsättningen. Figurerna (a) och (b) visar exempel på de minsta dominerande kantuppsättningarna (man kan kontrollera att det inte finns någon dominerande uppsättning av två kanter för en given graf).
Den dominerande uppsättningen av kanter för grafen G är den dominerande uppsättningen av linjegrafen L ( G ), och vice versa.
Varje maximal matchning är alltid en kantdominerande uppsättning. Figurerna (b) och (d) visar exempel på maximal matchning.
Dessutom är storleken på den minsta dominerande kantuppsättningen lika med storleken på den minsta maximala matchningen . Den minsta maximala matchningen är den minsta dominerande uppsättningen av kanter. Figur (b) ger ett exempel på den minsta maximala matchningen. Den minsta dominerande kantuppsättningen är inte nödvändigtvis den minsta maximala matchningen, som figur (a) illustrerar. Men givet den minsta dominerande kantuppsättningen D är det lätt att hitta den minsta maximala matchningen med | D | kanter (se t.ex. artikeln av Michalis Giannakakis och Fanica Gavrila [1] ).
Att avgöra om det finns en dominerande kantuppsättning av en given storlek för en given graf är NP-komplett (därav att hitta den minsta dominerande kantuppsättningen är NP-hård ). Michalis Giannakakis och Fanica Gavril [1] visade att problemet är NP-komplett även för en tvådelad graf med en maximal vertexgrad på 3, och även för en plan graf med en maximal vertexgrad på 3.
Det finns en enkel polynomtidsapproximationsalgoritm med en approximationsfaktor på 2 - vi hittar vilken maximal matchning som helst. Den maximala matchningen är den dominerande uppsättningen av kanter. Dessutom kan den maximala matchningen M vara dubbelt så stor som den minsta maximala matchningen, och den minsta maximala matchningen har samma storlek som den minsta dominerande kantuppsättningen.
Det är också möjligt att approximera med en faktor 2 den kantviktade versionen av problemet, men algoritmen är mycket mer komplicerad [2] .
Khlebikov och Khlebikova [3] visade att sökning med bästa koefficient (7/6) är ett NP-hårt problem.