2
$\begingroup$

A $k$-regular graph is one in which every vertex has degree k. A triangle-free graph is one in which any three vertices do not form a triangle. A dominating set $D$ of a graph $G$ is a set of vertices such that $\forall v \in (V(G)\setminus D)$, $v$ has a neighbour in $D$.

Is anything known about the hardness of deciding whether there is a dominating set of a given size in $k$-regular triangle-free graphs?($k\geq3$). It is already known that this problem is $NP-complete$ for triangle-free graphs.

$\endgroup$

1 Answer 1

1
$\begingroup$

We show that the minimum dominating set (MDS) problem is $\mathsf{NP}$-hard on $3$-regular triangle-free graphs. We show this by a reduction from the bipartite graphs of maximum degree $3$.

The MDS problem is $\mathsf{NP}$-hard on the bipartite graphs with maximum degree $3$ as shown in Theorem 6 of this paper. The reduction would imply that the problem is $\mathsf{NP}$-hard on $3$-regular triangle-free as well.

The following is the reduction:

Let $G$ be any bipartite graphs of maximum degree $3$. Note that $G$ is already triangle-free since it is bipartite. Moreover, we can assume that all the vertices in $G$ have degree either $2$ or $3$. Now, we create a $3$-regular triangle-free $G'$ as follows. For every vertex $v \in G$ of degree two, we define a gadget $G_{cv}$ shown below:

enter image description here

We connect vertex $v$ to gadget $G_{cv}$ with edge $(v,v_a)$. Let the new graph be $G'$. Note that $G'$ is $3$-regular triangle-free graph by construction. Now, the following claim easily follows:

Claim: $G$ has a dominating set of size $k$ if and only if $G'$ has a dominating set of size $k+2|V_t|$, where $|V_t|$ are the number of vertices in $G$ with degree two.

Proof: ($\to$) Suppose $G$ has a dominating set of size $k$. For every gadget $G_{cv}$, we add the vertices $v_b$ and $v_c$ to the dominating set. The vertices $v_b$ and $v_c$ dominates all the vertices in a gadget. Thus, $G'$ has a dominating set of size $k + 2|V_t|$.

($\gets$) Suppose $G'$ has a dominating set of size $k + 2|V_t|$. It is easy to see that to dominate all vertices in a gadget, we require at least two vertices. Moreover, if $v_a$ is included in the dominating set then we still require two more vertices to dominate all the vertices in a gadget. Therefore, if any gadget has vertex $v_a$ included in the dominating set, we can replace vertex $v_a$ with $v$ in the dominating set. Moreover, the other vertices of the gadget chosen in the dominating set, we replace them with $v_b$ and $v_c$. Thus, $G'$ has a dominating set of size at most $k + 2|V_t|$ such that it does not include any vertex $v_a$ and each gadget contains exactly two vertices. Thus, the vertices in the dominating set that comes from $G$ have size at most $k$ and they dominate all the vertices of $G$. Thus, $G$ has a dominating set of size $k$.

$\endgroup$
3
  • $\begingroup$ Can you explain why we can assume all vertices in $G$ have degree $2$ or $3$? $\endgroup$ Jul 3, 2023 at 4:33
  • 1
    $\begingroup$ @AnkitGayen Firstly, the hard instances that I used already had vertices with degrees only $2$ or $3$. Please check the paper. Secondly, for degree $1$ vertices you can attach two gadgets with it. Similar proof holds then. $\endgroup$ Jul 3, 2023 at 4:47
  • $\begingroup$ Yup! two gadgets does the job. I somehow thought the same reasoning will not apply for two gadgets. $\endgroup$ Jul 3, 2023 at 5:03

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.