ajecc's blog

How to solve this graph problem?
By ajecc, history, 7 years ago, In English

You are given a graph and a number k. Output the biggest set of nodes such as every node has at least k adjacent nodes that are also in the set. (The solution should have a better complexity than O(n^2), n = number of nodes) Thanks!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +18 Vote: I do not like it

A constructive solution works. We take a candidate set S, which starts as the whole graph, and iteratively reduce it removing invalid nodes until we arrive at the solution. At each point, if some node in S has less than k adjacent nodes in S, remove it and decrease the degree of all nodes adjacent to it by 1.

This works because every node you remove has no chance to be in the solution set, and the final set will be a solution.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I understand, but what is the complexity of this algorithm? I have a hard time figuring out :\

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      It can be done similar to BFS in O(n + m) time.

      → Reply