[name=Theorem, sibling=theorem]rThm [name=Lemma, sibling=lemma]rLem
[name=Corollary, sibling=corollary]rCor [name=Proposition,
sibling=proposition]rPro

# Finding a Hidden Edge

Ron Kupfer
Harvard University
<EMAIL_ADDRESS>Noam Nisan
The Hebrew University of Jerusalem
<EMAIL_ADDRESS>
###### Abstract

We consider the problem of finding an edge in a hidden undirected graph
$G=(V,E)$ with $n$ vertices, in a model where we only allowed queries that ask
whether or not a subset of vertices contains an edge. We study the non-
adaptive model and show that while in the deterministic model the optimal
algorithm requires $\binom{n}{2}$ queries (i.e., querying for any possible
edge separately), in the randomized model $\tilde{\Theta}\left(n\right)$
queries are sufficient (and needed) in order to find an edge.
In addition, we study the query complexity for specific families of graphs,
including Stars, Cliques, and Matchings, for both the randomized and
deterministic models.
Lastly, for general graphs, we show a trade-off between the query complexity
and the number of rounds, $r$, made by an adaptive algorithm. We present two
algorithms with $\mathcal{O}\left(rn^{2/r}\right)$ and
$\tilde{\mathcal{O}}\left(rn^{1/r}\right)$ sample complexity for the
deterministic and randomized models, respectively.

##  1 Introduction

Consider the following problem: the input is a hidden graph on $n$ vertices
and your goal is to identify an edge in the graph. For this you are allowed to
use the following type of query: pick a subset $S$ of the vertices and the
answer to the query $S$ is a single bit that is true iff there exist two
vertices $u,v\in S$ such that the edge $(u,v)$ is in the hidden graph. How
many such (non-adaptive) queries are needed in order to identify an edge?

These types of questions and similar ones pop up in a surprisingly diverse set
of situations. Many of them touch on the issue of reductions from search
problems (“find an edge”) to decision problems (“is there an edge”). The type
of computational model that is implied by many of these contexts allows
queries that pick a subset of the input bits and ask for their disjunction
(or, in a dual model, their conjunction). There are several variants of models
that differ by the collection of sets that may be used as a query and by
whether we allow adaptivity and randomization. In Section 2 we discuss some of
these models and their contexts.

###  1.1 Warmup

Before we proceed with our problem let us warm up by looking at the well-
studied simplest variant that ignores the graph structure and views the hidden
$m={\binom{n}{2}}$ potential edges of the input graph simply as a hidden
vector $x\in\\{0,1\\}^{m}$, and allows accessing the input using queries that
pick an arbitrary $Q\subseteq\\{1...m\\}$ and ask whether there exists some
bit $i\in Q$ with $x_{i}=1$. Our aim is to output some index $i\in\\{1...m\\}$
with $x_{i}=1$ (or that no such index $i$ exists, i.e. that $x=00...0$).

Binary search will certainly solve this problem with $\log_{2}(m+1)$ queries
which is clearly optimal. Suppose however that we aim for a non-adaptive
algorithm, one that makes all the queries before looking at any answer. What
is the non-adaptive complexity? It is a simple (and recommended) exercise to
prove that one cannot save on querying all $m$ bits, i.e. that the non-
adaptive complexity is exactly $m$ [20]. A more interesting exercise for the
curious reader is to show that we can do better using randomization: one may
randomly choose $O(\log^{2}m)$ non-adaptive queries such that for every $x$,
with high probability (over our randomized choices) an $i$ with $x_{i}=1$ is
returned [10].111Hint: start be solving the problem for the special case where
the hidden input contains exactly a single 1 bit. It turns out that this is
optimal and a matching $\Omega(\log^{2}m)$ lower bound for randomized non-
adaptive algorithms was given in [21].

###  1.2 Our Results

We now return to our model that does take into account the graph structure and
does not allow querying an arbitrary set of edges $Q$ but rather only allow
queries that specify a subset of the vertices and ask whether an edge is
contained within this subset. I.e., in terms of subsets of the edges, we only
allow queries of the form $Q_{S}=\left\\{(u,v)\mid u,v\in S\right\\}$. As the
trivial upper bound of querying all ${\binom{n}{2}}$ singleton edges is within
our query model, and since the deterministic lower bound in the general model
of $m={\binom{n}{2}}$ [20] still holds, the deterministic simultaneous
complexity in our model is clearly ${\binom{n}{2}}$. So the basic remaining
question is the randomized non-adaptive complexity.

Our main result shows that $\tilde{\Theta}\left(n\right)$ queries are needed
and sufficient in order to find an edge in the non-adaptive randomized model.
[] There exists a randomized non-adaptive algorithm that finds an edge in a
hidden graph, using $\tilde{\mathcal{O}}\left(n\right)$ queries. The
probability of failure of the algorithm on any given input is polynomially
small. Moreover, any randomized non-adaptive algorithm that succeeds in
finding an edge with at least a constant probability makes at least
$\tilde{\Omega}\left(n\right)$ queries.

Note that this establishes a quadratic gap between the deterministic and
randomized non-adaptive models in our setting.

We continue by analyzing the query complexity for specific families of graphs,
both in the randomized and deterministic models. Assume that there is a
guarantee that the hidden input graph comes from some family of possible
graphs. To what extent does this make the problem easier? We study this
question for each of three families of graphs: cliques (the graph is known to
be a clique on some unknown subset of the vertices), stars (a single unknown
center vertex connected to some unknown set of vertices), and matchings (the
degree of each vertex is at most 1).

[]

  * •

For Star, Clique, and Matching graphs, $\tilde{\Theta}\left(n\right)$ non-
adaptive deterministic queries are needed and sufficient in order to find an
edge.

  * •

For Clique and Matching graphs, there exist non-adaptive randomized algorithms
which use only poly-logarithmically many queries.

  * •

For Star graphs, any (even randomized) non-adaptive algorithm makes at least
$\tilde{\Theta}\left(n\right)$ queries.

Our final result relaxes the non-adaptivity restriction and considers a model
where more than a single round of queries is allowed. We exhibit a trade-off
between the query complexity and the number of rounds.

[] For finding an edge in a hidden graph using $r$ rounds,
${\Theta}\left(r\cdot n^{2/r}\right)$ queries are necessary and sufficient in
the deterministic model. There exists a randomized $r$-round algorithm that
makes $\tilde{\mathcal{O}}\left(r\cdot n^{1/r}\right)$ queries. The lower
bound for the deterministic case in this theorem was proven by [16], and
together with our randomized upper bound implies a gap between randomized and
deterministic algorithms for any fixed number of rounds.

All three sets of results are summarized in Table 1.

| Deterministic | Randomized
---|---|---
General Graphs |  $\binom{n}{2}$ ([20]) | $\tilde{\Theta}\left(n\right)$
Star | $\tilde{\Theta}\left(n\right)$ | $\tilde{\Theta}\left(n\right)$
Clique | ${\Theta}\left(n\right)$ | $\tilde{\Theta}\left(1\right)$
Matching | $\tilde{\Theta}\left(n\right)$ | $\tilde{\Theta}\left(1\right)$
General Graphs ($r$ rounds) |  ${\Theta}\left(r\cdot n^{2/r}\right)$ (lower bound [16]) | $\tilde{\mathcal{O}}\left(r\cdot n^{1/r}\right)$
Table 1: Summary of our results

###  1.3 Paper’s Structure

In Section 2 we list some of the contexts in the literature that provide
motivation to this model and discuss variants of our model. In Section 3 we
formally define our problem and add notations. In Section 4, we show how to
find an edge in general graphs and prove a matching lower bound. In Section 5,
we show algorithms and lower bounds for specific families of graphs, including
Star, Cliques, and Matching graphs. In Section 6, we extend our results for
general graphs to a model with $r$ adaptive rounds of querying. We conclude
with a discussion and open problems in Section 7.

##  2 Context and Related Work

Our model belongs to a family of models that allow “disjunction queries”.
I.e., a query that specifies a subset of the input bits and the answer to the
query is a bit that says whether there exists some input bit within the
queried set is true in the hidden input, i.e., the disjunction of the queried
bits.

###  2.1 Motivations

Disjunction-query models (or their dual models that return the conjunction of
the input bits) pop up in surprisingly diverse situations. Here we list
several directions studied before.

  * •

Reducing search to decision problems. A disjunction query may be viewed as a
decision problem that asks whether some solution exists within some subset of
the space. It is natural to attempt using such queries to actually find a
solution. This can be viewed as the combinatorial core of [25] for which a
matching lower bound appears in [21].

  * •

Group testing. Already in World War II, the US public health service found
that they can reduce the number of Syphilis tests administered by pooling a
set of blood samples, testing for an indicator in the pooled sample, i.e., in
the disjunction of the samples. Then, only if the pooled test was positive,
continuing with identifying the infected individual [14]. Similar economies of
testing were applied in the recent Covid-19 PCR tests (see e.g. [15, 17]) and
a large literature has is devoted to these ideas (see e.g. [14]).

  * •

Learning a hidden graph. There has been significant work on scenarios where
there is some ”hidden” graph that needs to be learned, where the available
ways to acquire information regarding the graph are exactly these types of
disjunction queries (e.g., [18, 19, 5, 4, 6, 11, 1]). Variants’ goals are to
estimate only basic properties of the hidden graph, such as its number of
edges [9, 12].

  * •

One-sided decision tree complexity. In [22] the following measure of
complexity of Boolean decision trees was introduced en route to proving
certain lifting theorems: the maximum number of 1-answers returned on a path
to a leaf. They show that this measure is equivalent, up to logarithmic
factors, to the complexity in a model that allows arbitrary disjunctions but
counts the length of paths.222Technically, they looked at the dual case of
0-answers and conjunctions.

  * •

Demand queries. In [24] a concrete model of computation that uses economically
motivated “demand queries” was suggested in order to study algorithms for
bipartite matching. It was shown that the demand query model is equivalent, up
to logarithmic factors, to a model that allows disjunction queries over
subsets of edges that are adjacent to a single left vertex.

  * •

Maximizing a valuation function under a cardinality constraint. We ourselves
have stumbled upon this diverse literature when we were trying to study the
complexity of maximizing the value of an OXS valuation subject to a
cardinality constraint. We describe the question and its relation to
disjunction queries in appendix A.

###  2.2 Query Models

Different variants of model differ from each other in the allowed set of
queries. To some extent, the graph structure imposed on the hidden input is a
convenient way of specifying several natural classes of allowed queries. In
general in these models, each query specifies a subset of the possible
${\binom{n}{2}}$ edges, where this subset must be from a pre-specified set of
allowed queries. There are several natural subsets of allowed queries that
have been previously studied:

  * •

Singleton: The weakest model in this family only allows querying single edges,
and is thus equivalent to a regular Boolean decision tree (e.g., [23]).

  * •

Arbitrary: The strongest model in this family allows queries the disjunction
of any set of edges. This model ignores the graph structure and looks at
simply a hidden set of bits (e.g., [8]).

  * •

Star: This model allows queries that look at an arbitrary subset of the edges
that are connected to a single vertex, i.e, queries of the form
$Q_{v,S}=\left\\{(u,v)\mid u\in S\right\\}$. This model was used in [26] and
is equivalent to the demand model studied in [24].

  * •

Independent Set: This model allows picking a subset of the vertices and asking
whether the set of edges connecting this subset of the vertices contains any
edge of the hidden graph. I.e., whether the given subset of vertices is an
independent set in the hidden graph. That is, queries of the form
$Q_{S}=\left\\{(u,v)\mid u,v\in S\right\\}$. This model was used in [18, 19,
5, 4, 6, 11, 1] and is the focus of this paper.

  * •

Bi-Set: This model allows picking two sets of vertices $A$ and $B$ and asks
whether the hidden graph contains any edge $(u,v)$ where $u\in A$ and $v\in
B$. This model contains the previous two models as special cases and was
studied in [9, 8].

For each of these query models, one may naturally study adaptive vs. non-
adaptive algorithms and deterministic vs. randomized ones.

###  2.3 Tasks

This paper is focused on the simplest task of identifying an arbitrary edge in
the graph in the Independent Set model. The same task was previously studied
by [20, 16] in the arbitrary queries model and their lower bounds trivially
hold for our case. Katona [20] showed that in the non-adaptive case,
$\binom{n}{2}$ queries must be made in order of guaranteeing the
identification of at least one edge. For $r$ rounds, Gerbner and Vizer [16]
showed that $\Omega\left(r\cdot n^{2/r}\right)$ queries are needed.

Other papers have considered other tasks such as completely identifying the
hidden graph (e.g., [18, 19, 5, 4, 6, 11, 1]), calculating or approximating
the number of edges in it [9, 12], or computing some function of the graph
[26, 8].

##  3 Model and Preliminaries

The input for our problem is an undirected graph $G=(V,E)$ with $|V|=n$ and
$|E|=m$, for which we are looking for a pair of vertices $u,v$ such that
$\left\\{u,v\right\\}\in E$. We denote by $d(v)$ the degree of a vertex $v$,
which is the number of its neighbors. The access to the input graph is given
via an Independent Set Query (IS), also noted as an Edge-Detecting Query.

######  Definition 1.

An Independent Set (IS) query, $Q:2^{V}\rightarrow\left\\{0,1\right\\}$,
receives as input a set $A\subseteq V$, and answers whether there exists an
edge $(u,v)\in E$ such that both $u$ and $v$ are in $A$. When $A$ contains an
edge, we say the query is positive, and negative otherwise.

A deterministic non-adaptive IS algorithm is a family $\mathcal{F}$ of subsets
of $V$, and a mapping from the set of answers $\left\\{(A,Q(A))\mid
A\in\mathcal{F}\right\\}$ to a pair of vertices in $V$, or a failing
message333The message could be informative, e.g., “the graph is empty”, “the
graph has at least $k$ edges”. These messages are in use when running several
tests in parallel, and the additional information is needed for the final
algorithm’s decision.. A randomized IS algorithm is a distribution over
deterministic algorithms. We say that an algorithm is $r$-adaptive if it
consists of $r$ rounds where the choice of queries for the $i$th round may
depend on the answers to queries of earlier rounds, but not on answers of the
$i$th round onward. Most of the algorithms and lower bounds in this work are
in the non-adaptive model, i.e., $r=1$. Adaptive algorithms are considered
only in Section 6.

In this work we focus on several families of graphs:

  * •

Singleton graphs: Graphs with a single edge, i.e., there are $u,v\in V$ such
that $E=\left\\{\left\\{u,v\right\\}\right\\}$.

  * •

Star: There exists a vertex $v\in V$ and a set $S\subseteq
V\setminus\left\\{v\right\\}$, such that $E=\left\\{\left\\{s,v\right\\}\mid
s\in S\right\\}$. We refer to $v$ as the center of the graph.

  * •

Clique: There exists a set $S\subseteq V$ such that
$E=\left\\{\left\\{u,v\right\\}\mid u,v\in S\right\\}$.

  * •

Matching: Each vertex has at most one neighbor.

  * •

Overlapping-Product: There exist two, not necessarily disjoint, sets
$A,B\subseteq V$, such that $E=\left\\{\left\\{a,b\right\\}\mid a\in A\ ,b\in
B,\ a\neq b\right\\}$. 444Overlapping-Product graphs is a family containing
both Star and Clique graphs and has implications for welfare maximization as
we discuss in Appendix A.

We denote by $\binom{V}{k}$ the family of subsets of size exactly $k$
contained in $V$, and by $\mathcal{P}(V)$ the family of all subsets of $V$. We
define a distribution ${\mathcal{U}}_{p}\left(A\right)$ over subsets of $A$,
by taking each item $a\in A$ with independent probability $p$. That is, for
$U\sim{\mathcal{U}}_{p}\left(A\right)$ and any set $S\subseteq A$, we have
that $\Pr\left(U=S\right)=p^{|S|}(1-p)^{|A\setminus S|}$. We use $\log n$ to
denote the logarithm function with base $2$, and $\ln n$ for the natural
logarithm. The following standard asymptotic notions are in use:
${\mathcal{O}},{\Omega},{\Theta}$, and their equivalents which suppress of
polylogarithmic factors of $n$,
$\tilde{\mathcal{O}},\tilde{\Omega},\tilde{\Theta}$.

##  4 Finding an Edge in a Hidden Graph

###  4.1 Finding an edge for singleton graphs

We start by showing that in the case that the hidden graph is known to contain
a single edge, the problem is relatively simple and can be solved
deterministically using a logarithmic number of queries.

[] There exists a deterministic IS algorithm that for any graph $G=(V,E)$ with
$m$ edges, returns the unique edge $e\in E$, if $m=1$. In case that $m=0$ the
algorithm returns the message ”none”, and in case that $m>1$ returns the
message ”more than one”, and makes $\mathcal{O}\left(\log n\right)$ non-
adaptive deterministic queries.

###### Proof.

We start with the assumption that $m=1$ and describe a randomized algorithm
for the problem of finding this unique edge. The algorithm first samples
$t=24\ln n$ random sets of vertices according to
${\mathcal{U}}_{\frac{1}{2}}\left(V\right)$. For every triplet $a,b,c\in V$,
the probability that a ${a,b}\in S$ and ${c}\notin S$ is $\frac{1}{8}$, and
the probability that this would not hold for any samples is

$\left(1-\frac{1}{8}\right)^{t}<n^{-3}.$

Assuming the graph’s single edge is $(a,b)$, for every sample $S$ it holds
that $Q(S)$ is positive if and only if $\left\\{a,b\right\\}\subseteq S$.
Whenever we have a positive $S$ such that $c\notin S$, we are guaranteed that
$c$ is not a part of the single edge. Taking a union over all possible
$a,b,c\in V$, gives that with positive probability, using $t$ samples, for any
single edge graph $\left\\{a,b\right\\}$, we can rule out all other vertices
as being part of the edge. Hence, there exists some selection of the $t$
queries that is correct for all possible single-edge inputs, and we can find
the edge deterministically using $t$ queries. The full algorithm needs also to
distinguish between the cases where $m=0$ and $m>1$. This is in fact a simple
task. The existent of at least one edge can be verified by the single query
$Q(V)$. If there is more than one edge in the graph, the elimination process
would always keep at least two pairs of vertices as candidates for an being an
edge and will fail returning a single edge, no matter how many queries the
algorithm makes, and this case is also easily identified after the $t$
queries. ∎

We later use the above algorithm as a sub-procedure in many of the algorithms
in this work, and use the following notion:

######  Definition 2.

Given a subset $S\subseteq V$, we denote by ${\mathcal{L}}\left(S\right)$ the
set of queries asked in order to solve the problem described in Proposition
4.1, for the graph $G=\left(S,E\cap\binom{S}{2}\right)$.

For Singleton graphs, i.e., when it is known that $m=1$, we give an explicit
construction using $\lceil 4\log n\rceil$ queries in Appendix B.1. In
addition, for cases when the single edge has a known endpoint $v$, we describe
an algorithm that uses $\lceil 2\log n\rceil$ queries for the same problem.
When is it possible to use the later, more efficient algorithm, we use the
notation ${\mathcal{L}^{v}}\left(S\right)$. Both algorithms have the same
asymptotic behavior like the one in Proposition 4.1, and we may use it without
harming the asymptotic correctness of any of our claims.

###  4.2 Upper Bound for General graphs

For general graphs, the trivial deterministic algorithm who queries all pairs
and returns any pair with positive answer, is in fact optimal as proven in
[20]:

[] [20]: Any deterministic algorithm for edge finding in a hidden graph,
requires $\binom{n}{2}$ queries. We reprove the claim in Appendix B.2. On the
other hand, we now show that in the randomized model, there exists an
algorithm that makes only $\tilde{\Theta}\left(n\right)$ queries, and fails
with a polynomially small probability.

Our algorithm handles three different cases in parallel. First, if the number
of edges in the graph is large, sampling random pairs of vertices finds an
edge with high probability. Second, assuming at least one of the vertices $v$
has a high degree, then $v$ and one of its neighbors can be found using an
efficient scheme described below. Lastly, if the former two cases do not
apply, i.e., there are few edges and they are scattered, we can find an edge
by querying few large sets. Whenever receiving a positive answer, there is a
good probability there is a single edge in this set. The edge itself can be
then identified using the algorithm from Proposition 4.1.

Let $D=\left\\{2^{i}\cdot\sqrt{n}\mid i=1,...,\left\lfloor\frac{1}{2}\log
n\right\rfloor\right\\}$ be a set of estimations for the maximal degree of a
vertex in the graph and $c>0$ some constant later to be chosen. We query the
following three families in parallel, each with quasi-linear many queries.

  * •

$\mathcal{F}_{1}$ is a family of $\lceil c\cdot(n+1)\ln n\rceil$ uniformly
chosen pairs.

  * •

For each vertex $v\in V$, and $d\in D$ we denote by $\mathcal{F}_{2}^{(v,d)}$
a sample of $\lceil c\cdot 4e^{2}\ln n\rceil$ sets sampled according to
${\mathcal{U}}_{\frac{1}{d}}\left(V\setminus\left\\{v\right\\}\right)$ and
define $\mathcal{F}_{2}$ as follows.

$\mathcal{F}_{2}=\bigcup_{v\in V,\ d\in
D}\bigcup_{S\in\mathcal{F}_{2}^{(v,d)}}{\mathcal{L}^{v}}\left(S\right)$

  * •

We denote by $\mathcal{F}_{3}^{0}$ a sample of $\lceil c\cdot 2e^{2}n\ln
n\rceil$ sets sampled according to
${\mathcal{U}}_{\frac{1}{\sqrt{n}}}\left(V\right)$, and define
$\mathcal{F}_{3}$ as follows.

$\mathcal{F}_{3}=\bigcup_{S\in\mathcal{F}_{3}^{0}}{\mathcal{L}}\left(S\right).$

By Proposition 4.1, we have that $|{\mathcal{L}}\left(S\right)|\leq 24\ln|S|$
and the total number of queries is then
$|\mathcal{F}_{1}\cup\mathcal{F}_{2}\cup\mathcal{F}_{3}|\leq c\cdot\alpha
n\log^{3}n$ for $\alpha=500$.

######  Lemma 1.

For every $c>0$, there is an algorithm which uses $c\cdot\alpha n\log^{3}n$
queries and finds an edge with probability at least $1-n^{-c}$.

###### Proof.

For a given graph $G=(V,E)$ with $n$ vertices, $m$ edges, and unknown maximal
degree $d$, we sample $\mathcal{F}_{1},\mathcal{F}_{2},\mathcal{F}_{3}$ as
described above and divide our analysis into three disjoint cases:

  1. 1.

$m>\frac{n}{2}$

  2. 2.

$m\leq\frac{n}{2}$ and $d\geq\sqrt{n}$

  3. 3.

$m\leq\frac{n}{2}$ and $d<\sqrt{n}$

In the first case, the probability for a query $S\in{\cal F}_{1}$ to hit an
edge is ${m}/{\binom{n}{2}}>1/(n+1)$, and when counting over all samples, the
failing probability is at most $\left(1-\frac{1}{n+1}\right)^{|{\cal
F}_{1}|}<n^{-c}$.

In the second case, if ${\cal F}_{1}$ finds an edge, the algorithm succeed.
Else, we use the answers from ${\cal F}_{2}$ in order to find a vertex of
maximal degree $d$ and one of its neighbors. Given $v\in V$ of degree $d$ and
$d^{\prime}\in D$ such that $d^{\prime}\leq d<2d^{\prime}$, we bound the
probability that $\mathcal{F}_{2}^{(v,d^{\prime})}$ contains a set with a
single edge. The probability of including exactly one of $v$’s neighbors is

$d\cdot\frac{1}{d^{\prime}}\left(1-\frac{1}{d^{\prime}}\right)^{d-1}>d\cdot\frac{1}{2d}\left(1-\frac{1}{d}\right)^{d-1}>\frac{1}{2e}.$

Conditioning on a selection of a neighbor $u$, the probability of excluding
all of $u$’s neighbors is at least,

$\left(1-\frac{1}{d^{\prime}}\right)^{d-1}>\left(1-\frac{1}{d}\right)^{d-1}>\frac{1}{e}.$

This is since $d$ is a bound on $u$’s degree and $v$ is a neighbor of $u$. In
addition, for any other edge $e\in E$, not touching either $v$ or $u$, the
probability for including $e$ in the sample is $\frac{1}{d^{\prime
2}}\leq\frac{1}{n}$. Using the union bound, with probability of at least
$1-\frac{m}{n}\geq\frac{1}{2}$, no such edge is selected. That is, for any set
$S\in\mathcal{F}_{2}^{(v,d^{\prime})}$ we have a probability of at least
$\frac{1}{4e^{2}}$ that $S$ contains a single edge. Using the queries
${\mathcal{L}}\left(S\right)$ the algorithm finds if this is indeed the case,
and if so, returns an edge. Since there are $c\cdot 4e^{2}\ln n$ samples in
$\mathcal{F}_{2}^{(v,d^{\prime})}$, the failing probability is at most
$n^{-c}$.

