We describe a local algorithm for finding subgraphs with high density, according to a measure of density introduced by Kannan and Vinay [1999]. The algorithm takes as input a bipartite graph G, a starting vertex v, and a parameter κ and outputs an induced subgraph of G. It is local in the sense that it does not examine the entire input graph; instead, it adaptively explores a region of the graph near the starting vertex. The running time of the algorithm is bounded by O (δκ2), which depends on the maximum degree δ, but is otherwise independent of the graph. We prove the following approximation guarantee: for any subgraph S with κ vertices and density θ, there exists aset S'? S for which the algorithm outputs a subgraph with density ω(θ/ log δ) whenever v ∈ S' and κ ≥ κ'. We prove that S' contains at least half of the edges in S.
展开▼
