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.

  • $\begingroup$ 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. $\endgroup$
    – Yonatan N
    Oct 7 '21 at 19:21

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$


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.