In the last case, if ${\cal F}_{1}$ or ${\cal F}_{2}$ finds an edge, the
algorithm succeed, and else we use the answers from ${\cal F}_{3}$ in the
following way. For any pair $\left\\{u,v\right\\}\in E$, the probability for a
set $S\in{\cal F}_{3}^{0}$ to include both $u$ and $v$ is $\frac{1}{n}$.
Conditioning on the selection of $u$ and $v$, the probability of excluding all
of their neighbors from the sampling is at least

$\left(1-\frac{1}{\sqrt{n}}\right)^{2\sqrt{n}-2}>\frac{1}{e^{2}}.$

This is since the maximal degree of each of the vertices is smaller than
$\sqrt{n}$. In addition, for any other edge $e\in E$ not touching either $v$
or $u$, the probability of including $e$ in the sample is $\frac{1}{n}$. Using
a union bound, with probability of at least $1-\frac{m}{n}\geq\frac{1}{2}$, no
such edge is selected. That is, for any $S\in{\cal F}_{3}^{0}$ there is a
probability of at least $(2e^{2}\cdot n)^{-1}$ to contain exactly one edge.
Using the queries ${\mathcal{L}}\left(S\right)$, the algorithm finds if this
is indeed the case, and if so, to return an edge. Since there are $c\cdot
2e^{2}n\ln n$ samples in ${\cal F}_{3}^{0}$, the failing probability is at
most $n^{-c}$.

In total, the algorithm makes
$|\mathcal{F}_{1}\cup\mathcal{F}_{2}\cup\mathcal{F}_{3}|\leq c\cdot\alpha
n\log^{3}n$ queries and fails to find an edge with probability at most
$n^{-c}$. ∎

Notice that failing is always of the form of an error message, i.e., the
algorithm never return a pair which does not induces an edge.

###  4.3 Lower Bound for General graphs

We now complete the proof of Theorem 1.2 with a matching lower bound.

[] Any randomized algorithm for edge finding that succeeds in a constant
probability, requires $\Omega\left(\frac{n}{\log^{2}n}\right)$ queries.
Moreover, the lower bound holds for the family of Star graphs.

###### Proof.

By Yao’s principle [27], it if sufficient to show that there exists a
distribution $\mathcal{D}$ over the inputs such that no deterministic
algorithm could succeed with high probability when the inputs are distributed
according to $\mathcal{D}$. Let $\mathcal{D}$ be the following distribution
over graphs: we choose one vertex $v$ uniformly at random. For every $u\in
V\setminus\left\\{v\right\\}$, the edge $\left\\{v,u\right\\}$ is in $E$ with
probability $\frac{1}{\log n}$.

Let $ALG$ be a deterministic algorithm for the problem who makes
$o\left(\frac{n}{\log^{2}n}\right)$ queries. We show that $ALG$ fails with
high probability where inputs are drawn from $\mathcal{D}$.

We have that any query of size at most $10\log^{2}n$, includes $v$ with
probability at most $\frac{10\log^{2}n}{n}$. Since there are
$o(\frac{n}{\log^{2}n})$ queries in total, the probability that any query
includes $v$ is negligible, and with probability $1-o(1)$ all of them return a
negative answer. On the other hand, for every query $S$ of size at least
$10\log^{2}n$, the probability that $S$ does not include any vertex connected
to $v$ is bounded by $(1-\frac{1}{\log n})^{10\log^{2}n}<n^{-10}$. Since there
are $o(\frac{n}{\log^{2}n})$ queries, by using the union bound, we get that
with probability of at least $1-n^{-9}$ over $\mathcal{D}$, in all of such
queries, there is always a vertex $u\in S$ who is a neighbor of $v$. Thus,
with probability $1-n^{-9}$, we have that $Q(S)$ is a mere indicator whether
or not $v\in S$. In case that any of the queries acted unexpectedly, we assume
the algorithm succeeds in finding an edge. Otherwise, the algorithm run on two
different stars that are both rooted at $v$ will be identical regardless of
the edges realization and the algorithm cannot do anything but guessing a
random vertex and succeed with probability $\frac{1}{\log n}$. In total, we
have a probability of $o(1)$ for finding an edge, hence proving a lower bound
for the randomized query complexity. ∎

The combination of the claims of Lemmas 1 and 4.3 is exactly the statement of
Theorem 1.2.

##  5 Finding an Edge in Special Cases

In this section, we study families of graphs for which we design more
efficient algorithms or prove tighter lower bounds, either in the
deterministic or randomized models. All of the results in this Section are
summarized in Theorem 1.2.

###  5.1 Overlapping-Product graphs

For this family, since star graphs are a type of overlapping-product graphs,
the randomized lower bound of Theorem 1.2 holds. We complete this result by
showing a deterministic algorithm with query complexity which is also quasi-
linear. The algorithm is based on a divide-and-conquer technique and it is
described in the following proof.

######  Lemma 2.

There exists a deterministic algorithm for finding an edge in a Overlapping-
Product graphs, that uses $n\lceil\log n\rceil$ queries.

###### Proof.

We build the algorithm recursively, assuming $n$ in the number of vertices in
the graph. For $n=0,1$, the claim is trivial. For $n>1$, the algorithm divides
the set $V$ into two disjoint sets $V_{1},V_{2}$, such that
$\left||V_{1}|-|V_{2}|\right|\leq 1$. Then, by the induction assumption, solve
for each set recursively in parallel using
$|V_{1}|\lceil\log|V_{1}|\rceil+|V_{2}|\lceil\log|V_{2}|\rceil\leq n\lceil\log
n-1\rceil$ queries. If there is an edge that both of its endpoints in the same
set, the algorithm finds it.

Otherwise, we check if there is an edge with one endpoint in each set, using
the fact that both sets do not contain any edge and the ”almost product”
property. We then query each of the sets in

$\mathcal{F}_{1}=\left\\{\left\\{v\right\\}\cup V_{2}\mid v\in
V_{1}\right\\}\quad\mathcal{F}_{2}=\left\\{\left\\{v\right\\}\cup V_{1}\mid
v\in V_{2}\right\\}.$

For any $v\in V_{1}$ such that $Q(\left\\{v\right\\}\cup V_{2})$ is positive,
we have that $v$ is an endpoint of an edge since there are no edges in
$V_{2}$. Assume without loss of generality that $v\in A$, thus there exist a
vertex $u\in V_{2}\cap B$. For any $w\in V_{2}$ such that
$Q(\left\\{w\right\\}\cup V_{1})$ is positive, we have that $w\in B$.
Otherwise, the pair $u,w$ induces an edge. In the same way, we have that all
vertices in $V_{1}$ which are endpoints of edges, belong to $A$ That is, any
pair $v_{1}\in V_{1}$ and $v_{2}\in V_{2}$ such that
$Q(\left\\{v_{1}\right\\}\cup V_{2})$ and $Q(\left\\{v_{2}\right\\}\cup
V_{1})$ are positive, induced an edge.

Since all queries are asked in a single parallel querying round, the total
number of queries is then $n\lceil\log n\rceil$. ∎

###  5.2 Stars

Lemma 4.3 shows that any randomized algorithm for finding an edge in a star
graph must query at least $\Omega\left(\frac{n}{\log^{2}n}\right)$ queries. We
now show a tighter lower bound for the deterministic case, using a reduction
from the problem of witness finding over $n-1$ items.

######  Lemma 3.

Any deterministic algorithm for edge finding in a hidden Star graph, requires
$n-1$ queries.

###### Proof.

Given an instance for the witness finding problem with $n-1$ items (or
equivalently, an input $G_{0}=(V_{0},E_{0})$ for the edge finding problem
where $\binom{V_{0}}{2}=n-1$), we show a reduction to the problem of edge
finding in a star graph $G=(V,E)$ with $n$ vertices.

denote by $v_{1},\ldots,v_{n}$ the vertices of $V$ and by
$u_{1},\ldots,u_{n-1}$ the items (or edges) in the original problem. We define
$E$ to have $v_{n}$ as the center of the graph and the neighbors are according
to the original problem, i.e., $\left\\{v_{i},v_{n}\right\\}\in\mathbb{E}$ if
$u_{i}$ is positive in the original problem, and there are no other edges in
$E$.

Every query that does not include $v_{n}$, does not include an edge and thus
always negative and gives no information. Every query that includes $v_{n}$ is
positive if and only if $u_{i}$ is positive in the original problem, thus
completing the reduction. Lemma 4.2 then complete the claim. ∎

