<p>The definition:  </p>

<blockquote>
  <p>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.</p>
</blockquote>

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

<p><strong>My question is:</strong><br>
Is an algorithm known for building largest non-disturbing subset of a graph?</p>

<hr>

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

<p>But I doubt that, for example, the case <code>n</code>=16 would be brute-forcible.  </p>

CC BY-SA 4.0
2019-04-08T18:12:41.250Z
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.
Chao Xu
CC BY-SA 4.0
2019-04-10T11:51:47.203Z
@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 :-)
Egor   Skriptunoff
CC BY-SA 4.0
2019-04-11T21:43:13.723Z
@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.
isaacg
CC BY-SA 4.0
2019-04-11T22:03:49.250Z
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.
isaacg
CC BY-SA 4.0
2019-04-12T07:28:53.923Z
@isaacg - Wow!  Indeed!  It's possible to have 5 members on 3-dimensional cube.
Egor   Skriptunoff
CC BY-SA 4.0
2019-04-12T09:57:05.020Z
@isaacg you are indeed correct, I see why I was wrong.
Chao Xu
CC BY-SA 4.0
2019-04-19T02:47:56.430Z
For the $2n$ dimensional hypercube, the set would have at least $\binom{2n}{n}$ vertices - just take all the vertices with exactly $n$ ones. I think that by taking all the levels that contains an even number of $1$s, you get a good set of size $\geq 2^{2n-1}$.  Are you hoping to get something better?
Sariel Har-Peled
CC BY-SA 4.0
2019-04-19T19:49:44.663Z
@SarielHar-Peled - What would be the path between members (0,0,0,0) and (1,1,1,1) in your suggestion "all the levels that contains an even number of 1s"?
Egor Skriptunoff
CC BY-SA 4.0
2019-04-21T17:47:29.963Z
Good point. Here is different example. Take all the vertices that have the first bit as $1$. Clearly, there is a path between any two such vertices using only vertices that have $0$ in the first bit. The size of the set is $2^{n-1}$.
Sariel Har-Peled
CC BY-SA 4.0
2019-04-24T13:24:55.513Z
@SarielHar-Peled - Largest non-disturbing subset would probably contain `(1-o(1))*2^n` members.
Egor Skriptunoff
CC BY-SA 4.0
2019-04-25T15:30:59.603Z
I wonder if following works. Start with whole hypercube. At each iteration we build a random tunnel from (0,...,0) to (1,...1), by picking random permutation [d], and setting the bits to one according to this permutation.  Tunnel surface has size $L = \Theta(d^2)$, and the probability to be on its surface for a vertex (should be) $L/2^d$. Repeat tunneling $2^d/L*\log d$ times. A vertex w.h.p in $d$ is on the boundary of one of the tunnels, Take all the vertices on the boundary of the tunnels to be the non-distrubing set. One should be getting $2^d (1-O(\log d / d))$ vertices, I think....
Sariel Har-Peled
CC BY-SA 4.0
2019-04-25T15:42:42.393Z
The probabilities in the above are not quite right. The probability of a vertex to be on a surface of a tunnel is at least $cd^{3/2}/2^d$, for some constant $c$. The rest of the argument goes through I believe. To see why the probability arguemnt works, observe that the probability of two hypercube vertices to be on a tunnel is the same if they have same number of ones. A vertex is in layer $i$ if it has $i$ ones. Every vertex has at least $d/2$ neighbors in one of its neighboring layers, and the maximum size of a layer is $c2^d /\sqrt{d}$.
Sariel Har-Peled
CC BY-SA 4.0
2019-04-26T05:14:59.133Z
Here is quicky writeup:
http://sarielhp.org/misc/blog/19/04/26/non_disturbing.pdf
Sariel Har-Peled
CC BY-SA 4.0
2019-04-30T08:58:26.990Z
@SarielHar-Peled - Your approach (to build connected dominating set by uniting a huge amount of random "tunnels") is very unpractical.  I believe some bright idea could solve this problem more efficiently in both constructing time and connected dominating set's size.  Probably, some kind of "spiral" inside the hypercube...
Egor   Skriptunoff
CC BY-SA 4.0
2019-05-07T10:44:11.657Z
What values of d do you care about? It gets roughly 80% for d=28. Thats not bad. It would be nicer to have something significantly better, naturally.
Sariel Har-Peled
CC BY-SA 4.0
2019-05-07T11:08:23.923Z
@SarielHar-Peled - d=10..32, and I want to have small (1 KByte) and fast functions `dword = encode(member_no)`, `member_no = decode(dword)` and `get_path_between(dword1, dword2)`.  So, some bright idea is needed.  Trivial method gives 50%, but I want more.
Egor   Skriptunoff
<graph-algorithms>
Largest "non-disturbing" subset in a graph
Egor   Skriptunoff
# Largest "non-disturbing" subset in a graph

