Is there an algorithm for this variant of the dominating set problem?

88 Views Asked by At

I stumbled upon this interesting variant of the dominating set problem lately, and as I have not been able to find a consecrated name, I suppose it has not been thoroughly studied yet.

The formulation is simple : Given a graph $G = (V, E)$, find two dominating sets $V_1$ and $V_2$ such that $|V_1| + |V_2| + |V_1 \cap V_2|$ is minimal.

I am working with big graph, so NP-completeness will ruin my hopes of an exact solution, but would there be some work already done around this idea, that would help me find an approximate solution ?

1

There are 1 best solutions below

0
On

The problem is $NP$-hard.

We will show it by reduction from the minimum dominating set problem.

Let $G(V, E)$ be a graph and let $S$ be a dominating set. We construct $H(V_1\cup V_2, E_H)$ where $V_i = \{v_i \mid v\in V\}$ are two copies of the vertices of $G$, and $$E_H = \{u_1v_1, u_1v_2, u_2v_1, u_2v_2 \mid uv\in E\} \cup \{v_1v_2 \mid v\in V\}.$$

Clearly, $S_1 = \{v_1 \mid v\in S\}$ is still a minimum dominating set. Similarly, $S_2 = \{v_2 \mid v\in S\}$ is also a minimum dominating set, which is disjoint from $S_1$, so $S_1, S_2$ is clearly a minimum solution of your problem.