###  5.3 Cliques

The algorithm of Lemma 2 finds an edge in a clique using
$\mathcal{O}\left(n\log n\right)$ queries, and can be improved to a linear
query complexity, as we show on Appendix B.3. [] There exist a deterministic
algorithm for finding an edge in a hidden clique, that uses
$\mathcal{O}\left(n\right)$ queries. On the other hand, we now show that in
the deterministic model, at least $\frac{n}{2}$ queries are needed in order to
find an edge in a clique.

######  Lemma 4.

in the deterministic model, at least $\frac{n}{2}$ queries are needed in order
to find an edge in a clique.

###### Proof.

Given a set of at most $\frac{n}{2}-1$ queries, $\mathcal{F}$, an adversary
may build a fooling set in the following way: We keep a set $C$ which we
initiate to include all the vertices of the graph. While there still exists a
set $S\in\mathcal{F}$ of size $1$ or $2$, update
$S^{\prime}=S^{\prime}\setminus S$ for all $S^{\prime}\in\mathcal{F}$, and
$C=C\setminus S$. Since there are at most $\frac{n}{2}-1$ queries, and each
set correspond to at most two vertices removal, the process ends with some set
$C$ of size at least $2$, and all $S\in\mathcal{F}$ are either empty, or
contains at least three vertices. According to the graph induced by $C$, the
answers to the queries are negative on any set $S$ that is now empty, and
positive for all other sets. No deterministic algorithm can distinguish
between the graphs induced by $C$ and a graphed induced by
$C\setminus\left\\{v\right\\}$ for any edge $v\in C$, thus failing on at least
one input. ∎

On the other hand, we show that using randomized queries, an edge of the
clique can be found using polylogarithmic many queries and polynomially small
failing probability. Let $D=\left\\{2^{i}\mid i=1,...,\left\lceil\log
n\right\rceil\right\\}$ be a set of estimations for the number of vertices in
the hidden clique and $c>0$ some constant. For each estimation $d\in D$, we
sample $\lceil c\cdot 8e\ln n\rceil$ sets according to
${\mathcal{U}}_{\frac{1}{d}}\left(V\right)$ and denote this family of samples
$\mathcal{F}_{d}$. We then query

$\mathcal{F}=\bigcup_{d\in
D}\bigcup_{S\in\mathcal{F}_{d}}{\mathcal{L}}\left(S\right),$

where $|\mathcal{F}|\leq c\alpha\log^{3}n$ for $\alpha=500$.

######  Lemma 5.

For every $c>0$, there is an algorithm which makes $c\alpha\log^{3}n$ queries
and finds an edge in a Clique graph with probability at least $1-n^{-c}$.

###### Proof.

Let $d$ be the number of vertices in the clique, and $d^{\prime}\in D$ is such
that $d^{\prime}\leq d<2d^{\prime}$. The algorithm succeed whenever there
exist at least one sample in $\mathcal{F}_{d^{\prime}}$ that has exactly one
edge. The probability the exactly two vertices of the clique are selected is
$\binom{d}{2}\left(\frac{1}{d^{\prime}}\right)^{2}\left(1-\frac{1}{d^{\prime}}\right)^{d-2}\geq\binom{d}{2}\left(\frac{1}{2d}\right)^{2}\left(1-\frac{1}{d}\right)^{d-2}>\frac{1}{8e}$.
Since $|\mathcal{F}_{d^{\prime}}|\geq c\cdot 8e\ln n$ we have that the failing
probability is at most $n^{-c}$. ∎

###  5.4 Matchings

For Matching graphs, the algorithm presented in Lemma 2 fails and we now show
a modification of the algorithm for this case.

######  Lemma 6.

There exists a deterministic algorithm for finding an edge in a hidden
matchings, that makes $\mathcal{O}\left(n\log^{2}n\right)$ queries.

###### Proof.

We build the algorithm recursively, assuming $n$ in the number of vertices in
the graph. For $n=0,1$, the claim is trivial. For $n>1$, the algorithm divides
the set $V$ into two disjoint sets $V_{1},V_{2}$, such that
$\left||V_{1}|-|V_{2}|\right|\leq 1$. Then, by the induction assumption,
solves for each set recursively. If there is an edge that both of its
endpoints in the same set, the algorithm finds it. Otherwise, we check if
there is an edge with one endpoint in each set, using the fact the both sets
do not contain any edge. We query for each $v\in V_{1}$ if it has a match in
$V_{2}$, and if so, what it is. That is,

$\mathcal{F}=\bigcup_{v\in V_{1}}{\mathcal{L}^{v}}\left(V_{2}\right),$

Let $f(n)$ be the total number of queries in the algorithm. We have that

$f(n)=f\left(\left\lceil\frac{n}{2}\right\rceil\right)+f\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+\left\lfloor\frac{n}{2}\right\rfloor\cdot
24\ln\left\lceil\frac{n}{2}\right\rceil$

for $n>1$ and $f(1)=1$ trivially. Using the generalized Master theorem (see,
e.g., [13]) we have that $f(n)=\mathcal{O}\left(n\log^{2}n\right)$, when all
of the queries are asked in a single parallel querying round. ∎

We show a deterministic lower bound of $\frac{n}{2}$ queries using reduction
from the witness finding problem. The reduction also proves that any
randomized algorithm that succeeds with constant probability, makes
$\Omega\left(\log^{2}n\right)$ queries.

######  Lemma 7.

Any deterministic algorithm for edge finding in a hidden matching, requires
$\frac{n}{2}$ queries. Moreover, Any randomized algorithm for this problem who
succeeds in finding an edge with constant probability, requires
$\Omega\left(\log^{2}n\right)$ queries.

###### Proof.

Given an instance for the witness finding problem with $\frac{n}{2}$ items (or
equivalently, an input $G_{0}=(V_{0},E_{0})$ for the edge finding problem
where $\binom{V_{0}}{2}=\frac{n}{2}$), we show a reduction to the problem of
edge finding in a Matching graph $G=(V,E)$ with $n$ vertices.

denote by $v_{1},\ldots,v_{\frac{n}{2}},u_{1},\ldots,u_{\frac{n}{2}}$ the
vertices of $V$ and by $w_{1},\ldots,w_{\frac{n}{2}}$ the items (or edges) in
the original problem. We define $E$ to have an edge
$\left\\{v_{i},u_{i}\right\\}$ in $E$ if $w_{i}$ is positive in the original
problem, and there are no other edges in $E$. Given a query $S$, the answer is
positive if and only if there exists $i$ such that both $v_{i}$ and $u_{i}$
belong to $S$ and $w_{i}$ is positive. That is, any query for this graph can
be asked on $G_{0}=(V_{0},E_{0})$ and the reduction is complete. Lemma 4.2
then show our claim for the deterministic model. For the randomized model, the
lower bound of $\Omega\left(\log^{2}n\right)$ for witness finding is due to
Kawachi et. al. [21]. ∎

In the randomized model, we take a similar approach to the one taken for
Clique graphs. Let $D=\left\\{2^{i}\mid i=1,...,\left\lfloor\log
n\right\rfloor\right\\}$ be a set of estimations for the number of edges in
the hidden matching and $c>0$ some constant. For each estimation $d\in D$, we
sample $\lceil c\cdot 2e\ln n\rceil$ sets according to
${\mathcal{U}}_{\frac{1}{\sqrt{d}}}\left(V\right)$ and denote this family of
samples $\mathcal{F}_{d}$. We then query

$\mathcal{F}=\bigcup_{d\in
D}\bigcup_{S\in\mathcal{F}_{d}}{\mathcal{L}}\left(S\right),$

where $|\mathcal{F}|\leq c\alpha\log^{3}n$ for $\alpha=500$.

######  Lemma 8.

For every $c>0$, there is an algorithm which makes $c\alpha\log^{2}n$ queries
and finds an edge in a Matchings graph with probability at least $1-n^{-c}$.

###### Proof.

Let $d$ be the number of edges in $E$, and $d^{\prime}\in D$ is such that
$d^{\prime}\leq d<2d^{\prime}$. the algorithm succeeds if at least one of the
samples in $\mathcal{F}_{d^{\prime}}$ has exactly one edge.

$d\left(\frac{1}{\sqrt{d^{\prime}}}\right)^{2}\left(1-\left(\frac{1}{\sqrt{d^{\prime}}}\right)^{2}\right)^{d-1}\geq
d\cdot\frac{1}{2d}\left(1-\frac{1}{d}\right)^{d-1}>\frac{1}{2e}.$

