2
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ You can replace each vertex $v_i$ by $p$ nodes $v_{i,1},v_{i,2},...,v_{i,p}$ and give them weights $c_{i,1},c_{i,2},...,c_{i,p}$, respectively. Then add edges $(v_{i_1,j},v_{i_2,j})$ for all $i_1\neq i_2$ and all $j$. Add edges $(v_{i,j_1},v_{i,j_2})$ for all $j_1,j_2$ and $i$. We will also have edges $(v_{i_1,j_1},v_{i_2,j_2})$, for all $j_1\neq j_2$, if there was an edge $(v_{i_1},v_{i_2})$ in the original graph. It looks like the problem can be reduced to minimum weighted independent set in this new graph. $\endgroup$ – plop Aug 12 at 3:20
  • $\begingroup$ Thanks @plop. It is a good idea, although changes the structure of the graph. I think it should be posted as an answer. $\endgroup$ – Mostafa Aug 12 at 3:27
  • 1
    $\begingroup$ Another way to look at this problem is to consider the assignment of a specific weight to some node in your graph as a weighted bipartite matching problem, where the independence on the side of original graph is an additional constraint. Bipartite matching problems with additional constraints are well studied, so perhaps this perspective helps. $\endgroup$ – Discrete lizard♦ Aug 12 at 9:06
  • $\begingroup$ Thanks @Discretelizard for the help. Do you mean considering a bipartite matching for each node? that means I will have $n$ nodes in the first set with some edges between them (due to the original problem), and for each node, a second set with $p$ nodes representing the weights? $\endgroup$ – Mostafa Aug 12 at 14:10
  • 1
    $\begingroup$ @Mostafa Not exactly, if I understand your problem correctly you cannot use weights of the same 'type' twice. So take as the first set the nodes in your graph, and as the second set a node for each different type of weight. So in total the graph has $n+T$ nodes, where $T$ is the total number of types of weights among all nodes. $\endgroup$ – Discrete lizard♦ Aug 12 at 14:19
2
$\begingroup$

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

enter image description here

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

enter image description here

Images created with this tool.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is great. But in the example, in the second figure, I think there should be edges between B1 and C1, and also B2 and C2. $\endgroup$ – Mostafa Aug 12 at 14:39
  • $\begingroup$ @Mostafa That's right. I forgot those. I replaced the image now. $\endgroup$ – plop Aug 12 at 14:41

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.