2
$\begingroup$

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) <u, \quad \forall i,j, \tag1 \\ &\quad\sum_{i}\sum_{k} x_{ik} = p, \tag2 \\ &\quad\sum_{i} x_{ik} = 1, \quad \forall k, \tag3 \\ &\quad\sum_{k} x_{ik} \leq 1, \quad \forall i, \tag4 \\ &\quad x_{ik} \in \{0,1\}, \quad \forall i, \forall k. \end{align}

Constraints (1) sets the edges between any two nodes $i,j$ that $d(i,j) <u$, 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?

$\endgroup$
  • 1
    $\begingroup$ (2) is implied by (3). $\endgroup$ – RobPratt Aug 10 at 13:03
  • 1
    $\begingroup$ And if there are no isolated vertices, (4) is implied by (1). $\endgroup$ – RobPratt Aug 10 at 13:49
  • $\begingroup$ 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. $\endgroup$ – Mostafa Aug 10 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.