Since $|\mathcal{F}_{d^{\prime}}|\geq c\cdot 2e\ln n$ we have that the failing
probability is at most $n^{-c}$. ∎

Note that by selecting $c=1/\ln n$, there is constant probability for the
algorithm to succeed while making only $\mathcal{O}\left(\log^{2}n\right)$
queries, which match the lower bound of Lemma 7. This conclude the proof of
Theorem 1.2.

##  6 Edge Finding Using $r$ Rounds

In this section we consider an adaptive model of $r$ rounds, when at each
round a family of queries are asked and answered in parallel and the selection
of the queries depends only on answers from previous rounds and possibly
randomization. When limited to $r$ adaptive querying rounds, we use the non-
adaptive algorithms from Section 4 in order to construct algorithms with
improved query complexity. We start by stating a lower bound by [16] for the
deterministic case. This bound holds even for arbitrary queries on any subset
of edges. [[16]] Any deterministic algorithm for edge finding which uses at
most $r$ rounds, requires $\Omega\left(r\cdot n^{2/r}\right)$ queries.

######  Definition 3.

For a graph $G=(V,E)$ and a disjoint partition of the vertices
$\left\\{V_{i}\right\\}$, we define the partition graph,
$H=(\mathcal{V},\mathcal{E})$ where $\mathcal{V}=\left\\{V_{i}\right\\}$ and

$\mathcal{E}=\left\\{\left\\{U,V\right\\}\mid U,V\in\mathcal{V},\exists a,b\in
U\cup V,\ s.t.\ \left\\{a,b\right\\}\in E\right\\}.$

See 1.2

###### Proof.

In the deterministic model, assume by induction that for any $r^{\prime}<r$ we
have that the total number of queries is at most $10r^{\prime}\cdot
n^{2/r^{\prime}}$. The case $r=1$ is handled in Theorem 1.2. For $r>1$,
partition $V$ arbitrarily into $k=\left\lceil 2\cdot n^{1/r}\right\rceil+4$
sets $V_{1},\ldots,V_{k}$ of size at most $t=\left\lfloor\frac{1}{2}\cdot
n^{1-1/r}\right\rfloor$ each 555We have that $kt\geq n$ for $r>1$.. In the
partition graph, we query all of the queries $Q(\left\\{V_{i},V_{j}\right\\})$
(i.e., $Q(V_{i}\cup V_{j})$ in the original graph), for $i,j\in[k]$. If all of
the answers are negative, the algorithm terminates, otherwise it continues
with any pair of two positive sets, iteratively. By the induction assumption,
the total number of queries $f(n)$ is then,

$\displaystyle f(n)$ $\displaystyle\leq$
$\displaystyle\binom{k}{2}+10(r-1){(2t)}^{2/(r-1)}$ $\displaystyle\leq$
$\displaystyle\left(2\cdot n^{1/r}+5\right)\left(2\cdot
n^{1/r}+4\right)/2+3(r-1){\left(n^{1-1/r}\right)}^{2/(r-1)}$
$\displaystyle\leq$ $\displaystyle 2\cdot n^{2/r}+9\cdot
n^{1/r}+10+10(r-1)\cdot n^{2/r}$ $\displaystyle\leq$ $\displaystyle 10r\cdot
n^{2/r},$

where the last inequality holds whenever $r<\log n$. For $r\geq\log n$, the
problem is solvable using binary search algorithm that makes $6$ queries at
each round (see Appendix B.4).

In the randomized model, assume that for any $r^{\prime}<r$ we have that the
total number of queries is at most $2000cr^{\prime}\cdot
n^{1/r^{\prime}}\ln^{3}n$ and the error probability is at most $r\cdot
n^{-c/r}$. The case $r=1$ is handled Theorem 1.2. For $r>1$, partition $V$
arbitrarily into $k=\left\lceil 2\cdot n^{1/r}\right\rceil+4$ sets
$V_{1},\ldots,V_{k}$ of size at most $t=\left\lfloor\frac{1}{2}\cdot
n^{1-1/r}\right\rfloor$ each. In the partition graph, we run the single-round
randomized algorithm from Theorem 1.2 with error parameter of $c$. The running
on the partition set is positive whenever there is an edge in the union of two
sets. We continue with this union iteratively, using $r-1$ rounds. By the
induction assumption the total number of queries $f(n)$ is then,

$\displaystyle f(n)$ $\displaystyle\leq$ $\displaystyle
500ck\ln^{3}k+2000c(r-1){(2t)}^{1/(r-1)}\ln^{3}2t$ $\displaystyle\leq$
$\displaystyle 500c(2n^{1/r}+5)\ln^{3}n+2000c(r-1){n}^{1/r}\ln^{3}n$
$\displaystyle\leq$ $\displaystyle 2000cr{n}^{1/r}\ln^{3}n$

where the second inequality holds whenever $r<\log n$. For $r\geq\log n$, the
problem is solvable with standard binary search algorithm, using two queries
at each round.

The algorithm errs with probability at most $k^{-c}+(r-1)\cdot(2t)^{-c}\leq
r\cdot n^{-c/r}$. Taking any $c>2r$ gives a polynomially small error
probability, with the required query complexity for $r<\log n$. As mentioned,
for $r\geq\log n$ the claim hold deterministically.

∎

##  7 Discussion and Open Problems

In this work we showed a randomized algorithm for edge finding in the non-
adaptive IS model and prove the tightness of its query complexity. We showed
that while in the deterministic model the optimal algorithm requires
$\binom{n}{2}$ queries, in the randomized model $\tilde{\Theta}\left(n\right)$
queries are sufficient (and needed) in order to find an edge. In addition, we
analyzed the query complexity for Stars, Clique and Matching graphs, for both
the randomized and deterministic model. Lastly, for general graphs, we showed
a trade-off between the query complexity and the number of adaptive rounds $r$
made by the algorithm. We show two algorithms with
$\mathcal{O}\left(rn^{2/r}\right)$ and
$\tilde{\mathcal{O}}\left(rn^{1/r}\right)$ sample complexity for the
deterministic and randomized models, respectively.

Two future directions are:

  * •

Closing the polylogarithmic gaps between lower and upper bounds in some of our
results.

  * •

Extending our results for edge finding in a graph to the task of hyperedge
finding in a hypergraphs, with the appropriate query model as discussed in [7,
2]. This extension has implications for welfare maximization as discussed in
Appendix A.

  * •

Finding the optimal adaptive randomized bound is still an open question. It
would be interesting to see either a $\Omega{rn^{1/r}}$ lower bound or an
improved randomized algorithm that takes further advantage of adaptivity.

