I detta papper studerar vi NP-komplett problemet med att hitta små k-dominerande uppsättningar i allmänna grafer, som tillåter k - 1 noder att misslyckas och fortfarande dominera grafen. Det klassiska minimala dominerande set-problemet är ett specialfall med k = 1. Vi visar att tillvägagångssättet att ha åtminstone k dominerande noder i närheten av varje nod inte är optimalt. För varje α > 1 kan den ge lösningar k α gånger större än en minsta k-dominerande uppsättning. Vi studerar också lägre gränser för möjliga approximationsförhållanden. Vi visar att det är NP-hårdt att approximera det minsta k-dominerande set problemet med en faktor som är bättre än (0.2267/k) ln(n/k). Dessutom, ett resultat för speciella ändliga summor gör att vi kan använda en girig strategi för k-domination med ett approximationsförhållande på ln( ska + k) + 1 < ln( ska) + 1.7, med  ska vara den maximala nod-grad. Vi uppnår också en approximation av ln(n) + 1.7 för h-steg k-domination, där noder inte behöver vara direkta grannar av dominerande noder, men kan vara h steg bort.
Författaren i REF har undersökt problemet med att hitta små kdominerande uppsättningar i allmänna grafer.
Approximating Fault-Tolerant Domination in General Graphs
{'venue': 'ANALCO', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}