A simple variant of node connectivity is NP-complete

References

• Chin , F. and Ramarao , K.V.S. 1986 . Optimal termination protocols for network partitioning . SIAM J. on Computing , February To appear
   Web of Science ®Google Scholar
• Chin F. Ramarao K. V. S. An information-based model for failure-handling in distributed database systems University of Pittsburgh Pittsburgh, PA To appear in IEEE Tr. on Software Engg. Also, available as Tech. Rep. of Dept. of Computer Science
   Google Scholar
• Dantzig , G.B. and Fulkerson , D.R. 1956 . “ On the max-flow min-cut theorem of networks, Linear Inequalities and Related Systems ” . In Annals of Math. Study , Vol. 38 , 215 – 221 . Princeton, NJ : Princeton University Press .
   Google Scholar
• Even , S. 1975 . An algorithm for determining whether the connectivity of a graph is at least k . SIAM J. on Computing , 4 ( 3 ) : 393 – 396 .
   Google Scholar
• Even , S. and Tarjan , R.E. 1975 . Network flow and testing graph connectivity . SIAM J. on Computing , 4 ( 4 ) : 507 – 518 .
   Google Scholar
• Galil , Z. 1980 . Finding the vertex connectivity of graphs . SIAM J. on Computing , 9 ( 1 ) : 197 – 199 .
   Web of Science ®Google Scholar
• Garey , M.R. and Johnson , D.S. 1979 . Computers and Intractability , San Francisco : Freeman and Company .
   Google Scholar
• Krishnamoorthy , M.S. and Deo , N. 1979 . Node-deletion NP-Complete problems . SIAM J. on Computing , 8 ( 4 ) : 619 – 625 .
   Web of Science ®Google Scholar
• Lewis , J.M. and Yannakakis , M. 1980 . The node-deletion problem for hereditary properties is NP-Complete . J. of Comp. Sys. Sci , 20 : 219 – 230 .
   Web of Science ®Google Scholar
• Skeen , D. and Stonebraker , M. 1983 . A formal model of crash recovery in a distributed system . IEEE Tr. on Software Engg. SE , SE9 ( 3 ) : 219 – 228 .
   Web of Science ®Google Scholar
• Yannakakis , M. 1981 . Edge-deletion problems . SIAM J. on Computing , 10 ( 2 ) : 297 – 309 .
   Web of Science ®Google Scholar