## References

  * Abasi and Nader [2019] Hasan Abasi and Bshouty Nader.  On learning graphs with edge-detecting queries.  In _Algorithmic Learning Theory_ , pages 3–30. PMLR, 2019.
  * Abasi et al. [2018] Hasan Abasi, Nader H Bshouty, and Hanna Mazzawi.  Non-adaptive learning of a hidden hypergraph.  _Theoretical Computer Science_ , 716:15–27, 2018.
  * Akra and Bazzi [1998] Mohamad Akra and Louay Bazzi.  On the solution of linear recurrence equations.  _Computational Optimization and Applications_ , 10(2):195–210, 1998.
  * Alon and Asodi [2005] Noga Alon and Vera Asodi.  Learning a hidden subgraph.  _SIAM Journal on Discrete Mathematics_ , 18(4):697–712, 2005.
  * Alon et al. [2004] Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov.  Learning a hidden matching.  _SIAM Journal on Computing_ , 33(2):487–501, 2004\.
  * Angluin and Chen [2008] Dana Angluin and Jiang Chen.  Learning a hidden graph using o (logn) queries per edge.  _Journal of Computer and System Sciences_ , 74(4):546–556, 2008.
  * Angluin et al. [2006] Dana Angluin, Jiang Chen, and Manfred Warmuth.  Learning a hidden hypergraph.  _Journal of Machine Learning Research_ , 7(10), 2006.
  * Assadi et al. [2020] Sepehr Assadi, Deeparnab Chakrabarty, and Sanjeev Khanna.  Graph connectivity and single element recovery via linear and or queries.  _arXiv preprint arXiv:2007.06098_ , 2020.
  * Beame et al. [2020] Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha.  Edge estimation with independent set oracles.  _ACM Trans. Algorithms_ , 16(4), 2020.  doi: 10.1145/3404867.
  * Ben-David et al. [1992] Shai Ben-David, Benny Chor, Oded Goldreich, and Michel Luby.  On the theory of average case complexity.  _Journal of Computer and system Sciences_ , 44(2):193–219, 1992.
  * Chang et al. [2014] Huilan Chang, Hung-Lin Fu, and Chih-Huai Shih.  Learning a hidden graph.  _Optimization Letters_ , 8(8):2341–2348, 2014\.
  * Chen et al. [2020] Xi Chen, Amit Levi, and Erik Waingarten.  Nearly optimal edge estimation with independent set queries.  In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 2916–2935. SIAM, 2020.
  * Cormen et al. [2009] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein.  _Introduction to algorithms, Third Edition_.  MIT press, 2009.
  * Du et al. [2000] Dingzhu Du, Frank K Hwang, and Frank Hwang.  _Combinatorial group testing and its applications_ , volume 12.  World Scientific, 2000.
  * Eberhardt et al. [2020] Jens Niklas Eberhardt, Nikolas Peter Breuckmann, and Christiane Sigrid Eberhardt.  Multi-stage group testing improves efficiency of large-scale covid-19 screening.  _Journal of Clinical Virology_ , 128:104382, 2020.
  * Gerbner and Vizer [2016] Dániel Gerbner and Máté Vizer.  Rounds in a combinatorial search problem.  _arXiv preprint arXiv:1611.10133_ , 2016.
  * Gollier and Gossner [2020] Christian Gollier and Olivier Gossner.  Group testing against covid-19.  Technical report, EconPol Policy Brief, 2020.
  * Grebinski and Kucherov [1997] Vladimir Grebinski and Gregory Kucherov.  Optimal query bounds for reconstructing a hamiltonian cycle in complete graphs.  In _Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems_ , pages 166–173. IEEE, 1997.
  * Grebinski and Kucherov [1998] Vladimir Grebinski and Gregory Kucherov.  Reconstructing a hamiltonian cycle by querying the graph: Application to dna physical mapping.  _Discrete Applied Mathematics_ , 88(1-3):147–165, 1998.
  * Katona [2011] Gyula OH Katona.  Finding at least one excellent element in two rounds.  _Journal of Statistical Planning and Inference_ , 141(8):2946–2952, 2011.
  * Kawachi et al. [2012] Akinori Kawachi, Benjamin Rossman, and Osamu Watanabe.  Query complexity and error tolerance of witness finding algorithms.  In _Electronic Colloquium on Computational Complexity (ECCC)_ , volume 19, page 2, 2012.
  * Knop et al. [2021] Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan.  Log-rank and lifting for and-functions.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 197–208, 2021.
  * Messmer and Bunke [1999] Bruno T Messmer and Horst Bunke.  A decision tree approach to graph and subgraph isomorphism detection.  _Pattern recognition_ , 32(12):1979–1998, 1999\.
  * Nisan [2021] Noam Nisan.  The demand query model for bipartite matching.  In _Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 592–599. SIAM, 2021.
  * Valiant and Vazirani [1985] Leslie G Valiant and Vijay V Vazirani.  Np is as easy as detecting unique solutions.  In _Proceedings of the seventeenth annual ACM symposium on Theory of computing_ , pages 458–463, 1985.
  * Wang et al. [2012] Jianguo Wang, Eric Lo, and Man Lung Yiu.  Identifying the most connected vertices in hidden bipartite graphs using group testing.  _IEEE Transactions on Knowledge and Data Engineering_ , 25(10):2245–2256, 2012.
  * Yao [1977] Andrew Chi-Chih Yao.  Probabilistic computations: Toward a unified measure of complexity (extended abstract).  In _18th Annual Symposium on Foundations of Computer Science_ , pages 222–227. IEEE Computer Society, 1977.

##  Appendix A Maximization under cardinality constraint

We study the sample complexity maximizing the value of a valuation
$f:2^{[n]}\rightarrow\mathbb{R}$ subject to a cardinality constraint $k$,
i.e., to find $\arg\max_{|S|=k}f(F)$. For simplicity, we assume (with loss of
generality) that the $f$ is capped in $k$ items, i.e, the value for a bundle
$S$ of size larger than $k$ is exactly

$f(S)=\max_{\begin{matrix}T\subset S,~{}|T|=k\end{matrix}}f(T).$

Observe that under this assumption, the value of the grand bundle is the same
as the value of an optimal bundle of size $k$, and every value query for a
bundle $S$ hinged whether or not the set contains an optimal solution. We
identify every optimal solution with an hyper-edge of dimension $k$ in an
hyper-graph with $n$ vertices. For $k=2$, we receive a graph $G$ where any
edge in the graph is a feasible solution of the maximization problem, and the
connection to the edge-finding-problem discussed in this paper is clear.

We now focus on the following family of valuations called OXS, and ask for the
number of non-adaptive value queries needed in order of solving the
maximization problem.

######  Definition 4.

A function $f:2^{[n]}\rightarrow\mathbb{R}$ is an assignment function (OXS) if
$f$ is the convolution of $r$ unit-demand functions $u_{1},\ldots,u_{r}$:
$f(S)=\bigvee_{i\in[r]}u_{i}(S):=\max_{\mathbin{\mathaccent
0{\cdot}\cup}_{i\in[r]}{S_{i}}=S}\sum_{i\in[r]}{u_{i}(S_{i})}$, where the sets
$S_{1},\ldots S_{r}$ are a partition of $S$.

When limiting ourself to OXS valuations characterized by two unit-demand
valuations, i.e., $r=2$, we observe that the capping at $k=2$ property
trivially holds, and that the graph induced by an OXS valuations has a special
form: it belongs to the family of Overlapping-Product graphs defined in
Section 3.

######  Proposition 1.

Given an OXS valuation $f$ described by two unit-demand valuations, the graph
induced by pairs of items of maximal value as a bundle is an Overlapping-
Product graph.

###### Proof.

By definition there exist two unit-demand valuations $u_{1},u_{2}$ such that
$f(S)=\bigvee_{i\in[2]}u_{i}(S)$. Let $A_{i}^{j}$ be the set of items of $j$th
highest values in $u_{i}$, and denote the value of item in $A_{i}^{j}$ by
$a_{i}^{j}$.

If there exist a pair $x\neq y$ such that $x\in A_{1}^{1}$ and $y\in
A_{2}^{1}$, then in any maximal pair both valuations are maximized and a pair
$r,s$ is maximizing $f$ if and only if one of them belongs to $A_{1}^{1}$ and
the other to $A_{2}^{1}$ (might be the case that some of them belong to both
sets). This is an Overlapping-Product graph with those sets.

In no such pair exists, we have that $A_{1}^{1}=A_{2}^{1}$ and this set is a
singleton. In this case, any maximizing pair includes this item with addition
of an item from some set ( either $A_{1}^{2}$, $A_{2}^{2}$ or their union,
depending on the values of $a_{1}^{2}$ and $a_{2}^{2}$.). This is also an
Overlapping-Product graph (in fact, this is a star graph). ∎

An immediate corollary is that the non-adaptive complexity of maximizing an
OXS valuation with cardinality constraint $k=2$, is at most
$\mathcal{O}\left(n\log n\right)$.

##  Appendix B Missing Proofs

###  B.1 Explicit constructions for Proposition 4.1

######  Lemma 9.

There exist a deterministic IS algorithm that for a Singleton graph, returns
the only $e\in E$, using $\lceil 4\log n\rceil$ non-adaptive deterministic
queries.

###### Proof.

We name the vertices of $V$ using $k=\lceil\log n\rceil$ bits, define

$F_{i}^{b}=\left\\{v\in V\mid\text{the $i$-th bit of $v$ is $b$}\right\\},$

and query

$\mathcal{F}=\left\\{F_{i}^{b}\mid i\in\left[\lceil\log n\rceil\right],\
b\in\left\\{0,1\right\\}\right\\}.$

Assuming $G$ has a single edge $\left\\{u,v\right\\}$, each positive answer
$Q(F_{i}^{b})$ ensures that $u$ and $v$ have the same value for this bit, and
its different otherwise. If we look at the vertices of $V$ as elements of the
filed $\mathbb{F}_{2^{k}}$, this set of answers encode an equation of the form
$u\oplus v=a$ for some $a\in\mathbb{F}_{2^{k}}$.

We now map each vertex $v\mapsto v^{-1}$ and query according to the new names.
That is, we have that

