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?