Ph.D Student Mazzawi Hanna Reconstructing Graphs Using Edge Counting Queries Department of Computer Science Professor Nader Bshouty Abstract

In this thesis we study three well known combinatorial search problems in various settings: The coin weighing problem, the problem of reconstructing graphs using additive queries and the problem of reconstructing hypergraphs using additive queries. All of the three combinatorial search problems share a common structure. In each problem we have a set of objects called a universe or an instance space. From the instance space a unique object is selected, we call it the hidden object. To solve a combinatorial search problem an algorithm must uniquely identify the hidden object by asking minimal number of queries of a given type. We distinguish between two types of algorithms to solve any combinatorial search problem. Adaptive algorithms are algorithms that take into account outcomes of previous queries while non-adaptive algorithms make all queries in advance, before any answer is known.

In the coin weighing problem, we have a hidden n-vector v with m non-zero real number entries. We are allowed to ask queries, Qv(x) = xT v, where x is in {0,1}n. We show the existence of a non-adaptive algorithm for reconstructing the hidden vector with query complexity that matches the information theoretic lower bound. We also give a polynomial time adaptive algorithm for the same problem. This algorithm is optimal for smaller m's and almost optimal for all range of m. Moreover, we introduce few techniques that make our algorithms resistant to noise. That is, using these techniques our algorithms reconstruct correctly the hidden vector even if some of the answers to the queries are incorrect.

In the problem of reconstructing a hidden graph from queries, we have a hidden graph G=(V,E,w). The set of vertices V is known and the set of edges E and their weights are unknown. We are allowed to ask queries, QG(S), that returns the sum of weights of the edges in the subgraph induced by S, where S is a subset of V. For the problem of reconstructing a hidden weighted graph, we show the existence of a non-adaptive algorithm with query complexity that matches the information theoretic lower bound. We also give the first optimal polynomial time adaptive algorithm for reconstructing unweighted graphs. We then extend this result by giving an almost optimal polynomial time adaptive algorithm for reconstructing weighted graphs.

Finally, we show similar results for the problem of reconstructing hidden hypergraphs with constant rank.