A binary search problem on graphs

AbstractLet G=(V,E) be a graph and ē∈E an unknown edge. In order to find ē we choose a sequence of test sets W⊂V, where after every test we are told whether both vertices incident to ē are in W, or not. For c(G), the minimum number of tests required, the inequality c(G)≥⌈log2|E|⌉ clearly holds (information theoretic lower bound). It was conjectured by Chang and Hwang that for a bipartite graph G this lower bound is always achieved. Here we show c(G)≤⌈log2|E|⌉+1 for bipartite graphs and c(G)≤⌈log2+|E|⌉+3 for arbitrary graphs