IIT Kanpur Sample Test Paper

Question

Given an undirected graph with vertices as your friends and  edges between people who do not  talk  to each other. Your task is to invite as many guests to your party  such that there are no two friends at the party who have problem talking to each other. This problem is an instance of:
A. Maximum vertex  cover.
B. Maximum cut.
C. Maximum eigenvalue of adjacency matrix.
D. None of the above.

Answer 1

Answer is D.

This problem is finding the largest maximal independent set or maximum independent set.

Independent Set : Given an undirected Graph G = (V,E) an independent set is a subset of nodes U ⊆ V , such that no two nodes in U are adjacent. 

Maximum Independent set: An Independent set of maximum cardinality is known as maximum independent set.

Maximal Independent set: An independent set that is not the subset of another independent set is called maximal.

Comments

YEs correct.But what does maximal vertex cover means?In max. vertex set i can always include all the vertices.

Similarly b option.I can include all the edges.

Does option a and b has any usage?

---

Yes i agree with you.

i don't think option a and b have any relevance to the problem.