A graph problem

Question

Consider the following graph problem. For a number $K$ and a set $\mathcal{K} = \{ 1, \ldots,K\}$, we have a set of vertices $V_k^s$ for all $s \subset \mathcal{K} \setminus \{k\}$, $s$ is not empty and for all $k$. For example, if $K =2$, we have $V_1^{\{2\}}$ and $V_2^{\{1\}}$. if $K =3$, we have $V_1^{\{2,3\}}$, $V_1^{\{2\}}$, $V_1^{\{3\}}$, $V_2^{\{1,3\}}, V_2^{\{1\}}, V_2^{\{3\}}, V_3^{\{1,2\}}, V_3^{\{1\}}, V_3^{\{2\}}$. The weight of vertex $V_k^s$ is denoted by $v_k^s$.

There is an edge between two vertices $V_k^s$ and $V_l^t$, if $k \in t$ and $l \in s$. For example, for $K=3$, there is an edge between $V_1^{\{2,3\}}$ and $V_2^{\{1\}}$, but there is no edge between $V_1^{\{2\}}$ and $V_3^{\{1\}}$.

The resulting graphs for $K=2$ and $K=3$ have been shown in the two following figures. Note that the corresponding graph for $K=k$ have $Q_k = k \times (2^{k-1}-1)$ vertices.

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

For a given number $K$ and its corresponding graph, 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). I want to know whether this problem is NP-complete? I am looking for an algorithm (probably approximation) which runs in polynomial time of $Q_K$.

---

A more general problem: Consider the following graph problem. For a number $K$, a set $\mathcal{K} = \{ 1, \ldots,K\}$, and $b_1, \ldots, b_K$, we have a set of vertices $V_{k,b_k}^s$ for all $s \subset \mathcal{K} \setminus \{k\}$, $s$ is not empty and for all $k$. The weight of vertex $V_{k,b_k}^s$ is denoted by $v_{k,b_k}^s$ and $v_{k,b_k}^s = v_{l,b_l}^s$ if $b_k = b_l$.

1) There is an edge between two vertices $V_{k,b_k}^s$ and $V_{l,b_l}^t$, if $k \in t$ and $l \in s$. 2) There is an edge between two vertices $V_{k,b_k}^s$ and $V_{l,b_l}^s$, if $b_k = b_l$.

If all $b_1, \ldots, b_K$ are different, then this problem becomes the one described above.

Answer 1

If all weights are with a factor W of each other, then you can get a
W-approximation by just pretending they're all equal and applying
the linear-time solution mentioned in your question's last paragraph.


One can get an efficient ​ $\ln(Q_k)$-approximation ​ by
using Algorithm 3.1.7 and finding the $\operatorname{argmax}$s as follows:

Vertices in the same column are not adjacent, so cliques have at most one vertex in each column. ​ ​ ​ Brute-force over the possibilities for which set P of not-already-covered columns the
non-empty clique uses. ​ ​ ​ (There are at only 2$^k$-1 possibilities, and if ​ 1 < k ​ then ​ 2$^k$-1 < Q_k .)
For each column in P, find the minimum weight of not-already-covered vertices
whose superscripts each include the indices of the other columns in P.
If any elements of P have no such vertices then P does not induce any cliques,
else with M being the maximum of those minimum weights,
[M is the weight of the minimum-weight cliques that induce P] and
[those cliques are formed by choosing, for each column in P, exactly one of the vertices in that column which is such that [the vertex's superscript includes the indices of all other columns in P] and [the vertex's weight is at most M]].

By "subgraph" in the rest of this answer, I mean induced.

Pretending the not-in-the-subgraph vertices are already covered turns that into
a poly$(Q_k)$-time ln(n)-approximation for n-vertex subgraphs of your graphs.
Observe that solutions always restrict to no-more-expensive solutions to subgraphs, so in particular the minimum cost for a subgraph cannot exceed the minimum cost for the original graph.
Thus, what I described two sentences ago can be used as a heuristic to hopefully get better
lower bounds, and as a special case of that, yields an algorithm which provably achieves better approximation bounds when most weights are much smaller than the maximum weight:

Split the graph into a large low-weight part and a small (n-vertex) high-weight part.
Combining a cover of the low-weight part with a ln(n)-approximation for
the high-weight part yields a cover of the input graph whose cost is at most
[cost for low-weight part] ​ ​ ​ + ​ ​ ​ [ ln(n) ​ $\cdot$ ​ [optimum cost for input graph] ] ​ .


If n is sufficiently small, then you can do even better by using an
Exponential-Time Approximation of Weighted Set Cover on the high-weight part.