6
$\begingroup$

The definition:

The subset of vertices in a graph is called "non-disturbing" if any two vertices from this subset could be connected by a path not passing through other vertices of this subset.

Informally speaking, any two members must have a way to speak to each other without disturbing other members.
And we want to put as many members in a graph as we could.

My question is:
Is an algorithm known for building largest non-disturbing subset of a graph?


I'm especially interested in solving this task for n-dimensional hypercube (having 2^n vertices).
n is from 1 to 64.
By paper-and-pencil approach I could find solutions for small n:
for n=1 we could have 2 members,
for n=2 we could have 3 members,
for n=3 we could have 5 members,
for n=4 we could have 10 members.

But I doubt that, for example, the case n=16 would be brute-forcible.

$\endgroup$
  • $\begingroup$ If you require the path to contain at least 2 edges (so in the non-disturbing subset, the path have to leave the subset then come back), then the problem is the same as finding the minimum connected dominating set. Likely, your problem is also NP-hard. $\endgroup$ – Chao Xu Apr 8 at 18:12
  • $\begingroup$ @ChaoXu - Thank you for providing correct terminology! Now I know that (for almost all graphs) my question is equivalent to finding spanning tree having maximal number of leaves. Googling becomes much easier :-) $\endgroup$ – Egor Skriptunoff Apr 10 at 11:51
  • 1
    $\begingroup$ @ChaoXu The connected dominating set characterization seems wrong to me. Consider two opposite vertices of a square. The set is non-disturbing, but the complement is not connected. $\endgroup$ – isaacg Apr 11 at 21:43
  • 1
    $\begingroup$ For the 3-dimensional cube, there is a non-disturbing subset containing 5 vertices. If we label the vertices 000, 001, ..., 111 where there is an edge between each pair of vertices that have hamming distance 1, then the subset 001, 010, 110, 100, 101 is non-disturbing. This non-disturbing subset has a disconnected complement. $\endgroup$ – isaacg Apr 11 at 22:03
  • $\begingroup$ @isaacg - Wow! Indeed! It's possible to have 5 members on 3-dimensional cube. $\endgroup$ – Egor Skriptunoff Apr 12 at 7:28

Your Answer

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

Browse other questions tagged or ask your own question.