Consider an undirected graph $G = (V,E)$ with a weight function $w \colon V \to \mathbb{N}$ on its vertices. Let $\alpha_w(G)$ denote the maximum weight of an independent set in $G$, i.e., the maximum over all sets $S \subseteq V(G)$ consisting of pairwise nonadjacent vertices, of the value $\sum _{v \in S} w(v)$. Then the collection $\mathcal{I}_w(G)$ of maximum-weight independent sets of $G$ is defined as:

$\mathcal{I}_w(G) := \{ S \subseteq V(G) \mid S \text{ is an independent set and } \sum_{v \in S} w(v) = \alpha_w(G) \}$.

The same collection of maximum-weight independent sets can be generated by multiple different weight functions on $G$. For example, multiplying all weight values by the same constant leads to the same collection of maximum-weight independent sets. Let's say a weight function on an $n$-vertex graph is $f(n)$ bounded if each vertex weight lies in the range $\{1, \ldots, f(n)\}$. I am interested in the following question:

Is it true that for any weight function $w$ on an $n$-vertex graph $G$, there exists an equivalent $2^{o(n)}$-bounded weight function? That is, does there always exist a weight function $w'$ which assigns integer weights in the range from $1$ to $2^{o(n)}$ such that $\mathcal{I}_w(G) = \mathcal{I}_{w'}(G)$?

When we restrict $G$ to be a forest, there is an elementary argument to show that an equivalent weight function exists that is $O(n)$-bounded. In general, theorems from integer linear programming theory can be used to prove that there is always an equivalent weight function which is $2^{O(n \log n)}$-bounded, even in much more general settings. Can better bounds be obtained in this restricted setting of maximum weight independent sets?

  • $\begingroup$ The $\lceil n / 2 \rceil$ upper bound for forests doesn't look right. For a star tree with $n$ vertices and the only maximum weight set consisting of only the center we need weights up to $n$. $\endgroup$ – Mikhail Tikhomirov Mar 19 at 17:35
  • $\begingroup$ I think weight zero is also allowed in the def. $\endgroup$ – domotorp Mar 19 at 19:32
  • $\begingroup$ Actually, this doesn't help much if you ask for two maximum weight sets: the center or all the leaves. $\endgroup$ – domotorp Mar 19 at 19:33
  • $\begingroup$ You are right; my claimed bound of $\lceil n/2 \rceil$ for forests was in a slightly more relaxed model where I allow vertices to be merged into one, so that it occurring in a max independent set means all vertices that were merged belong to that maximum independent set. In the model as stated, $Theta(n)$ is the right bound for forests. $\endgroup$ – Bart Jansen Mar 23 at 17:06

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.