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.

$\endgroup$
3
  • $\begingroup$ I'd start pondering distance and cuts. $\endgroup$
    – greybeard
    Mar 12 at 7:09
  • $\begingroup$ @greybeard Could you elaborate a bit more? $\endgroup$ Mar 12 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
    Mar 12 at 8:39
0
$\begingroup$

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

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

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