Monday, 13 August 2007

algorithms - Reconstructing a graph given access to its cut function

Given an unweighted graph G=(V,E), let the cut function on this graph be defined to be:
C:2VrightarrowmathbbZ such that:
C(S)=|(u,v)inE:uinSwedgevnotinS|
Suppose you have the ability to query C, but otherwise have no knowledge of the edge set E. Is it possible to reconstruct G by making only polynomial (in |V|) many queries to the cut function?

No comments:

Post a Comment