Improved Approximations for Minimim Independent Dominating Set in Bounded
Degree Graphs
We consider the problem of finding an independent dominating set of
minimum cardinality in bounded degree and regular graphs.
We first give
an approximate heuristic for MIDS in at most
cubic graphs, based on greedy and local search
techniques.
Then, we consider graphs of bounded degree $B$ and $B$-regular
graphs, for $B \ge 4$.
In particular, the greedy phase proposed for at most cubic graphs is
extended to any $B$ and iteratively repeated
until the degree of the remaining graph is greater than 3.
Finally, a local search phase is executed on the remaining at most
cubic graph.
Our algorithms achieve approximation ratios:
- 1.923 for cubic graphs;
- 2 for at most cubic and 4-regular graphs;
- ${{(B^2-2B+2)(B+1)} \over {B^2+1}}$ for B-regular graphs, $B \ge 5$;
- ${{(B^2-B+1)(B+1)} \over {B^2+1}}$ for graphs of bounded degree $B \ge 4$.
Conference
Version
Springer Link