Testing the Supermodular-Cut Condition
For a function \(f:2^{V} \to \mathbb {Z}_{+}\) on a finite set V with f(?)=f(V)=0, adigraph D=(V,A) is called f-connected if it satisfies the f-cut condition, that is, ? D (X)?f(X) for any X?V, where ? D (X) is the number of arcs from X to V?X. We show that, for any crossing supermodular function f, the f-connectivity can be tested with a constant number of queries in the general digraph model with average degree bound. As immediate corollaries, we obtain constant-time testers for k-edge-connectivity, rooted-(k,l)-edge-connectivity, and the property of having k arc-disjoint arborescences. We also give a corresponding result for the undirected case.
supermodularity property testing bounded-degree model