Suppose $G$ is a d-regular graph with $n$ vertices, such that $\log n$ is much smaller than $d$. Suppose we create a set $S$ of vertices such that $|S| = \frac{n \log n}{d}$. For every vertex in the graph, suppose we have kept track of the $\log n$ lowest-ranked vertices. Note that, this can be random because the ordering of the $n$ vertices is arbitrary, to begin with. Now we define $S$ to be the set of first $\frac{n \log n}{d}$ vertices.
Now only looking at the vertices of $S$, we start a decomposition of the graph $G$. We proceed in the order of vertices as they are numbered. Start with one vertex $v$ and look at the neighborhood of $v$, calling it $N(v)$. We call this $v \cup N(v)$ one cluster/partition of the graph. We delete all the vertices and edges involved with vertices in this cluster from $G$. Then pick the next lowest ranked vertex in $S$ and repeat until $S$ is empty.
Observe that our ordering was arbitrary to begin with, so the resulting graph and vertex numbers will be different in various runs of the procedure. But, on average(or maybe with high probability)what is known about the following questions?
- When our procedure ends and $S$ is empty, have we partitioned the whole graph $G$, i.e. have we deleted everything? Please note that I am not asking about a particular case. I want to understand what will it look like in an average case.
- I mentioned that maybe $d$ is very large and we are not able to store the whole $G$. In that case, we know $\log n$ neighbors of each vertex and in the clustering procedure at each step, we delete those $\log n$ neighbors of $v$ along with their edges. In this case, I ask the same question again. When our procedure ends and $S$ is empty, have we partitioned the whole graph $G$?
- Lastly, if $G$ was not a $d$ regular graph at all, but an arbitrary graph and $d$ is just the average degree of all vertices, then is it possible to say something about the previous questions?
I will really appreciate any answer, hint, or maybe some research papers which have introduced techniques to handle this kind of problem.