Question

Problem 1: Given a graph G (V,E) a subset U S V of nodes is called a node cover if each edge in E is adjacent to at least one node in U. Given a graph, we do not know how to find the minimum node cover in an efficient manner. But if we restriet G to be a tree, then it is possible. Give a greedy algorithm that finds the minimum node cover for a tree. Analyze its correctness and running time. A tree if a connected graph with no cycles, i.e. where any pair of nodes is connected by a simple path.

Answer 1

            U = Ø

            while(E != Ø )

                        choose a vertex v ∈ V having maximum degree in all the remaining unvisited                                              vertices

                        U = U ∪ {v}

                        E ← E - {e ∈ E : v ∈ e}

Return U

• This algorithm accepts a graph G.
• Initially define set U as an empty set which will later contain all the vertices in node cover.
• While loop iterates over all the edges and in each iteration performs following tasks:
  • Select a vertex from all the unvisited vertices which has maximum degree i.e. vertex with highest number of edges incident on it. Call this vertex v.
  • Add this vertex to the set of node cover U
  • Remove all the edges which incidents on v from the set E of edges.
• Loop stops when all E becomes Ø meaning all the edges have been visited by the node cover.
• Return set U containing node cover.
• Time Complexity of above algorithm is O(V + E).