Is this a known problem in graph theory?

Question

My basic problem includes a graph where each node $i$ is associated with a weight $c_i$, and the problem is to find a minimum (or maximum) weighted independent set with a fixed cardinality $p$. This is I believe a well-known problem in graph theory that is well-studied for different types of graphs.

Now, suppose I am dealing with a generalized form of the problem as following. The weight of each node can take $p$ different values, that is each node is associated with $p$ different weights. The aim is again to find a minimum (or maximum) weighted independent set with a fixed cardinality $p$, however, each type of weight can be selected only once. Precisely, if the weight type $j$ is selected for the node $i$, i.e., we select the weight $c_{ij}$, then the other selected nodes cannot take a weight of type $j$.

My question is that, is this still a graph theory problem? Is it a known generalization in the graph theory problems?

Any help and/or reference is appreciated.

Answer 1

If $G=(V,E)$, with $V=\{v_1,v_2,...,v_n\}$ and weights $\{c_{i,j}, i=1,2,...,n, j=1,2,...,p\}$ is the given graph, then we can construct the strong product (I finally found the name of the operation) $G\boxtimes K_p$ of $G$ and $K_p$, where $K_p$ is the complete graph with $p$ vertices. This is the graph with vertices $\{v_{i,j},i=1,2,...,n, j=1,2,...,p\}$ and edges $\{v_{a,b},v_{c,d}\}$ where either:

1. $a=c$,
2. $b=d$ or
3. $\{v_a,v_c\}\in E$. (The actual condition of the strong product reduces to this since in $K_p$ all vertices are adjacent).

We give the vertex $v_{i,j}$ the weight $c_{i,j}$, for $i=1,2,...,n$ and $j=1,2,...,p$.

The problem on $G$ is equivalent to the problem minimum (maximum) weighted independent set in the weighted $G\boxtimes K_p$. If a vertex $v_{i,j}$ of the new graph is chosen this corresponds to choosing vertex $v_i$ of the original graph and using the $j$-th weight $c_{i,j}$ corresponding to it.

The set of edges of $G\boxtimes K_p$ are exactly those that prevent the corresponding choices in $G$ to use adjacent vertices or reusing weights with the same index:

• Condition $1$ defines edges in the strong product that prevent the equivalent of using two weights from the same original vertex.
• Condition $2$ prevents using the weights with the same index from different vertices of the original graph.
• Condition $3$ prevents that two vertices that were neighbors in the original graph are selected.

Example:

If $G$ is the graph

and $p=2$, then $G\boxtimes K_2$ would be the graph

Images created with this tool.