Subset of nodes such that all nodes of a graph are adjacent We have been given a graph $G$, we need to find a subset of nodes $S$ such that each node of the graph is in $S$ or is adjacent to a node from $S$. Additionally, the elements of the subset $S$ should not be adjacent to each other neither should they share a common neighbour node.
This is an example of the given problem:
In the given graph, the subset $S = $ {2, 4} is a valid solution as $3$ and $5$ are adjacent to 2 while $1$ and $6$ are adjacent to $4$. Further, $2$ and $4$ are not adjacent neither do they share a common neighbour.
The subset $S = $ {4, 5} is NOT valid as $4$ and $5$ have a common neighbour $1$.

I have been looking for an efficient way to do this; my attempt at an algorithm gives an exponential time complexity.
Any hints are appreciated, thanks in advance.
In the literature, such a subset is called a perfect code.
As it is NP-complete to determine if a given graph has a perfect code, even on some very restricted inputs, your exponential-time algorithm is probably about as good as it gets.