Could I please get help with this Critical Node problem?

Thank you

Given an undirected graph G = (V, E), for any subset of nodes S V we can construct a graph GS from G by removing all nodes in S together with their incident edges. In the critical node problem (CNP), we are given an integer 1 k |V | and need to find a subset S of size k such that the graph GS has the minimum pair-wise connectivity. Here pairwise connectivity of a graph is defined as the number of pairs of connected vertices in the graph.

Input: The file cnp.in includes multiples lines. The first line contains three integers 1 n 1000, 1 m 100000 and 1 k n that correspond to the number of nodes, edges, and the size of S. Each of the following m lines contain two integers u and v, separated by one space, to denote an edge from u to v. Nodes are numbered from 1 to n.

Output: The file cnp.out contains exactly 2 lines. The first line contains an integer P that is the minimum pairwise connectivity of GS. The second line contains exactly k integers which are the id of the nodes in S.

Explain of the output: After removing two nodes 3 and 4 and their incident edges from the graph, we obtain a graph GS with two connected components C1 = {1, 2} and C2 = {5, 6, 7}. The number of connected pairs in the component C1 and C2 are one and three, respectively. Thus the total number of connected pairs (pairwise-connectivity) is 4.

I. Your program in Java/C++ that solves the above problem following the above input/output format. A makefile and/or compiling instruction should be included if you have multiple source files. Your program should not take more than 5 minutes to terminate on any graph within the limits described in the Input section.

II. A report outline the results of your program on random graphs and different k values. The report should have at least two parts. In the first part, you fix k = 5 and run your program for graphs of sizes 50, 100,..., 500. In the second parts, you run your program on a random graph of size 100 and output the pairwise connectivity in GS when k = 5, 10, ..., 50. For each run, output the number of nodes, edges, the number k, and the pairwise connectivity of GS.

Sample input/output: cnp.n cnp. out 7112 12 34 13 14 24 34 35 36 46 56 57 67 123444566677 711123334556