# Minimizing weight values while preserving the collection of maximum-weight independent sets

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?

• 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$. – Mikhail Tikhomirov Mar 19 at 17:35
• I think weight zero is also allowed in the def. – domotorp Mar 19 at 19:32
• Actually, this doesn't help much if you ask for two maximum weight sets: the center or all the leaves. – domotorp Mar 19 at 19:33
• 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. – Bart Jansen Mar 23 at 17:06