$H_{i}^{b}=\left\\{v\in V\mid\text{the $i$-th bit of $v^{-1}$ is
$b$}\right\\},$

and we query

$\mathcal{H}=\left\\{H_{i}^{b}\mid i\in\left[\lceil\log n\rceil\right],\
b\in\left\\{0,1\right\\}\right\\}.$

Hence, we can now deduce an equation of the form $u^{-1}\oplus v^{-1}=b$ for
some $b\in\mathbb{F}_{2^{k}}$.

The set of equations give the values of $u\oplus v$ and $u\cdot v$ and have a
unique solution up to switching $u$’s and $v$’s names.

By additionally querying $Q(V)$, we can verify that $E$ is not empty. ∎

For cases in which it is known that $G$ is star graph with center at a known
vertex $v$, we describe an algorithm that uses $\lceil 2\log n\rceil$ queries
for the same problem.

######  Lemma 10.

There exist a deterministic IS algorithm that for a Star graph $G=(V,E)$ with
$m$ edges and a known center $v$, returns the only $e\in E$, if $m=1$, in case
that $m=0$ the algorithm returns the message ”$none$”, in case that $m>1$
returns the message ”$more\ than\ one$”, and it is implementable using $\lceil
2\log n\rceil$ non-adaptive deterministic queries.

###### Proof.

We name the vertices of $U$ using $\lceil\log n\rceil$ bits and query

$\mathcal{F}=\left\\{\left\\{v\right\\}\cup\left\\{u\in U\mid\text{the $i$-th
bit of $u$ is $b$}\right\\}\mid i\in[\lceil\log n\rceil],\
b\in\left\\{0,1\right\\}\right\\}.$

The positive answers encode the endpoint in $U$. If there is no such endpoint,
all answers would be negative. While if there are more then one such endpoint,
there is an index $i$ with positive answer for both values of $b$. Either way,
the algorithm identify this is the case and return the proper message. ∎

###  B.2 Proof of Lemma 4.2

See 4.2

###### Proof.

Given a set of queries, an adversary may build a fooling set in the following
way: We start with $G=(V,E)$, with $E=\binom{V}{2}$, the full graph over $V$
vertices. For every query $S$, let $E(S)$ be the set of edges with both
endpoints in $S$. While there still exist a set $S$ such that $|E(S)|$ of size
$1$, update $E(S^{\prime})\leftarrow E(S^{\prime})\setminus E(S)$ for all
$S^{\prime}$, and $E\leftarrow E\setminus E(S)$. That is, we guarantee that
the answer for the query $S$ is negative.

Since there are at most $\binom{n}{2}$ queries, and each set correspond to a
single edge removal, the process end with some set $E$ and for any $S$ we have
that $E(S)$ are either empty or contains at least two edges. In addition, $E$
is not empty.

According to the graph induced by $E$, the answers to the queries are negative
on any set $S$ such that $E(S)$ is empty, and positive for all other sets.
Hence, no deterministic algorithm can distinguish between the graphs induced
by $E$ and a graphed induced by $E\setminus\left\\{e\right\\}$ for any edge
$e\in E$, thus failing on at least one input. ∎

###  B.3 Tighter Upper Bounds for Cliques

See 5.3

###### Proof.

We describe three different algorithms, all using $\mathcal{O}\left(n\right)$
queries.

First, as in Lemma 2, we use a divide-and-conquer technique. We divide the set
$V$ into two disjoint sets $V_{1},V_{2}$, such that
$\left||V_{1}|-|V_{2}|\right|\leq 1$, and solve for each set recursively.
Since $G$ is a clique graph, if both $V_{1}$ and $V_{2}$ induce no edge, there
are at most one vertex from $S$ in either one. That is, the graph contains at
most one edge and it can be found by querying ${\mathcal{L}}\left(V\right)$
according to the construction in Appendix B.1. the total number of queries
$f(n)$ is then following the formula:

$f(n)=f\left(\left\lceil\frac{n}{2}\right\rceil\right)+f\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+\lceil
4\log n\rceil+1.$

Using Akra–Bazzi theorem [3], we have that $f(n)={\Theta}\left(n\right)$.

For the other two algorithms, we start by naming the vertices arbitrarily
$1,\ldots,n$ and querying,

$\mathcal{F}_{1}=\left\\{\left\\{1,\ldots,i\right\\}\mid
i\in[n]\right\\}\quad\mathcal{F}_{2}=\left\\{\left\\{i,\ldots,n\right\\}\mid
i\in[n]\right\\}.$

Since $V$ is in both sets, the total number of queries is exactly $2n-1$.

We can now identify the second smallest and second largest indexes of vertices
of the Clique, those are the vertices that correspond to the first positive
answer in $\mathcal{F}_{1}$ and the last positive answer in $\mathcal{F}_{2}$,
respectively. If they are not identical, the algorithm found an edge. The only
case in which those vertices are the same, is when the clique size is exactly
three. In this case, only one of the clique’s vertices is known.

We find a second vertex using one of the following two schemes. We may query:

$\mathcal{F}_{3}=\left\\{\left\\{{i},\ldots,{(i+\lfloor\frac{n}{2}\rfloor\mod
n)}\right\\}\mid i\in[n]\right\\}.$

Let $S_{\ell}=\left\\{1,...,\lfloor\frac{n}{2}\rfloor\right\\}$ and
$S_{h}=\left\\{\lceil\frac{n}{2}\rceil+1,...,n\right\\}$. If $n$ is even, one
of the sets contains at least two vertices of the clique while the other
contains at most one. That is, for some of the sets in $\mathcal{F}_{3}$ the
answer is positive and for some are not, and we can identify two of the
clique’s vertices by the phase shift in answers. If $n$ is odd, we still have
that either $S_{\ell}$ or $S_{h}$ contains at most one of the clique vertices.
If one of them contains at least two vertices, we continue as before,
otherwise we have that $\lceil\frac{n}{2}\rceil$ is part of the clique. In the
later case, the only way that $\lceil\frac{n}{2}\rceil$ is not included in a
positive query is if the other two vertices are $1$ and $n$. But then, the
query $\left\\{n,1,\ldots,\lfloor\frac{n}{2}\rfloor-1\right\\}$ is positive,
and again we can identify two of the clique’s vertices by the phase shift in
answers. This algorithm has a total query complexity of $3n$.

Another option is to use a similar technique as in Proposition 4.1 for finding
a single edge, and use it to find all three edges of the graph. As before, we
ask $2n$ queries in order to identify one of the clique vertices. In addition,
we build a randomized set of queries by sampling $t=64\ln n$ sets of vertices
according to ${\mathcal{U}}_{\frac{1}{2}}\left(V\right)$. Assuming the
vertices of the clique are $\left\\{a,b,c\right\\}\in V$, for every sample
$S$, it holds that $Q(S)$ is positive if and only if at least two of the
vertices are in $S$. Assume $a$ is known from the first part of the algorithm.
For every vertices $a,b,c,d\in V$, the probability that $a,d\in S$ and
$b,c\notin S$ is $\frac{1}{16}$, and the probability that this would not hold
any samples is

$\left(1-\frac{1}{16}\right)^{t}<n^{-4}.$

Whenever we have a negative answer that includes $a$, we are guaranteed that
any $d\in S$ is not a part of the clique. Taking a union bound over all
possible $a,b,c,d\in V$, gives that with positive probability, using $t$
samples, for any Clique graph $\left\\{a,b,c\right\\}$, we can rule out all
other vertices as being part of an edge. Hence, there exist some selection of
the $t$ queries that is always correct, and we can find the edge
deterministically using $t$ queries and the total number of queries is
$2n+64\ln n$.

∎

###  B.4 Fully Adaptive Binary Search

######  Lemma 11.

There exist a deterministic $\lceil\log n\rceil$-adaptive algorithm for
finding an edge using $6$ queries at each round.

###### Proof.

By adding dummy vertices, we may assume that $n$ is power of $2$. We prove our
claim by induction. For $n\leq 4$, the algorithm simply query all possible
pairs. For general $n>4$, we split the vertices arbitrarily into $4$ equal
size sets $V_{1},...,V_{4}$, and query all $6$ queries of the form
$Q(V_{i}\cup V_{j})$ for $\left\\{i,j\right\\}\in\binom{[4]}{2}$. Any edge in
the graph is contained in at least one such query, and we can continue with
any positive answer while removing half of the vertices. Thus, having $\log
n-1$ total rounds. ∎