A connected component in an undirected graph is a subgraph C with these two properties: C' is connected, and no edges exist between nodes in C and nodes outside C. We consider the following problem of splitting a graph into small pieces by deleting some nodes: Given a graph G = (V,E) and an integer c, delete a subset U CV of nodes (and all their incident edges) from G such that, in the remaining graph, every connected component has at most c nodes, and the size U is as small as possible. The problem appears, e.g., in data analysis, where the nodes represent data items, an edge means similarity, and the data shall be partitioned into small clusters, thereby neglecting as few data as possible. Describe an algorithm that solves this problem in O*((c+1)*) time or better, and argue why your proposed algorithm is correct. Hint: It can be helpful to consider the special case c = 1 first, and then generalize your insights to any fixed c.

A connected component in an undirected graph is a subgraph C with these two properties: C' is connected, and no edges exist between nodes in C and nodes outside C. We consider the following problem of splitting a graph into small pieces by deleting some nodes: Given a graph G = (V,E) and an integer c, delete a subset U CV of nodes (and all their incident edges) from G such that, in the remaining graph, every connected component has at most c nodes, and the size U is as small as possible. The problem appears, e.g., in data analysis, where the nodes represent data items, an edge means similarity, and the data shall be partitioned into small clusters, thereby neglecting as few data as possible. Describe an algorithm that solves this problem in O((c+1)) time or better, and argue why your proposed algorithm is correct. Hint: It can be helpful to consider the special case c = 1 first, and then generalize your insights to any fixed c.