We study two problems related to the Small Set Expansion Conjecture [
14]: the
Maximum weight
\(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)\) with integral vertex weights. The goal is to select a set
\(U\subseteq V\) of maximum weight so that the number of edges with at least one endpoint in
\(U\) is at most
\(m'\). Goldschmidt and Hochbaum [
8] show that the problem is NP-hard and they give a
\(3\)-approximation algorithm for the problem. The approximation guarantee was improved to
\(2+\epsilon \), for any fixed
\(\epsilon > 0\) [
12]. We present an approximation algorithm that achieves a guarantee of
\(2\). Interestingly, we also show that for any constant
\(\epsilon > 0\), a
\((2-\epsilon )\)-ratio for
MWEC implies that the Small Set Expansion Conjecture [
14] 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 edges in
\(U\) is minimized. A
\(2(1+\epsilon )\)-approximation for the problem follows from the work of Carnes and Shmoys [
3]. We improve the approximation ratio by giving a
\(2\)-approximation algorithm for the problem and show a
\((2-\epsilon )\)-inapproximability under Small Set Expansion Conjecture conjecture. Only the NP-hardness result was known for this problem [
8]. We show that a natural linear program for
FCEC has an integrality gap of
\(2-o(1)\). We also show that for any constant
\(\rho >1\), an approximation guarantee of
\(\rho \) for the
FCEC problem implies a
\(\rho (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\subseteq 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 [
4]. We give a combinatorial algorithm for this problem.