# A graph problem

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.

• We need to find a subgraph of the initially given graph, which includes all the vertices and has minimum sum weight, right? – Stefan4024 Jun 20 '16 at 22:54
• @Stefan4024 exactly. – m0_as Jun 20 '16 at 22:58
• @Stefan4024 Do you have any idea? – m0_as Jun 23 '16 at 20:37
• Not really. At first I thought of using the Greedy Algorithm by starting at connected vertex with highest value and then connect it to the vertex with highest value that is connected to it. But unfortunately I found some counter-example. – Stefan4024 Jun 23 '16 at 20:51
• You can model this as a integer knapsack problem. Enumerate all possible subgraphs. Treat each subgraph $S$ as an "item" for the knapsack problem, whose weight is $\sum_{j \in S} 2^j$ and whose value is $\max_{j \in S} G_j$. Then you just need to find a set of "item"s whose weight sums to exactly $2^{10}-1$ and whose value is minimal. – Irvan Jul 11 '16 at 7:30

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 < Qk .)
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.

• Thanks for your suggested approach. Can you explain more simply about your third paragraph? I didn't get it. One more question, do you think this problem is NP-hard? – m0_as Feb 12 '17 at 22:11
• What are you counting as "paragraph"s? ​ (i.e., what does my "third paragraph" start and end with?) ​ I suppose I'd guess that this problem is NP-hard. ​ ​ ​ ​ – user57159 Feb 12 '17 at 22:43
• The paragraph that starts with "Vertices in the same column are not adjacent, so cliques have at most one vertex in each column." Do you have any idea for showing that this is NP-hard? – m0_as Feb 12 '17 at 23:32
• Are you wondering about how to perform or just correctness of the procedure? ​ My vague idea is two possible weights, one much larger than the other, so that graph-coloring on the complement of the large-weight subgraph reduces to your problem. ​ (I can explain how that reduction works if you'd like, but I have no idea regarding showing hardness of those graph-coloring problems.) ​ ​ ​ ​ – user57159 Feb 12 '17 at 23:38
• "So, in ... not empty, right?" ​ Yes. ​ ​ ​ ​ – user57159 Feb 22 '17 at 7:05