<p>We confirm @YonatanN's conjecture:</p>
<p><strong>Lemma 1.</strong> <em>There is always an optimal solution <span class="math-container">$v'$</span> such that, for some <span class="math-container">$i'$</span>, <span class="math-container">$|v_{i'}' - v_{i'}| = k$</span>, while <span class="math-container">$v'_i = v_i$</span> for all <span class="math-container">$i\ne i'$</span>.</em></p>
<p>@YonatanN's suggested algorithm (try all possible such solutions and choose the best) will give the following corollary:</p>
<p><strong>Corollary 1.</strong> <em>There is a polynomial-time algorithm for the problem in the post.</em></p>
<p><em>Proof of Lemma 1.</em> Among optimal solutions, let <span class="math-container">$v'$</span> be one with a minimum number of <em>offset</em> indices, that is, <span class="math-container">$i$</span> such that <span class="math-container">$v'_i \ne v_i$</span>.
Suppose for contradiction that <span class="math-container">$v'$</span> has at least two offset indices <span class="math-container">$h$</span> and <span class="math-container">$j$</span>.</p>
<p><em>Case 1.  First consider the case that <span class="math-container">$v'_h &gt; v_h$</span> and <span class="math-container">$v'_j &gt; v_j$</span>.</em>
Fix <span class="math-container">$\delta = d(h) - d(j)$</span>, where
<span class="math-container">$$d(x) = |\{(x, i) \in E : v'_x &gt; v'_i\}| - |\{(x, i) \in E : v'_x &lt; v'_i\}|.$$</span>
Imagine increasing <span class="math-container">$v'_h$</span> while decreasing <span class="math-container">$v'_j$</span> at unit rate by an arbitrarily small <span class="math-container">$\epsilon&gt;0$</span>.
This operation (for <span class="math-container">$\epsilon \le v'_j - v_j$</span>) would preserve <span class="math-container">$\sum_{i} |v'_i - v_i|$</span>, so the solution would remain feasible,
and it would increase the objective value at rate at least <span class="math-container">$\delta$</span>.
We conclude by this thought experiment (and the optimality of <span class="math-container">$v'$</span>) that <span class="math-container">$\delta \le 0$</span>.</p>
<p>Now actually decrease <span class="math-container">$v'_h$</span> and increase <span class="math-container">$v'_j$</span>, both at unit rate, until <span class="math-container">$v'_h = v_h$</span>.
This increases the objective at rate at least <span class="math-container">$-\delta\ge 0$</span>, and preserves feasibility,
so it yields another optimal solution with fewer offset indices (as <span class="math-container">$h$</span> is no longer offset),
contradicting the choice of <span class="math-container">$v'$</span>.</p>
<p>(We use above that, as we continue to decrease <span class="math-container">$v'_h$</span> and increase <span class="math-container">$v'_j$</span>, the rate of increase in the objective does not decrease.  This is because all edges that contribute positively to the rate (e.g. <span class="math-container">$(i,h)$</span> with <span class="math-container">$v'_i &gt; v'_h$</span>) continue to do so, while edges that contribute negatively may start contributing positively.)</p>
<p><em>Case 2. Next consider the case that <span class="math-container">$v'_h &gt; v_h$</span> and <span class="math-container">$v'_j &lt; v_j$</span>.</em>  Consider increasing <span class="math-container">$v'_h$</span> and <span class="math-container">$v'_j$</span> at unit rate by an arbitrarily small positive amount.  This would preserve feasibility while increasing the objective at rate at least <span class="math-container">$\alpha = d(h) + d(j$</span>). So <span class="math-container">$\alpha \le 0$</span>.
Now decrease both <span class="math-container">$v'_h$</span> and <span class="math-container">$v'_j$</span> at unit rate until <span class="math-container">$v'_j = v_j$</span>.  This preserves feasibility while increasing the objective at rate at least <span class="math-container">$-\alpha \ge 0$</span>, yielding another optimal solution with fewer offset indices, contradicting the choice of <span class="math-container">$v'$</span>.</p>
<p>For each remaining case (e.g. <span class="math-container">$v'_h &lt; v_h$</span> and <span class="math-container">$v'_j &lt; v_j$</span>), a symmetric argument shows that the case cannot happen.  It follows that <span class="math-container">$v'$</span> has at most one offset index.  Let <span class="math-container">$i'$</span> be that index, if it exists, and otherwise an arbitrary index.  If <span class="math-container">$|v'_{i'} - v_{i'}| = k$</span>, we are done, so assume <span class="math-container">$|v'_{i'} - v_{i'}| &lt; k$</span>.
Now decreasing <span class="math-container">$v'_{i'}$</span> would increase the objective at rate at least <span class="math-container">$d(i')$</span>, so the optimality of <span class="math-container">$v'$</span> implies <span class="math-container">$d(i') \le 0$</span>.  So increase <span class="math-container">$v'_{i'}$</span> at unit rate until <span class="math-container">$|v'_{i'} - v_{i'}| = k$</span>.  This preserves feasibility, while increasing the objective at rate at least <span class="math-container">$-d(i') \ge 0$</span>, giving the desired optimal solution. <span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2021-10-08T16:42:10.317Z
2021-10-08T18:46:53.113Z
2021-10-08T18:46:53.113Z
Neal Young
<p>Given a graph <span class="math-container">$G=\{V,E\}$</span>, each node <span class="math-container">$i$</span> has a value <span class="math-container">$v_i$</span>. Given budget <span class="math-container">$k$</span>, we have <span class="math-container">$k$</span> chance to add 1 or minus 1 for a node's value, for example, <span class="math-container">$v'_i=v_i+1$</span> or <span class="math-container">$v'_i=v_i-1$</span>. In particular, <span class="math-container">$v'_i$</span> denotes the value of node <span class="math-container">$i$</span> after <span class="math-container">$k$</span> modifications. The target is to maximize absolute value difference between each pair of connected node after <span class="math-container">$k$</span> times modifications, which is formulated as:
<span class="math-container">\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}</span></p>
<p>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?</p>
<p>Thanks in advance.</p>

CC BY-SA 4.0
2021-10-07T19:21:03.373Z
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.
Yonatan N
<np-hardness><optimization>
Maximize the absolute value of connected nodes after $k$ modifications
Refrain
# Maximize the absolute value of connected nodes after $k$ modifications

(Asked by: username_0 on 2021-10-07)

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.

**Tags:** np-hardness, optimization
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2021-10-08. Score: 2 | Accepted 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$


---

