Given an undirected graph $G$, the $k$-core of $G$ is defined as the maximal subgraph such that each vertex has at least $k$ neighbors in the subgraph. The cores of $G$ can be computed by the following algorithm, which computes the $k$-core by iteratively removing vertices with degree $< k$.

1: $ k \leftarrow 1$;

2: while $G$ is not empty:

3: $\ $ $\ $ while there is a vertex $v$ with degree $< k$:

4: $\ $ $\ $ $\ $ $\ $ decrease by $1$ the degree of the neighbors of $v$ in $G$;

5: $\ $ $\ $ $\ $ $\ $ remove $v$ from $G$;

6: $\ $ $\ $ $k \leftarrow k + 1$;

An order that the vertices are removed in line 5 is called a degeneracy order. There can be multiple degeneracy orders for $G$ due to the tie in line 3.

Question. I want to uniformly sample a degeneracy ordering for $G$. I wonder if this is a known question in the community. I have googled it but found nothing. Is there an efficient algorithm for this task?

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.