In sociology, one often studies a graph G in which nodes represent people and edges repres...

In sociology, one often studies a graph G in which nodes represent people and edges represent those who are friends with each other. Let's assume for purposes of this question that friendship is symmetric, so we can consider an undirected graph.

Now suppose we want to study this graph G, looking for a "close-knit" group of people. One way to formalize this notion would be as follows. For a subset S of nodes, let e(S) denote the number of edges in S–that is, the number of edges that have both ends in S. We define the cohesiveness of S as e(S)/|S|. A natural thing to search for would be a set S of people achieving the maximum cohesiveness.

(a) Give a polynomial-time algorithm that takes a rational number a and determines whether there exists a set S with cohesiveness at least α.

(b) Give a polynomial-time algorithm to find a set S of nodes with maximum cohesiveness.