2
$\begingroup$

Assume we are given a graph of $N$ vertices $V_1, \ldots, V_N$. For each vertex $V_i$, there is a corresponding weight $v_i$. For a graph of $N$ vertices, we want to find the minimum weight subgraph consisting of disjoint cliques which includes all vertices (that is, all vertices are present in the subgraph and each vertex is exactly in one clique) under two following conditions:

  1. For each clique (complete subgraph) of the original graph, the weight is defined as the maximum of the weights of the vertices of the clique. More specifically, if vertices $X_1, \ldots, X_k$ form a clique where $x_i$ is the weight of vertex $X_i$, then the weight of this clique is $\max\{x_1,\ldots,x_k \}$.
  2. The total weight of a subgraph with multiple cliques is the sum of the weights of the cliques.

I want to know whether this problem is NP-complete? Is there any approximation algorithm for this problem which runs in polynomial time of $N$.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

The special case when each vertex weight $v_i$ is equal to $1$ sums up to solving the following problem: partition the vertices into cliques and minimize the number of cliques.

This is known as the Vertex Clique Cover problem (see here). [Edit: it is straightforward to see that Vertex Clique Cover can be reduced to your problem, and so it's NP-hard.]

Unfortunately, as stated on the Wikipedia page, the problem cannot approximated within a $n^{1 - \varepsilon}$ factor, and so there is polytime approximation algorithm achieving a reasonable factor.

If you have structural knowledge of the graph you are studying, that might help (e.g. I think if the degree is bounded, you may be able to approximate something).

$\endgroup$
14
  • $\begingroup$ Thanks for your response. So, the Vertex Clique Cover problem can be reduced to our problem where all vertices have weight 1. From, this we can conclude that our problem is NP-hard (and since there is a polynomial time verification for it, it is NP-complete). Am I right? $\endgroup$
    – m0_as
    Jan 8, 2017 at 1:16
  • 1
    $\begingroup$ Yes, you're right! Sorry I forgot to mention it's NP-hard (and, as you say, NP-complete). $\endgroup$
    – Manuel Lafond
    Jan 8, 2017 at 3:05
  • $\begingroup$ Thanks. Regarding whether the graph of this question has a specific structure, yes it has. The structure has been explained here: math.stackexchange.com/questions/1833883/a-graph-problem/… I was guessing that because that question was long, it is better to ask it in a more general way again because it is no easy to read that question. $\endgroup$
    – m0_as
    Jan 8, 2017 at 3:19
  • 1
    $\begingroup$ No we can't assume it's NP-complete for all classes of graphs. For instance, Vertex Clique Cover is in P for all bipartite graphs (because it's the problem of finding a maximum matching). The graphs that are "hard" are those created in proof of hardness of Vertex Clique Cover. And also those graph classes for which a specific proof of hardness exists (for instance, I think that VCC on 3-regular graphs is NP-hard, but that required its own proof). $\endgroup$
    – Manuel Lafond
    Jan 8, 2017 at 4:16
  • 1
    $\begingroup$ It does seem that this paper could help you: zib.de/groetschel/pubnew/paper/…. From what I understand, at the end of page 194, they find in polytime a minimum weight VCC on perfect graphs, where the weight is simply given for each clique (what I say here has to be verified though). But like you, I don't have time to understand it fully. Maybe it's something you can ask as another question. $\endgroup$
    – Manuel Lafond
    Jan 10, 2017 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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