<p>There are good reasons to expect that there is no polynomial time reduction that takes as input a graph $G$ and outputs a graph $\hat{G}$ such that $\omega(\hat{G})$ depends <em>only</em> on $\gamma(G)$. In particular the Clique problem is complete for $W[1]$ while Dominating Set is complete for $W[2]$, see the <a href="http://en.wikipedia.org/wiki/Parameterized_complexity">Wikipedia page for Parameterized Complexity</a>. A reduction from Dominating Set to Clique where the size of the clique only depends on the size of the dominating set would imply that $W[2] = W[1]$, which is considered unlikely. </p>

<p>On the other hand it is not too hard to make a reduction where $\omega(\hat{G})$  depends only on $\gamma(G)$ and $|V(G)|$. For every edge $uv \in G$ make two vertices $[u,v]$ and $[v,u]$ in $\hat{G}$. For two vertices $[u_1,v_1]$ and $[u_2,v_2]$ of $\hat{G}$ we put an edge between them if $u_1 \neq u_2$, $u_1 \neq v_2$ and $u_2 \neq v_1$. We claim that $\omega(\hat{G}) = |V(G)| - \gamma(G)$. </p>

<p>The intuition is that the vertex $[u,v]$ is interpreted as ``$u$ is dominated by $v$''. Then each vertex of $G$ not in the dominating set should choose exactly one vertex in the dominating set to dominate it. Someone who has chosen to be dominated may then not be a dominator.</p>

<p>Consider a dominating set $S$ in $G$. We make a set $\hat{S}$ as follows: for each vertex $u \notin S$, pick an arbitrary neighbor $v \in S$ of $u$ and add $[u,v]$ to $\hat{S}$. Clearly $\hat{S}$ is a clique of size $|V(G)| - |S|$.</p>

