# Is this a common generalization of the independent set problem?

Suppose a minimum weighted independent set in a conflict graph with $$n$$ vertices. The basic version is where each vertex $$i$$ is associated with a weight $$c_i$$. i.e., there is a vector $$C$$ for the weights. The problem is to find a set of vertices (with a fixed cardinality $$p$$) with the minimum total weight. Now, suppose the generalization of the problem as follows:

There are $$p$$ types of weights for each vertex, i.e., there is a matrix $$C_{n\times p}$$ for the weights. The problem is to find a set of vertices (with a fixed cardinality $$p$$) with the minimum total weight, where each type of the weights can only be selected once.

The mathematical formulation of the problem is as follows ($$i$$ and $$j$$ are the indices for the vertices, and $$k$$ is the index for types of weights).

\begin{align} z = \min&\quad\sum_{i}\sum_{k} c_{ik} x_{ik} \\ \text{s.t.}&\quad \sum_k x_{ik} + \sum_k x_{jk} \leq 1, \quad d(i,j)

Constraints (1) sets the edges between any two nodes $$i,j$$ that $$d(i,j) , where $$u$$ is a pre-defined parameter.

Is this a known type of generalization in the graph theory problems? I mean is there a similar generalization in maximum independent set, or related problems?

• (2) is implied by (3). Aug 10 '20 at 13:03
• And if there are no isolated vertices, (4) is implied by (1). Aug 10 '20 at 13:49
• Thanks @RobPratt, yes (2) is redundant. Your second comment is also very helpful. Now I think it is better to identify those isolated ones, if any, and include (4) only for those ones. Aug 10 '20 at 14:02