# Maximize the absolute value of connected nodes after $k$ modifications

Given a graph $$G=\{V,E\}$$, each node $$i$$ has a value $$v_i$$. Given budget $$k$$, we have $$k$$ chance to add 1 or minus 1 for a node's value, for example, $$v'_i=v_i+1$$ or $$v'_i=v_i-1$$. In particular, $$v'_i$$ denotes the value of node $$i$$ after $$k$$ modifications. The target is to maximize absolute value difference between each pair of connected node after $$k$$ times modifications, which is formulated as: $$\begin{gather} \max\sum_{e(i,j)\in E}{|v'_i-v'_j|} \\ s.t. \sum_{i\in V}|v'_i-v_i|=k \end{gather}$$

I want to ask whether this problem is NP-hard or not? I find this function is not submodular or monotone, thus is there any solution with an approximation ratio if it is NP-hard?

Thanks in advance.

• Is it not the case that an optimal solution keeps picking the same vertex value in the same direction all $k$ times? If it is, then the problem has a pretty straightforward poly-time algorithm (try both possible directions for all possible vertices) and is thus (likely) not NP-hard. Oct 7, 2021 at 19:21

## 1 Answer

We confirm @YonatanN's conjecture:

Lemma 1. There is always an optimal solution $$v'$$ such that, for some $$i'$$, $$|v_{i'}' - v_{i'}| = k$$, while $$v'_i = v_i$$ for all $$i\ne i'$$.

@YonatanN's suggested algorithm (try all possible such solutions and choose the best) will give the following corollary:

Corollary 1. There is a polynomial-time algorithm for the problem in the post.

Proof of Lemma 1. Among optimal solutions, let $$v'$$ be one with a minimum number of offset indices, that is, $$i$$ such that $$v'_i \ne v_i$$. Suppose for contradiction that $$v'$$ has at least two offset indices $$h$$ and $$j$$.

Case 1. First consider the case that $$v'_h > v_h$$ and $$v'_j > v_j$$. Fix $$\delta = d(h) - d(j)$$, where $$d(x) = |\{(x, i) \in E : v'_x > v'_i\}| - |\{(x, i) \in E : v'_x < v'_i\}|.$$ Imagine increasing $$v'_h$$ while decreasing $$v'_j$$ at unit rate by an arbitrarily small $$\epsilon>0$$. This operation (for $$\epsilon \le v'_j - v_j$$) would preserve $$\sum_{i} |v'_i - v_i|$$, so the solution would remain feasible, and it would increase the objective value at rate at least $$\delta$$. We conclude by this thought experiment (and the optimality of $$v'$$) that $$\delta \le 0$$.

Now actually decrease $$v'_h$$ and increase $$v'_j$$, both at unit rate, until $$v'_h = v_h$$. This increases the objective at rate at least $$-\delta\ge 0$$, and preserves feasibility, so it yields another optimal solution with fewer offset indices (as $$h$$ is no longer offset), contradicting the choice of $$v'$$.

(We use above that, as we continue to decrease $$v'_h$$ and increase $$v'_j$$, the rate of increase in the objective does not decrease. This is because all edges that contribute positively to the rate (e.g. $$(i,h)$$ with $$v'_i > v'_h$$) continue to do so, while edges that contribute negatively may start contributing positively.)

Case 2. Next consider the case that $$v'_h > v_h$$ and $$v'_j < v_j$$. Consider increasing $$v'_h$$ and $$v'_j$$ at unit rate by an arbitrarily small positive amount. This would preserve feasibility while increasing the objective at rate at least $$\alpha = d(h) + d(j$$). So $$\alpha \le 0$$. Now decrease both $$v'_h$$ and $$v'_j$$ at unit rate until $$v'_j = v_j$$. This preserves feasibility while increasing the objective at rate at least $$-\alpha \ge 0$$, yielding another optimal solution with fewer offset indices, contradicting the choice of $$v'$$.

For each remaining case (e.g. $$v'_h < v_h$$ and $$v'_j < v_j$$), a symmetric argument shows that the case cannot happen. It follows that $$v'$$ has at most one offset index. Let $$i'$$ be that index, if it exists, and otherwise an arbitrary index. If $$|v'_{i'} - v_{i'}| = k$$, we are done, so assume $$|v'_{i'} - v_{i'}| < k$$. Now decreasing $$v'_{i'}$$ would increase the objective at rate at least $$d(i')$$, so the optimality of $$v'$$ implies $$d(i') \le 0$$. So increase $$v'_{i'}$$ at unit rate until $$|v'_{i'} - v_{i'}| = k$$. This preserves feasibility, while increasing the objective at rate at least $$-d(i') \ge 0$$, giving the desired optimal solution. $$~~~\Box$$