(Asked by: username_0 on 2019-04-08)

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.

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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 :-)  
> **username_2**: @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.  
> **username_2**: 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.  
> **username_0**: @username_2 - Wow!  Indeed!  It's possible to have 5 members on 3-dimensional cube.  
> **username_1**: @username_2 you are indeed correct, I see why I was wrong.  
> **username_3**: For the $2n$ dimensional hypercube, the set would have at least $\binom{2n}{n}$ vertices - just take all the vertices with exactly $n$ ones. I think that by taking all the levels that contains an even number of $1$s, you get a good set of size $\geq 2^{2n-1}$.  Are you hoping to get something better?  
> **username_4**: @SarielHar-Peled - What would be the path between members (0,0,0,0) and (1,1,1,1) in your suggestion "all the levels that contains an even number of 1s"?  
> **username_3**: Good point. Here is different example. Take all the vertices that have the first bit as $1$. Clearly, there is a path between any two such vertices using only vertices that have $0$ in the first bit. The size of the set is $2^{n-1}$.  
> **username_4**: @SarielHar-Peled - Largest non-disturbing subset would probably contain `(1-o(1))*2^n` members.  
> **username_3**: I wonder if following works. Start with whole hypercube. At each iteration we build a random tunnel from (0,...,0) to (1,...1), by picking random permutation [d], and setting the bits to one according to this permutation.  Tunnel surface has size $L = \Theta(d^2)$, and the probability to be on its surface for a vertex (should be) $L/2^d$. Repeat tunneling $2^d/L*\log d$ times. A vertex w.h.p in $d$ is on the boundary of one of the tunnels, Take all the vertices on the boundary of the tunnels to be the non-distrubing set. One should be getting $2^d (1-O(\log d / d))$ vertices, I think....  
> **username_3**: The probabilities in the above are not quite right. The probability of a vertex to be on a surface of a tunnel is at least $cd^{3/2}/2^d$, for some constant $c$. The rest of the argument goes through I believe. To see why the probability arguemnt works, observe that the probability of two hypercube vertices to be on a tunnel is the same if they have same number of ones. A vertex is in layer $i$ if it has $i$ ones. Every vertex has at least $d/2$ neighbors in one of its neighboring layers, and the maximum size of a layer is $c2^d /\sqrt{d}$.  
> **username_3**: Here is quicky writeup: http://sarielhp.org/misc/blog/19/04/26/non_disturbing.pdf  
> **username_0**: @SarielHar-Peled - Your approach (to build connected dominating set by uniting a huge amount of random "tunnels") is very unpractical.  I believe some bright idea could solve this problem more efficiently in both constructing time and connected dominating set's size.  Probably, some kind of "spiral" inside the hypercube...  
> **username_3**: What values of d do you care about? It gets roughly 80% for d=28. Thats not bad. It would be nicer to have something significantly better, naturally.  
> **username_0**: @SarielHar-Peled - d=10..32, and I want to have small (1 KByte) and fast functions `dword = encode(member_no)`, `member_no = decode(dword)` and `get_path_between(dword1, dword2)`.  So, some bright idea is needed.  Trivial method gives 50%, but I want more.  

---

## 0 answers

