2
$\begingroup$

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.
$\endgroup$
7
  • $\begingroup$ What do you have so far? The problem is NP-complete, so you won't find very efficient optimal algorithms. You can try a simple greedy algorithm where you first color a dominating set and then try to make it a 2-DS. $\endgroup$
    – Pål GD
    Commented Oct 10, 2023 at 22:00
  • $\begingroup$ Is there anything you can tell us about the input graphs? $\endgroup$
    – Pål GD
    Commented Oct 10, 2023 at 22:01
  • $\begingroup$ The input graphs represent the positions of network nodes in realspace, with edges connecting nodes that are within a certain distance and line of sight of each other. $\endgroup$
    – Ada Song
    Commented Oct 11, 2023 at 5:24
  • $\begingroup$ As per your problem definition, in a feasible solution, if a vertex $v$ is in dominating set; does it must have a neighbor in the dominating set? $\endgroup$ Commented Oct 11, 2023 at 7:41
  • $\begingroup$ Is the graph sparse? How many edges do you expect an $n$-vertex graph to have? For example, planar graphs have at most $5n$ edges. $\endgroup$
    – Pål GD
    Commented Oct 11, 2023 at 7:52

1 Answer 1

2
$\begingroup$

In Parameterized Complexity for Domination Problems on Degenerate Graphs, Golovach and Villanger give an algorithm for the Dominating Threshold et problem, which is defined as follows:

Dominating Threshold Set
Input: A graph $G$, and two integers $k$ and $r$
Question: Does there exist a set $S$ of at most $k$ vertices such that for every vertex $v \in V(G)$, $|N[v] \cap S| \geq r$, i.e., every vertex has at least $r$ neighbors in $S$ (including themselves), i.e., dominators need only have one additional neighbor in $S$.

They give an algorithm running in time $O(k^{O(dkr)} \cdot n^{O(1)})$, where $d$ is the degeneracy of the graph.

The problem is often called Double Domination in the literature.

Your problem is also sometimes referred to as a sigma-rho-domination problem, with $\sigma \geq 2$ and $\rho \geq 0$. This is simply saying that every vertex needs two neighbors in $S$ ($\sigma$) and however many they wish ($\rho$) in $V \setminus S$ (see Telle, Nord. J. Comput., 1994).

It is also known as the $[2,k]$-domination number (see Chellali et al., Discrete Applied Mathematics, Volume 161, Issue 18, December 2013, Pages 2885-2893).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.