How easy is it to estimate a graph by observing only a few random cuts? Is there prior work related to this? I did google but could not find anything concrete.
Any help would be appreciated. Thanks.
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityHow easy is it to estimate a graph by observing only a few random cuts? Is there prior work related to this? I did google but could not find anything concrete.
Any help would be appreciated. Thanks.
Its not clear what you want to estimate, or what you mean by looking at a random cut. But it is hard to learn much about a graph by just observing the size of a random cut. This is because a random cut will always cut $m/2$ edges in expectation (where $m$ is the number of edges in the graph), independent of the structure of the graph. Of course, the entire graph can be thought of as a vector of length ${n \choose 2}$, so if you get to observe the -exact- size of that many random cuts, because they are likely to be linearly independent, you can reconstruct the graph. There's nothing special about cuts here: you're just observing the exact value of the dotproduct of $d$ linearly independent vectors with an unknown vector of length $d$, and this system of linear equations will have an exact solution.