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. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
