5
$\begingroup$

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.

Improve this question
$\endgroup$
17
  • 2
    $\begingroup$ "Every member of $\mathbb{A}$ of size 3 or greater should form a simple cycle in this graph" should be "Every member of $\mathbb{A}$ of size 3 or greater forms a connected component that is a complete graph. $\endgroup$
    – John L.
    Commented Dec 20, 2018 at 6:24
  • 2
    $\begingroup$ There is a simple algorithm using $O(kn)$ queries. Find the part of 1 using $n-1$ queries. Then pick an element not in the part of 1, find its part, and so on. $\endgroup$
    – Yuval Filmus
    Commented Dec 20, 2018 at 6:32
  • 3
    $\begingroup$ There’s a simple $\Omega(n\log n)$ information-theoretic lower bound when $k$ is not fixed (or when $k=n/2$), by counting the number of possible partitions. $\endgroup$
    – Yuval Filmus
    Commented Dec 20, 2018 at 10:15
  • 2
    $\begingroup$ Here's an easy proof of $\Theta(n^2)$ worst-case time when $k$ is not fixed, or is $\Theta(n)$: Suppose $k=n-1$. Then there is exactly one edge in the graph. If you test fewer than $n(n-1)/2-1$ unordered vertex pairs, then there are at least two, say $ab$ and $cd$, that you haven't tested. The input in which $ab$ is the only subset, and the input in which $cd$ is the only subset, therefore cannot be distinguished by any such algorithm. $\endgroup$
    – j_random_hacker
    Commented Dec 20, 2018 at 10:50
  • 2
    $\begingroup$ @j_random_hacker In your example they still can't do better because testing anything bigger than a pair would result in false. $\endgroup$
    – orlp
    Commented Dec 20, 2018 at 11:18

1 Answer 1

Reset to default
2
$\begingroup$

A simple algorithm may be:

Loop on:

  1. take the next unassigned element Ei and create a new set Si assigning Ei to it.
  2. 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...

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.