Maximum Independent Set on a Tree

Given a social graph that is guaranteed to be a tree, select the largest possible group of people such that no two selected people know each other. Follow-up: remove the tree guarantee. Requirements You are given a graph representing whether people know each other. The graph is guaranteed to be a tree. Return the maximum number of people you can select such that every selected pair does not know each other. Equivalently, find the maximum independent set size on a tree. Follow-up: if the graph is not guaranteed to be a tree, how would you solve or characterize the problem? The round also asks candidates to write code and test cases; interviewer-provided tests may be available. Notes Tree DP: for each node, compute two values: take[node] = 1 + sum(skip[child]); skip[node] = sum(max(take[child], skip[child])). The answer is max(take[root], skip[root]). If the graph is arbitrary, maximum independent set is NP-hard. For bipartite graphs it can be related to minimum vertex cover via Konig's theorem; for small graphs, bitmask DP or branch-and-bound is possible. Preparation Implement tree DP on an adjacency list with parent tracking. Write tests for a chain, star, single node, and balanced tree. Prepare the follow-up answer: arbitrary graph is NP-hard; name practical constrained alternatives rather than promising a polynomial exact solution.