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.

Improve this question
$\endgroup$
16
  • $\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, 2019 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, 2019 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, 2019 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, 2019 at 22:03
  • $\begingroup$ @isaacg - Wow! Indeed! It's possible to have 5 members on 3-dimensional cube. $\endgroup$
    – Egor Skriptunoff
    Apr 12, 2019 at 7:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.