Report

Example Question on Linear Program, Dual and NP-Complete Proof COT5405 Spring 11 Question • Given an undirected connected graph G = (V,E) and a positive integer k ≤ |V|. • Two vertices u and v are connected if and only if there exists at least one path from u to v. • For all the possible vertex pairs, we want to remove k vertices from G, so that • the number of connected vertex pairs in the resulting graph is minimized. • We call it k-CNP (critical node problem) Integer Program • Variables: – uij = 1 if vertex i and j are connected in the resulted graph, otherwise uij = 0. Note uii = 1. – vi = 1 if vertex i is removed, otherwise vi = 0. • The objective function and 2 constraints m in 1 2 u ij i , j V (i , j ) E , u i j vi v j 1 v iV i k vi vj uij 1 1 0 1 0 0 0 1 0 0 0 1 Leftover Connectivity • Consider node pairs i and j, where (i,j) is NOT an edge. u ij u jh u hi 1, ( i , j , h ) V h i j Uij Ujh Uhi 1 1 1 1 0 0 0 1 0 0 0 X h i j Final Formulation LP relaxation Dual M in c j X M ax j j s .t . a yb i i i ij X j bi for all i j s .t . ya i ij cj for all j 0 for all i i X j 0 for all j yi M in ( 1 1 1 1 , , , 2 2 2 2 1 2 )( u 1 2 u 1 3 u n 1, n ) ' n 2 s .t . 1 1 1 1 0 n 2 0 0 0 0 n 0 0 0 0 0 1 1 0 |E| rows 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 n 3 row s 3 0 0 0 0 0 0 0 0 0 1 1 row u 12 u1 3 u 23 0 0 u n 1, n 0 v1 vn 1 1 1 1 1 k Ready to write dual • How many constraints in Primal – n • How many constraints in Dual – 2 n (3 | E | 1)dim ension in total • Dual variable 3 n 3 | E | 1 3 – For the constraint on (i,j) belonging to E, define xij – For the constraint on i,j,h belonging to V, define yijh – For the constraint on the aggregate vi, define z M ax (1,1, , 1, 1, 1 , k )( x12 y123 z) ' n 3 | E | 1 3 s .t . 1 0 0 1 1 0 0 n 3 3 |E | 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 x 12 0 x13 0 y 123 y 312 1 y132 1 1 1 z 1 2 1 2 1 2 1 2 1 2 0 0 0 Final Dual NP-Complete Proof • Decision Version – Given an undirected connected graph G and positive integer k – a value L<n(n-1)/2 – is there a set of k vertices, whose removal makes the number of connected vertex pairs in the resulting graph is at most L? In NP • Given such a set of k vertices, • Remove them from the graph, • Calculate the number of connected pairs using DFS or BFS in polynomial time, • Compare with L – Give answer: Yes or No Is NP-hard Reduction from Vertex Cover (VC) • Instance of VC: given a graph G = (V,E) where |V|= n, is there a vertex cover of size at most k? • Instance of k-CNP: on the graph G, is there a set of k vertices whose removal makes the # of connected pairs 0? Is NP-hard • Forward: If we can have a VC of size k ---> delete those k nodes ---> connectivity = 0 • Backward: If we can delete k nodes to make # connections 0 --> no edges left -> vertex cover of size k NP-Completeness • In NP • NP-hard • For an alternative proof, please refer to A. Arulselvan et al, ``Detecting Critical Nodes In Sparse Graphs’’, J. Computers and Operations Research, 2009. http://plaza.ufl.edu/clayton8/cnp.pdf Thank You Q&A