TY - JOUR

T1 - On set expansion problems and the small set expansion conjecture

AU - Gandhi, Rajiv

AU - Kortsarz, Guy

N1 - Funding Information:
We thank V. Chakravarthy for introducing the FCEC problem to us. We also thank V. Chakravarthy and S. Roy for useful discussions. Thanks also to U. Feige for bringing the Small Set Expansion Conjecture to our attention. This work has been Supported in part by NSF awards 1050968 and 1218620. This work was started when the first author was visiting IBM Research, New Delhi. India.
Publisher Copyright:
© 2015 Elsevier B.V.

PY - 2015/10/30

Y1 - 2015/10/30

N2 - We study two problems related to the Small Set Expansion Conjecture (Raghavendra and Steurer, 2010): the Maximum weightm′-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) with integral vertex weights. The goal is to select a set U V of maximum weight so that the number of edges with at least one endpoint in U is at most 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+ε, for any fixed ε>0 (Liang, 2013). We present an approximation algorithm that achieves a guarantee of 2. Interestingly, we also show that for any constant ε>0, a (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, and our goal is to find a subset of vertices U of total weight at least k such that the number of edges with at least one edge in U is minimized. A 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-ε)-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). We also show that for any constant ρ>1, an approximation guarantee of ρ for the FCEC problem implies a ρ(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) and a set U V. The objective is to find a set W so that (e(W)+e(U,W))/deg(W) is maximum. This problem admits an LP-based exact solution (Chakravarthy et al., 2012). We give a combinatorial algorithm for this problem.

AB - We study two problems related to the Small Set Expansion Conjecture (Raghavendra and Steurer, 2010): the Maximum weightm′-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) with integral vertex weights. The goal is to select a set U V of maximum weight so that the number of edges with at least one endpoint in U is at most 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+ε, for any fixed ε>0 (Liang, 2013). We present an approximation algorithm that achieves a guarantee of 2. Interestingly, we also show that for any constant ε>0, a (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, and our goal is to find a subset of vertices U of total weight at least k such that the number of edges with at least one edge in U is minimized. A 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-ε)-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). We also show that for any constant ρ>1, an approximation guarantee of ρ for the FCEC problem implies a ρ(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) and a set U V. The objective is to find a set W so that (e(W)+e(U,W))/deg(W) is maximum. This problem admits an LP-based exact solution (Chakravarthy et al., 2012). We give a combinatorial algorithm for this problem.

KW - Dense graphs

KW - Edge covering

KW - Small set expansion

UR - http://www.scopus.com/inward/record.url?scp=84940722139&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84940722139&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2015.05.028

DO - 10.1016/j.dam.2015.05.028

M3 - Article

AN - SCOPUS:84940722139

VL - 194

SP - 93

EP - 101

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -