The dominating set problem asks us to find a set of nodes $S$ such that for a graph $(V, E), \forall v \in V$, $v$ has a neighbor in $S$ or is in $S$ itself.
I'm looking for an algorithm which finds $S$ such that any $v$ has at least two neighbors in $S$ instead. It doesn't have to be optimal, as I'm using this algorithm in network design where a somewhat suboptimal solution is extra redundancy. Ideally it would be straightforward to implement, though—working in Rust if that changes anything—and performance matters given the size of these networks.
Intuitively, I want to say I could just use a prebuilt algorithm (like so) to calculate the dominating set, then eliminate all nodes which have two neighbors in the dominating set before running the calculation on the resultant graph. Then you'd just rinse and repeat if necessary. I'm not sure if there's a more performant solution out there, though, hence the question.
Edit: To add some characterisation to the graphs I'm looking at:
- These graphs are currently unit disk graphs. I expect this will change once topographic concerns are taken into line of sight calculations: for the time being all I care about is the distance between points. As such, I'd prefer a graph algorithm over a geometric one.
- The graphs are very dense, with max neighbors of around 20-30, and total edges of around $10N$ in bad cases. There are usually a few 'straggler' nodes that either have no or very few neighbors, but these can also be trimmed or processed in some other way.