Algorithm for the independent domination number

422 Views Asked by At

A dominating set for a graph $G = (V, E)$ is a subset $D$ of $V$ such that every vertex not in $D$ is adjacent to at least one member of $D$. The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$.

The independent domination number $i(G)$ of a graph $G$ is the size of the smallest independent dominating set (or, equivalently, the size of the smallest maximal independent set).

I need a code or algorithm for the independent domination number.

can you help me?

1

There are 1 best solutions below

0
On

Sadly, this problem is NP-hard, hence there is no known polynomial time algorithm for this problem (and probably there is no way to find one such algorithm). Worse yet, as stated in that link, unless P=NP, no polynomial-time approximation algorithm for this problem can guarantee to find an independent dominating set with size within a factor of $K$ of the optimal, where $K$ is any fixed constant $>1$.

You may find polynomial time approximate algorithms if you are working in some especial types of graphs. Here they show a (random) polynomial time approximation algorithm for this problem in some special graphs. They also discuss aproximating algortihms for some other types of graphs.