What is known about learning a maximal independent set in a (very) sparse graph?

Question

Maximal independent set is known to be hard in many meanings (hard to approximate, $W[1]$-hard, etc.). But if the number of edges is very small, then the problem becomes simpler. Here, I'm interested in learning an independent set from an unknown graph.

Assume that we have an unknown sparse graph $G=(V,E)$ with at most $k\ll |V|$ edges ($k$ is given).

We want to find a maximal independent set for the graph using as few queries as possible, where Query$(S)$, for some $S\subseteq V$ returns 1 if $S$ is an independent set and $0$ otherwise.

For example, if $k=1$, we can find an independent set of size $n-1$ using $\Theta(\log n)$ queries.

What is the query complexity for general $k$?

If I want to learn the exact graph (rather than just a maximal independent set), is the query complexity similar?

For $k=1$ we can also find the edge using $\Theta(\log n)$ queries.

The run time of the algorithm here can be arbitrary, all I care about is the query complexity.

Answer 1

Roughly $O(k \log(n/k))$ queries suffice, in the regime you are talking about.

We can equivalently think of this as finding a minimal vertex cover for $G$, given ability to query whether a particular set is a vertex cover or not. The algorithm is as follows:

1. Let $S := V$ (the set of all vertices).

2. While $S$ is not a minimal vertex cover:

   • Pick a random subset $T \subseteq S$ of size $|T| = \lceil |S|/k \rceil$.
   • If $S \setminus T$ is a vertex cover, let $S := S \setminus T$.

Note that the final vertex cover will have size $\le k$.

How many iterations does this take to converge? Well, for $S \setminus T$ to be a vertex cover, $T$ must avoid all of the vertices in the final minimal vertex cover, so the probability that a $S \setminus T$ is a vertex cover is at least

$$\left(1 - {k \over |S|}\right)^{|T|} \approx \left(1 - {k \over |S|}\right)^{|S|/k} \approx 1/e.$$

In other words, there is a constant probability in each iteration that $S \setminus T$ is a vertex cover. Thus, the total number of iterations is proportional to the number of times that we succeed in reducing the size of $S$.

Each time that we successfully reduce the size of $S$, we multiply its size by a factor of $1 - 1/k$. We start with $n$ vertices, and end with about $k$ vertices, so the number of reductions $r$ satisfies

$$n \times \left(1 - {1 \over k}\right)^r = k,$$

or in other words,

$$r = {\log(k/n) \over \log(1 - 1/k)} \approx k \log(k/n).$$

Thus, we do a total of $O(k \log(k/n))$ iterations, i.e., a total of $O(k \log(k/n))$ queries. When the algorithm terminates, we have found a minimal vertex cover.

What is the cost of testing the termination condition? The algorithm terminates when we have already tried all possible subsets $T$ of $S$ and none of them can be removed from $S$ ($S \setminus T$ was not a vertex cover for any subset $T$ of size $\lceil |S|/k \rceil$). Note that we'll end with a vertex cover of size $\le k$, so in the last iterations, $|T|=1$, so it'll only take $O(k \log k)$ iterations before we've tried all possibilities for $T$. At that point the procedure terminates. So, this doesn't increase the total asymptotic running time.

You can think of this algorithm as a simple variant of delta debugging.