patternMinor
Least number of guesses needed to determine all unknown subsets of a set
Viewed 0 times
guessesnumberneededallunknownsubsetsdetermineleastset
Problem
Say I have a set $\mathbb{S}=\{1,2,...,n\}$. I have an adversary who breaks up $\mathbb{S}$ into $k$ unknown and disjoint subsets. Denote this new set $\mathbb{A}$. I can guess any combination $s$ and my adversary has to tell me if $s$ is itself a subset of any element in $\mathbb{A}$.
For example, if $n=4$, a valid $\mathbb{A}$ might be $\{ \{2\}, \{1,3,4\}\}$. All "true" guesses are $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{3,4\}$, $\{1,4\}$, $\{1,3,4\}$.
What's the fastest algorithm and the upper bound on number of guesses I need to make to fully reverse engineer $\mathbb{A}$?
Obviously the brute force algorithm takes $^nC_1 + ^nC_2 + ... + ^nC_n $ guesses for every possible subset.
But I think I only need to test all possible subsets of size 2 i.e. exactly $^nC_2$ guesses?
Then, I can represent each of the correct guesses of size 2 as an undirected edge in a graph. Every member of $\mathbb{A}$ of size 3 or greater should form a simple cycle in this graph. So I just need to DFS on every node in this graph, removing the longest cycle detected from the graph, and repeat for all remaining nodes until only lone edges (subsets of size 2) or unconnected vertices (subsets of size 1) remain.
This graph should have $n$ vertices and at most $^nC_2$ edges. So the fastest algorithm has a time complexity of $\mathbb{o}(n^{2}\cdot{}^{n}C_{2})$. Is there an approach with fewer guesses or a faster graph algorithm?
P.S.: In case anyone's interested about the context: One example use case is if $n$ known services are hosted on unknown $k$ servers with unknown grouping, and you have some way to overload any subset of services to mount a denial attack on a server. The problem becomes if you can profile the servers with the least number of queries. I came across a similar scenario and thought this was a pretty interesting problem with no literature on.
For example, if $n=4$, a valid $\mathbb{A}$ might be $\{ \{2\}, \{1,3,4\}\}$. All "true" guesses are $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{3,4\}$, $\{1,4\}$, $\{1,3,4\}$.
What's the fastest algorithm and the upper bound on number of guesses I need to make to fully reverse engineer $\mathbb{A}$?
Obviously the brute force algorithm takes $^nC_1 + ^nC_2 + ... + ^nC_n $ guesses for every possible subset.
But I think I only need to test all possible subsets of size 2 i.e. exactly $^nC_2$ guesses?
Then, I can represent each of the correct guesses of size 2 as an undirected edge in a graph. Every member of $\mathbb{A}$ of size 3 or greater should form a simple cycle in this graph. So I just need to DFS on every node in this graph, removing the longest cycle detected from the graph, and repeat for all remaining nodes until only lone edges (subsets of size 2) or unconnected vertices (subsets of size 1) remain.
This graph should have $n$ vertices and at most $^nC_2$ edges. So the fastest algorithm has a time complexity of $\mathbb{o}(n^{2}\cdot{}^{n}C_{2})$. Is there an approach with fewer guesses or a faster graph algorithm?
P.S.: In case anyone's interested about the context: One example use case is if $n$ known services are hosted on unknown $k$ servers with unknown grouping, and you have some way to overload any subset of services to mount a denial attack on a server. The problem becomes if you can profile the servers with the least number of queries. I came across a similar scenario and thought this was a pretty interesting problem with no literature on.
Solution
A simple algorithm may be:
Loop on:
In worst case, this is O(kn) as you won't do this loop more than k times. In average case, I am not sure...
Loop on:
- take the next unassigned element Ei and create a new set Si assigning Ei to it.
- loop on all unassigned elements Ej, testing the pair {Ei,Ej}. If it is true, assign j it to Si.
In worst case, this is O(kn) as you won't do this loop more than k times. In average case, I am not sure...
Context
StackExchange Computer Science Q#101820, answer score: 2
Revisions (0)
No revisions yet.