Reconstructing Graphs Using Edge Counting Queries

Hanna Mazzawi (Ph.D. Thesis Seminar)

Wednesday, 01.06.2011, 13:30

Taub 601

Advisor: Prof. Nader H. Bshouty

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
\emph{universe} or an \emph{instance space}. From the instance space
a unique object is selected, we call it the \emph{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 of
the form
$$
Q_v(x) = x^T v,
$$
where $x\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)$, where $E\subseteq V\times V$ and
$w\in \mathbb{R}^E$. The set of vertices $V$ is known, and the set
of edges $E$ and their weights are unknown. We are allowed to ask
queries of the form
$$
Q_G(S) = \sum_{e\in E\cap (S\times S)} w(e),
$$
for $S\subseteq V$. That is, the query returns the sum of weights of
the edges in the subgraph induced by $S$. 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 study the problem of reconstructing hidden hypergraphs.
We have a hidden hypergraph $H=(V', E', w')$, where $E'\subset
2^{V'}$ and $w'\in \mathbb{R}^{E'}$. As in the previous problem, the
set of vertices is the only set known, and one must reconstruct the
hidden hypergraph using queries of the form
$$
Q_G(S) = \sum_{e\in E\cap 2^S} w(e),
$$
for $S\subseteq V$. That is, the query returns the sum of weights in
the subgraph induced by $S$. For this problem, we show the existence
of a non-adaptive algorithm for reconstructing an unweighted
hypergraph with constant rank with query complexity that matches the
information theoretic lower bound. Here the rank of a hypergraph is
the size of its largest edge. We also prove the existence of a
non-adaptive algorithm for constant rank weighted graphs with query
complexity that matches the information theoretic lower bound.
To achieve the above results, we use numerous techniques from
theoretical computer science such as, the probabilistic method,
fourier coefficients analysis of functions, the divide and conquer
approach, the guess and check approach, methods from coding theory
and more.