Detecting and Characterizing Small Dense Bipartite-like Subgraphs by the Bipartiteness Ratio Measure

Abstract

We study the problem of finding and characterizing subgraphs with small \textit{bipartiteness ratio}. We give a bicriteria approximation algorithm \verb|SwpDB| such that if there exists a subset $S$ of volume at most $k$ and bipartiteness ratio $\hat{I}¸$, then for any $0<\hat{I}\mu <1/2$, it finds a set $S^{\prime }$ of volume at most $2k^{1+\hat{I}\mu }$ and bipartiteness ratio at most $4\sqrt{\hat{I}¸/\hat{I}\mu }$. By combining a truncation operation, we give a local algorithm \verb|LocDB|, which has asymptotically the same approximation guarantee as the algorithm \verb|SwpDB| on both the volume and bipartiteness ratio of the output set, and runs in time $O(\hat{I}{\mu }^2\hat{I}{¸}^{-2}{k}^{1+\hat{I}\mu }{\ln }^{3}k)$, independent of the size of the graph. Finally, we give a spectral characterization of the small dense bipartite-like subgraphs by using the $k$th \textit{largest} eigenvalue of the Laplacian of the graph.

17 pages; ISAAC 2013