7
$\begingroup$

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?

$\endgroup$

migrated from cs.stackexchange.com Dec 3 '14 at 21:20

This question came from our site for students, researchers and practitioners of computer science.

5
$\begingroup$

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. 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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