<p>On the other hand consider a clique $\hat{S}$ in $\hat{G}$. Let $S$ be the set of vertices $u$ in $V(G)$ such that there does not exist a $v \in V(G)$ such that $[u,v] \in \hat{S}$. Observe now that $|S| \geq |V(G)| - |\hat{S}|$, since each element of $\hat{S}$ rules out at most one vertex of $G$. Consider a vertex $u \notin S$. There must be some vertex $v \in V(G)$ such that $[u,v] \in \hat{S}$. We know that $uv \in E(G)$, it remains to show that $v \in S$. Suppose not, then there must be some $v' \in V(G)$ such that $[v,v'] \in \hat{S}$. But $[u,v]$ and $[v,v']$ are non-adjacent in $\hat{G}$, contradicting that $\hat{S}$ is a clique. So $S$ is a dominating set.</p>

CC BY-SA 3.0
2014-12-03T22:28:12.733Z
2014-12-03T22:28:12.733Z
daniello
<p>Let $G$ be a simple undirected graph. Recall that $S \subseteq V(G)$ is a <em>dominating set</em> of $G$ if every vertex of $v \in V(G) \setminus S$ has a neighbour in $S.$</p>

<p>It is well known that it is NP complete to determine the  minimal dominating set of $G$ and that is usually done via the vertex-cover problem.</p>

<p>As the title suggests, I would like to reduce dominating set to the max clique problem. One can of course use the standard reductions to do so, but I would like to find a as "small as possible" reduction. That is I would like to be able to reduce a graph $G$ to a graph $\widehat{G}$ that is as small as possible and so that $\gamma(G)$ can be efficiently determined from $\omega(\widehat{G}).$ Here $\gamma$ and $\omega$ are the size of the dominating set and clique number respectively.</p>

<p>Can someone suggest such a reduction?</p>

CC BY-SA 3.0
2014-12-04T07:54:24.830Z
This is related DS to vertex cover:  http://cstheory.stackexchange.com/questions/25376/is-there-simple-reduction-dominating-set-to-vertex-cover?noredirect=1#comment66221_25376
joro
<graph-theory><reductions><np><clique>
Minimal polynomial reduction of dominating set to max clique
Jernej
# Minimal polynomial reduction of dominating set to max clique

(Asked by: username_0 on 2014-11-20)

Let $G$ be a simple undirected graph. Recall that $S \subseteq V(G)$ is a *dominating set* of $G$ if every vertex of $v \in V(G) \setminus S$ has a neighbour in $S.$

It is well known that it is NP complete to determine the minimal dominating set of $G$ and that is usually done via the vertex-cover problem.

As the title suggests, I would like to reduce dominating set to the max clique problem. One can of course use the standard reductions to do so, but I would like to find a as "small as possible" reduction. That is I would like to be able to reduce a graph $G$ to a graph $\widehat{G}$ that is as small as possible and so that $\gamma(G)$ can be efficiently determined from $\omega(\widehat{G}).$ Here $\gamma$ and $\omega$ are the size of the dominating set and clique number respectively.

Can someone suggest such a reduction?

**Tags:** graph-theory, reductions, np, clique

> **Comments:**
> **username_1**: This is related DS to vertex cover:  http://cstheory.stackexchange.com/questions/25376/is-there-simple-reduction-dominating-set-to-vertex-cover?noredirect=1#comment66221_25376  

---

## 1 answers

### Answer by username_2 on 2014-12-03. Score: 5 | Accepted answer

There are good reasons to expect that there is no polynomial time reduction that takes as input a graph $G$ and outputs a graph $\hat{G}$ such that $\omega(\hat{G})$ depends *only* on $\gamma(G)$. In particular the Clique problem is complete for $W[1]$ while Dominating Set is complete for $W[2]$, see the [Wikipedia page for Parameterized Complexity](http://en.wikipedia.org/wiki/Parameterized_complexity). A reduction from Dominating Set to Clique where the size of the clique only depends on the size of the dominating set would imply that $W[2] = W[1]$, which is considered unlikely.

On the other hand it is not too hard to make a reduction where $\omega(\hat{G})$ depends only on $\gamma(G)$ and $|V(G)|$. For every edge $uv \in G$ make two vertices $[u,v]$ and $[v,u]$ in $\hat{G}$. For two vertices $[u\_1,v\_1]$ and $[u\_2,v\_2]$ of $\hat{G}$ we put an edge between them if $u\_1 \neq u\_2$, $u\_1 \neq v\_2$ and $u\_2 \neq v\_1$. We claim that $\omega(\hat{G}) = |V(G)| - \gamma(G)$.

The intuition is that the vertex $[u,v]$ is interpreted as ``$u$ is dominated by $v$''. Then each vertex of $G$ not in the dominating set should choose exactly one vertex in the dominating set to dominate it. Someone who has chosen to be dominated may then not be a dominator.

Consider a dominating set $S$ in $G$. We make a set $\hat{S}$ as follows: for each vertex $u \notin S$, pick an arbitrary neighbor $v \in S$ of $u$ and add $[u,v]$ to $\hat{S}$. Clearly $\hat{S}$ is a clique of size $|V(G)| - |S|$.

On the other hand consider a clique $\hat{S}$ in $\hat{G}$. Let $S$ be the set of vertices $u$ in $V(G)$ such that there does not exist a $v \in V(G)$ such that $[u,v] \in \hat{S}$. Observe now that $|S| \geq |V(G)| - |\hat{S}|$, since each element of $\hat{S}$ rules out at most one vertex of $G$. Consider a vertex $u \notin S$. There must be some vertex $v \in V(G)$ such that $[u,v] \in \hat{S}$. We know that $uv \in E(G)$, it remains to show that $v \in S$. Suppose not, then there must be some $v' \in V(G)$ such that $[v,v'] \in \hat{S}$. But $[u,v]$ and $[v,v']$ are non-adjacent in $\hat{G}$, contradicting that $\hat{S}$ is a clique. So $S$ is a dominating set.


---

