Testing connectivity of faulty networks in sublinear time

Given a set F of vertices of a connected graph G  , we study the problem of testing the connectivity of G−FG−F in polynomial time with respect to |F||F| and the maximum degree Δ of G  . We present two approaches. The first algorithm for this problem runs in O(|F|Δ2ε−1log(|F|Δε−1))O(|F|Δ2ε−1log(|F|Δε−1)) time for every graph G   with vertex expansion at least ε>0ε>0. The other solution, designed for the class of graphs with cycle basis consisting of cycles of length at most l  , leads to O(|F|Δ⌈l/2⌉log(|F|Δ⌊l/2⌋))O(|F|Δ⌈l/2⌉log(|F|Δ⌊l/2⌋)) running time. We also present an extension of this method to test the biconnectivity of G−FG−F in O(|F|Δllog(|F|Δl))O(|F|Δllog(|F|Δl)) time.