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.


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.

  • $\begingroup$ Thanks for the answer, but I must be missing something. Consider a graph with many vertices and only $k=2$ edges (say, $a,b$ are connected to a shared vertex $c$). Now if the randomly chosen subset $T$ contains $c$ but not $a,b$, then you'll end up with a vertex cover of $\{a,b\}$, right? so your method won't succeed in finding the VC $\{c\}$. Your solution might find a VC of size $\le k$, but I don't see a reason for it to find the minimal $VC$, which is what I'm after. $\endgroup$ – R B Jul 16 '17 at 11:23
  • $\begingroup$ @RB, Are you looking for a maximum independent set or a maximal independent set? The problem says the latter, but your comment makes it sound like you actually want the former. If so, I suggest you edit the question to ask about maximum independent set rather than maximal independent set. $\endgroup$ – D.W. Jul 16 '17 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.