1
$\begingroup$

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$. enter image description here

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ I'd start pondering distance and cuts. $\endgroup$
    – greybeard
    Commented Mar 12, 2021 at 7:09
  • $\begingroup$ @greybeard Could you elaborate a bit more? $\endgroup$
    – tobyrick123
    Commented Mar 12, 2021 at 7:44
  • $\begingroup$ Out of my turf here, but sure I can: needing all nodes covered exactly once, you need nodes at a pairwise distance of three. Within a single connected component of $G$, it may lead to a useful heuristic to consider the/a diameter. Pondering cuts got me nowhere. $\endgroup$
    – greybeard
    Commented Mar 12, 2021 at 8:39

2 Answers 2

Reset to default
0
$\begingroup$

This is an exact cover problem, so you could use standard algorithms for exact cover; or you could use a SAT solver.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$

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.