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 [email protected].
