TY - JOUR

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

AU - Gandhi, Rajiv

AU - Kortsarz, Guy

N1 - 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

U2 - 10.1016/j.dam.2015.05.028

DO - 10.1016/j.dam.2015.05.028

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:84940722139

SN - 0166-218X

VL - 194

SP - 93

EP - 101

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -