So I came across this problem that I would like help solving/explaining:

We have a graph with arboricity a (can be partitioned to a min of a trees). We run the following algorithm on the graph: - All vertexes are marked active at start time. - In every round i, from i=1 and forth, each vertex with utmost 3a active neighbors will be removed from the graph to sub-set H_i and is marked inactive.

A- How many active vertexes will remain after O(log(a)) rounds?

B- What is the tight upper bound (Theta) on the max vertex size of the graph induced by the set of active vertexes after O(log(a)) rounds?


Your Answer

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

Browse other questions tagged or ask your own question.