<p>I don't know if there is a suitable approximation algorithm for this problem, but I can provide a counter-example for your heuristic algorithm: <br/>
Assume G has 2*n vertices with weights <br/>
$$W(v_i) = w - \epsilon * i$$
Which in your algorithm will be sorted by this order:
$$v_1, v_2, ... v_{2n}$$
And there's an edge between $v_i$ and $v_j$ iff $\exists k : i-j = 2*k$<br/>
The resulting graph is the union of 2 cliques with size n<br/>
The algorithm alternates between these two, which means in every step a clique with exactly one vertex will be returned, yielding a final answer with weight:
$$2*n*w - \epsilon * n * (2*n+1)$$
But we know that the optimum weight is just $2*w - 3*\epsilon$ <br/>
So the approximation factor can be as big as $n/2$ (assuming that the graph has $n$ vertices) which is not very interesting because the obvious algorithm "Pick each vertex as a clique" has an approximation factor of $n$</p>

CC BY-SA 3.0
2017-07-28T12:11:44.427Z
2017-07-28T12:11:44.427Z
Pooya Shati
<p>Consider the following graph problem. We are given a graph $\mathcal{G} = (\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of vertices and $\mathcal{E}$ is the set of edges. For each vertex $V \in \mathcal{V}$, there is a weight $W(V)$. </p>

<p>For a clique $Q=(Q_V,Q_E)$ where $Q_v \subset \mathcal{V}$ and $Q_E \subset \mathcal{E}$, the weight of clique $Q$ is defined as $W(Q) = \max_{V \in Q_V}W(V)$. </p>

<p>Now, we want to find a set of cliques covering all vertices $\mathcal{V}$ such that the sum of weights of these cliques are minimum.</p>

<p><strong>In this problem NP-hard?</strong> 
I think since the graphs are general, when the weights are equal, then the problem become minimum clique cover problem in which we want to cover the graph $\mathcal{G}$ with minimum number of cliques. Since this problem is NP-hard, the problem with arbitrary weights is also NP-hard. Am I right?</p>

<p><strong>How can we find an approximation algorithm for this problem?</strong>
I think the most trivial algorithm that comes to mind is this but I don't know how good it is.</p>

<p>Sort the vertices based on their weights in decreasing order (the first one has the highest weight) and if two have the same weight we sort them based on the number of edges of them. Assume the sorted list of vertices is $V_1, \ldots, V_{10}$. Now, we start from the clique $C = V_1$ and check the list $V_2, \ldots, V_{10}$ from left to right. For each element, we check whether adding $V_j$ to $S$ results in a clique or not. If yes, we form a clique of $S$ and $V_j$, and remove $V_j$ from the list. We continue this process (now for $S = \{V_1,V_j\}$) until we reach the end of list $V_2, \ldots, V_{10}$. Now we remove the vertices of set S, from $V_1, \ldots, V_{10}$, and repeat the above procedure for the first element of $V_1, \ldots, V_{10}$ minus the set $V$.</p>

CC BY-SA 3.0
2017-07-26T07:25:13.697Z
Is this homework? Did you look at the special case where all vertices have unit-weight?
Gamow
CC BY-SA 3.0
2017-07-26T17:14:26.033Z
@Gamow No, it is not a class homework. I think since the graphs are general, when the weights are equal, then the problem become minimum clique cover problem in which we want to cover the graph $\mathcal{G}$ with minimum number of cliques. Since this problem is NP-hard, the problem with arbitrary weights is also NP-hard. Am I right?
m0_as
CC BY-SA 3.0
2017-07-26T17:17:13.993Z
@Gamow My main question is about finding a good approximation algorithm. I have one greedy algorithm in mind, but I don't know how good it is and how to find a approximation bound for that.
m0_as
CC BY-SA 3.0
2017-07-27T02:46:24.700Z
Indeed if all weights are equal to 1, then this is clique cover, and cannot be approximated better than a factor $n^{1-\varepsilon}$, for $n$ the number of vertices, and $\varepsilon > 0$ any constant.
Sasho Nikolov
CC BY-SA 3.0
2017-07-27T02:59:05.000Z
@SashoNikolov I am not familiar with this type of statement. Is the fact that complexity of approximation depends on $\epsilon$ hidden in the statement? I mean, if not, I guess we can make $\epsilon$ arbitrarily small, (like $\epsilon = 0.9999$), and get a very good approximation. So, I guess as we make $\epsilon$ smaller, the complexity goes higher. Right? In which order?
m0_as
CC BY-SA 3.0
2017-07-27T14:28:37.020Z
I think there is some confusion: I am saying that approximation is hard. I.e. for any $\varepsilon > 0$, it is NP-hard to approximate clique cover better than a factor $n^{1-\varepsilon}$. The complexity of the NP-hardness reduction increases as $\varepsilon$ goes to $0$. See http://www.theoryofcomputing.org/articles/v003a006/v003a006.pdf
Sasho Nikolov
<graph-theory><graph-algorithms><np-hardness><approximation-algorithms>
Clique cover problem
m0_as
# Clique cover problem

(Asked by: username_0 on 2017-07-26)

Consider the following graph problem. We are given a graph $\mathcal{G} = (\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of vertices and $\mathcal{E}$ is the set of edges. For each vertex $V \in \mathcal{V}$, there is a weight $W(V)$.

For a clique $Q=(Q\_V,Q\_E)$ where $Q\_v \subset \mathcal{V}$ and $Q\_E \subset \mathcal{E}$, the weight of clique $Q$ is defined as $W(Q) = \max\_{V \in Q\_V}W(V)$.

Now, we want to find a set of cliques covering all vertices $\mathcal{V}$ such that the sum of weights of these cliques are minimum.

**In this problem NP-hard?**
I think since the graphs are general, when the weights are equal, then the problem become minimum clique cover problem in which we want to cover the graph $\mathcal{G}$ with minimum number of cliques. Since this problem is NP-hard, the problem with arbitrary weights is also NP-hard. Am I right?

**How can we find an approximation algorithm for this problem?**
I think the most trivial algorithm that comes to mind is this but I don't know how good it is.

Sort the vertices based on their weights in decreasing order (the first one has the highest weight) and if two have the same weight we sort them based on the number of edges of them. Assume the sorted list of vertices is $V\_1, \ldots, V\_{10}$. Now, we start from the clique $C = V\_1$ and check the list $V\_2, \ldots, V\_{10}$ from left to right. For each element, we check whether adding $V\_j$ to $S$ results in a clique or not. If yes, we form a clique of $S$ and $V\_j$, and remove $V\_j$ from the list. We continue this process (now for $S = \{V\_1,V\_j\}$) until we reach the end of list $V\_2, \ldots, V\_{10}$. Now we remove the vertices of set S, from $V\_1, \ldots, V\_{10}$, and repeat the above procedure for the first element of $V\_1, \ldots, V\_{10}$ minus the set $V$.

**Tags:** graph-theory, graph-algorithms, np-hardness, approximation-algorithms

> **Comments:**
> **username_1**: Is this homework? Did you look at the special case where all vertices have unit-weight?  
> **username_0**: @username_1 No, it is not a class homework. I think since the graphs are general, when the weights are equal, then the problem become minimum clique cover problem in which we want to cover the graph $\mathcal{G}$ with minimum number of cliques. Since this problem is NP-hard, the problem with arbitrary weights is also NP-hard. Am I right?  
> **username_0**: @username_1 My main question is about finding a good approximation algorithm. I have one greedy algorithm in mind, but I don't know how good it is and how to find a approximation bound for that.  
> **username_2**: Indeed if all weights are equal to 1, then this is clique cover, and cannot be approximated better than a factor $n^{1-\varepsilon}$, for $n$ the number of vertices, and $\varepsilon > 0$ any constant.  
> **username_0**: @SashoNikolov I am not familiar with this type of statement. Is the fact that complexity of approximation depends on $\epsilon$ hidden in the statement? I mean, if not, I guess we can make $\epsilon$ arbitrarily small, (like $\epsilon = 0.9999$), and get a very good approximation. So, I guess as we make $\epsilon$ smaller, the complexity goes higher. Right? In which order?  
> **username_2**: I think there is some confusion: I am saying that approximation is hard. I.e. for any $\varepsilon > 0$, it is NP-hard to approximate clique cover better than a factor $n^{1-\varepsilon}$. The complexity of the NP-hardness reduction increases as $\varepsilon$ goes to $0$. See http://www.theoryofcomputing.org/articles/v003a006/v003a006.pdf  

---

## 1 answers

### Answer by username_3 on 2017-07-28. Score: 2

I don't know if there is a suitable approximation algorithm for this problem, but I can provide a counter-example for your heuristic algorithm:   
Assume G has 2\*n vertices with weights   
$$W(v\_i) = w - \epsilon \* i$$
Which in your algorithm will be sorted by this order:
$$v\_1, v\_2, ... v\_{2n}$$
And there's an edge between $v\_i$ and $v\_j$ iff $\exists k : i-j = 2\*k$  
The resulting graph is the union of 2 cliques with size n  
The algorithm alternates between these two, which means in every step a clique with exactly one vertex will be returned, yielding a final answer with weight:
$$2\*n\*w - \epsilon \* n \* (2\*n+1)$$
But we know that the optimum weight is just $2\*w - 3\*\epsilon$   
So the approximation factor can be as big as $n/2$ (assuming that the graph has $n$ vertices) which is not very interesting because the obvious algorithm "Pick each vertex as a clique" has an approximation factor of $n$


---

