1
$\begingroup$

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$.

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ Is this homework? Did you look at the special case where all vertices have unit-weight? $\endgroup$
    – Gamow
    Commented Jul 26, 2017 at 7:25
  • $\begingroup$ @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? $\endgroup$
    – m0_as
    Commented Jul 26, 2017 at 17:14
  • $\begingroup$ @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. $\endgroup$
    – m0_as
    Commented Jul 26, 2017 at 17:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sasho Nikolov
    Commented Jul 27, 2017 at 2:46
  • 1
    $\begingroup$ 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 theoryofcomputing.org/articles/v003a006/v003a006.pdf $\endgroup$
    – Sasho Nikolov
    Commented Jul 27, 2017 at 14:28

1 Answer 1

Reset to default
2
$\begingroup$

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$

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.