Testing k-edge-connectivity of digraphs

This paper presents an algorithm that tests whether a given degree-bounded digraph is k-edge-connected or ɛ-far from k-edge-connectivity. This is the first testing algorithm for k-edgeconnectivity of digraphs whose running time is independent of the number of vertices and edges. A digraph of n vertices with degree bound d is ɛ-far from k-edge-connectivity if at least ɛdn edges have to be added or deleted to make the digraph k-edge-connected, preserving the degree bound. Given a constant error parameter ɛ and a degree bound d, our algorithm always accepts all k-edge-connected digraphs and rejects all digraphs that is ɛ-far from k-edge-connectivity with probability at least 2/3. It runs in $ Oleft( {dleft( {frac{c} {{varepsilon d}}} right)^k logfrac{1} {{varepsilon d}}O} right) $ Oleft( {dleft( {frac{c} {{varepsilon d}}} right)^k logfrac{1} {{varepsilon d}}O} right) (c > 1 is a constant) time when input digraphs are restricted to be (k-1)-edge connected and runs in $ Oleft( {dleft( {frac{{ck}} {{varepsilon d}}} right)^k logfrac{k} {{varepsilon d}}O} right) $ Oleft( {dleft( {frac{{ck}} {{varepsilon d}}} right)^k logfrac{k} {{varepsilon d}}O} right) (c > 1 is a constant) time for general digraphs.