On set expansion problems and the small set expansion conjecture ?
We study two problems related to the Small Set Expansion Conjecture(Raghavendra and Steurer, 2010): the Maximum weightm? m ? -edge cover(MWEC)problem and the Fixed cost minimum edge cover(FCEC)problem. In the MWEC problem, we are given an undirected simple graph G=(V,E) G = ( V , E ) with integral vertex weights. The goal is to select a set U?V U ? V of maximum weight so that the number of edges with at least one endpoint in U U is at most m? m ? . Goldschmidt and Hochbaum (1997) show that the problem is NP-hard and they give a 3-approximation algorithm for the problem. The approximation guarantee was improved to 2+? 2 + ? , for any fixed ?>0 ? > 0 (Liang, 2013). We present an approximation algorithm that achieves a guarantee of 2. Interestingly, we also show that for any constant ?>0 ? > 0 , a (2??) ( 2 ? ? ) -ratio for MWEC implies that the Small Set Expansion Conjecture(Raghavendra and Steurer, 2010) does not hold. Thus, assuming the Small Set Expansion Conjecture, the bound of 2 is tight. In the FCEC problem, we are given a vertex weighted graph, a bound k k , and our goal is to find a subset of vertices U U of total weight at least k k such that the number of edges with at least one edge in U U is minimized. A 2(1+?) 2 ( 1 + ? ) -approximation for the problem follows from the work of Carnes and Shmoys (2008). We improve the approximation ratio by giving a 2-approximation algorithm for the problem and show a (2??) ( 2 ? ? ) -inapproximability under Small Set Expansion Conjecture. Only the NP-hardness result was known for this problem (Goldschmidt and Hochbaum, 1997). We show that a natural linear program for FCEC has an integrality gap of 2?o(1) 2 ? o ( 1 ) . We also show that for any constant ?>1 ? > 1 , an approximation guarantee of ? ? for the FCEC problem implies a ?(1+o(1)) ? ( 1 + o ( 1 ) ) approximation for MWEC . Finally, we define the Degrees density augmentation problem which is the density version of the FCEC problem. In this problem we are given an undirected graph G=(V,E) G = ( V , E ) and a set U?V U ? V . The objective is to find a set W W so that (e(W)+e(U,W))/deg(W) ( e ( W ) + e ( U , W ) ) / d e g ( W ) is maximum. This problem admits an LP-based exact solution (Chakravarthy etal., 2012). We give a combinatorial algorithm for this problem.
small set expansion edge covering dense graphs