<p>Here's an argument that it's polynomial for $k=2$. </p>

<p>If $k=2$, each bin can only be connected to two other bins, and thus the graph falls into paths and cycles. We can thus just worry about a cycle. In fact, we can guess which bin is capped first. Since there are only a polynomial number of guesses, we can try all of them, and reduce the problem to the case where the graph is a path.</p>

<p>Now, whether a bin can be capped only depends on whether or not you've capped its neighbors. That is, for bin $1$, we have one of the following constraints:</p>

<ol>
<li>bin $1$ can be capped only before you've capped bin $2$,</li>
<li>bin $1$ can be capped only after you've capped bin $2$,</li>
<li>bin $1$ can be capped any time,</li>
<li>bin $1$ can never be capped.</li>
</ol>

<p>For case 1, you might as well cap bin $1$ as the first thing you do. Now, you have a path of length $n-1$, and you can use recursion. </p>

<p>For case 2, you might as well cap bin $1$ as the last thing you do. Now, you have a path of length $n-1$, and you can use recursion.</p>

<p>For case 3, capping bin $1$ will either add or subtract balls from bin $2$. If it adds them, make it the first bin you cap. If it subtracts them, make it the last bin you cap. In either case, you've reduced the problem to a path of length $n-1$.</p>

<p>For case 4, you've solved the problem: it's impossible to win.</p>

<p>This gives an algorithm of time $O(n^2)$. For a cycle of length $n$, we need to test $n$ different paths, breaking the cycle in every possible place. And for a path of length $n'$, in constant time, we can convert the problem to the same problem on a path of length $n'-1$. </p>

CC BY-SA 3.0
2014-11-29T18:02:44.453Z
2014-11-29T20:22:32.827Z
2014-11-29T20:22:32.827Z
Peter Shor 
<p>We prove hardness for $k \geq 3$. First observe that the problem is equivalent to the following graph problem: Input is a graph $G$ of maximum degree $k$, with an integer demand $d_v$ on every vertex $v$ and an integer weight $w_e$ for every edge $e$. The task is to find an acyclic orientation of the edges (i.e resulting in a DAG) such that for every vertex, the sum of the weights of the incoming edges is at least the demand. </p>

<p>Here the demand of the vertex corresponding to bin $i$ is $Q-c_i$, and the weight of an edge is the "reward" or "penalty" incurred on one bin when capping the other.</p>

<p>We prove hardness for $k \geq 3$. We reduce from $3$-SAT where every literal appears either $1$ or $2$ times. This variant of $3$-SAT is <a href="http://www.google.no/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=4&amp;ved=0CDEQFjAD&amp;url=http%3A%2F%2Fwww.cse.msu.edu%2F~torng%2FClasses%2FArchives%2Fcse830.07spring%2FLectures%2Fexample-reductions.pdf&amp;ei=gmJ6VMGTFomGzAOtyIGIDg&amp;usg=AFQjCNErSPH0f35uvm-P0biuzcI7WBKiDQ&amp;sig2=nQbIUH6q97Tc0Q64uheoLg&amp;bvm=bv.80642063,d.bGQ&amp;cad=rja" rel="nofollow">known to be NP-complete</a>. Make one vertex for every clause and every literal. Connect every pair of literals corresponding to the same variable by an edge of weight $-2$. Connect every literal with the clauses that contain it by edges of weight $1$. Every clause gets demand $1$, and every literal gets demand $0$ if it appears in two clauses and $-1$ if it appears in one clause.</p>

<p>For the forward direction, if there is a satisfying assignment orient all 
edges away from the literals set to true and into the literals set to false. This is clearly acyclic and it is easy to check that all vertex demands are satisfied.</p>

<p>For the reverse direction consider an acyclic orientation that satisfies all vertex demands. For every variable, look at the edge between the corresponding literals and set the variable accordingly: if the edge is oriented from $x$ to $\bar{x}$ set $x$ to ${\sf true}$, otherwise set $x$ to ${\sf false}$. Now, if the edge is oriented from $x$ to $\bar{x}$, then, in order to meet $\bar{x}$'s demand all other edges incident to $\bar{x}$ must also be oriented towards $\bar{x}$. The same holds for $x$ if the edge is oriented from $\bar{x}$ towards $x$. Since every vertex corresponding to a clause must have at least one edge oriented towards it it follows that every clause contains a literal set to true.</p>

CC BY-SA 3.0
2014-11-30T04:41:44.260Z
By "Connect every pair of literals", you mean complementary pair of literals, right?
Htr2
CC BY-SA 3.0
2014-11-30T11:14:55.880Z
@Htr2 Indeed! ("... corresponding to the same variable")
daniello
CC BY-SA 3.0
2014-11-30T00:20:56.440Z
2014-11-30T00:20:56.440Z
daniello
<p>Consider a game where one has a set of bins $(b_1, b_2, ...)$, and each bin has an associated initial count of balls $(c_1, c_2, ...)$.  The rules of the game are as follows:</p>

<p>(1) Once a bin has a threshold number of balls $Q$ (the threshold is uniform for all bins), the bin may be capped, and capping is irreversible.  However, one is not obligated to cap the bin once this condition is met.  Capping must be SEQUENTIAL.  One cannot simultaneously cap two bins to avoid e.g. a situation where capping one bin drops the number of balls in the other bin below the threshold $Q$ necessary for capping.</p>

<p>(2) Once a bin is capped, a bin-specific set of "punishments" or "rewards" can be specified for at most $k$ other bins.  For example, we might say that, in capping bin $3$, we need to subtract two balls from bin $1$ and add seven balls to bin $5$.  So to each bin we assign a two $k$-tuples: the first, e.g. {1,5}, with values from the previous example, specifies the bins to be "punished" or "rewarded", and the second, e.g. {-2, 7}, again from the provided examples, species how many balls to add or remove from each of the bins in the first tuple.</p>

<p>(3) Negative values for bin ball counts are permissible, and a bin may initiate (i.e. have some $c_i$ value) $\leq 0$.</p>

<p>(4) We add the constraint that punishments or rewards must be symmetric.  If capping some bin $b_i$ means subtracting one ball from bin $b_j$, it must also be the case that capping bin $b_j$ means subtracting one ball from bin $b_i$.</p>

<p>(5) We add the constraint that the total number of punishments or rewards a bin may receive is at most $k$.  By the symmetry condition from (4), this correspondingly implies that the total number of punishments or rewards a bin may deliver is at most $k$.</p>

<p>Consider now the decision problem: provided some set of bins $(b_1, b_2, ...)$, initial ball counts $(c_1, c_2, ...)$, and access to all of the dependencies elaborated on in rule (2), can all of the bins be capped?</p>

<p>This problem is trivially in $NP$, but for what smallest value of $k$ is it $NP$-complete?  Can the decision problem be $NP$-complete for $k=2$?  Is there an easy reduction from an $NP$-complete problem or a problem solvable in polynomial time?</p>

<p>Update // Added further constraints (4) + (5), where (5) is implied by (4).  That should be it.</p>

CC BY-SA 3.0
2014-11-29T14:02:05.687Z
Are we allowed to add balls to a bin? Is "capping" sequential?
Aravind
CC BY-SA 3.0
2014-11-29T15:43:10.570Z
Do you have any $k$ for which you know the problem is NP-complete?
Peter Shor 
CC BY-SA 3.0
2014-11-29T16:20:33.410Z
Can't the problem be reformulated as a graph problem: Input is an undirected graph $G$ of maximum degree $k$, with an integer weight $w(v)$ on every vertex $v$ and integer weight $w(e)$ for every edge $e$. The task is to find a permutation of $V(G)$ such that for every vertex the sum of its weight plus the weight of all edges ``towards the left" in the permutation is at least $Q$?
daniello
CC BY-SA 3.0
2014-11-29T16:26:03.600Z
@Aravind Capping must be sequential.  I have updated (1) to reflect this.  My apologies.  Regarding adding balls... I'm not sure what you mean?  Once the initial ball counts are set, they may only ever be changed by capping other bins (leading to the punishments and rewards in terms of adding and withdrawing balls to other specified bins).
Htr2
CC BY-SA 3.0
2014-11-29T16:28:17.483Z
@PeterShor I am working on $k = 3$ at the moment, I will hopefully have more to report soon.
Htr2
CC BY-SA 3.0
2014-11-29T16:30:04.997Z
@daniello Yes, however please note that we set all $w(v)$ to be equal (though $w(e)$ may be distinct).  Great, do you see a reduction from this to a known problem?
Htr2
CC BY-SA 3.0
2014-11-29T16:33:45.037Z
Why are all vertex weights same? I was thinking that $w(v_i) = c_i$ where $v_i$ is the vertex corresponding to bin $i$.
daniello
CC BY-SA 3.0
2014-11-29T16:36:30.427Z
@daniello That's correct.  I misunderstood your comment.  The threshold is always $Q$, however, the goal is to have the sum of $w(v_i)$ and the set of edges from $v_i$ to "capped" bins (within one edge traversal) equal or exceed $Q$.
Htr2
<np-hardness><reductions><np><np-complete>
Balls & Bins: A punishment and reward game
Htr2
# Balls & Bins: A punishment and reward game

(Asked by: username_0 on 2014-11-29)

Consider a game where one has a set of bins $(b\_1, b\_2, ...)$, and each bin has an associated initial count of balls $(c\_1, c\_2, ...)$. The rules of the game are as follows:

(1) Once a bin has a threshold number of balls $Q$ (the threshold is uniform for all bins), the bin may be capped, and capping is irreversible. However, one is not obligated to cap the bin once this condition is met. Capping must be SEQUENTIAL. One cannot simultaneously cap two bins to avoid e.g. a situation where capping one bin drops the number of balls in the other bin below the threshold $Q$ necessary for capping.

(2) Once a bin is capped, a bin-specific set of "punishments" or "rewards" can be specified for at most $k$ other bins. For example, we might say that, in capping bin $3$, we need to subtract two balls from bin $1$ and add seven balls to bin $5$. So to each bin we assign a two $k$-tuples: the first, e.g. {1,5}, with values from the previous example, specifies the bins to be "punished" or "rewarded", and the second, e.g. {-2, 7}, again from the provided examples, species how many balls to add or remove from each of the bins in the first tuple.

(3) Negative values for bin ball counts are permissible, and a bin may initiate (i.e. have some $c\_i$ value) $\leq 0$.

(4) We add the constraint that punishments or rewards must be symmetric. If capping some bin $b\_i$ means subtracting one ball from bin $b\_j$, it must also be the case that capping bin $b\_j$ means subtracting one ball from bin $b\_i$.

(5) We add the constraint that the total number of punishments or rewards a bin may receive is at most $k$. By the symmetry condition from (4), this correspondingly implies that the total number of punishments or rewards a bin may deliver is at most $k$.

Consider now the decision problem: provided some set of bins $(b\_1, b\_2, ...)$, initial ball counts $(c\_1, c\_2, ...)$, and access to all of the dependencies elaborated on in rule (2), can all of the bins be capped?

This problem is trivially in $NP$, but for what smallest value of $k$ is it $NP$-complete? Can the decision problem be $NP$-complete for $k=2$? Is there an easy reduction from an $NP$-complete problem or a problem solvable in polynomial time?

Update // Added further constraints (4) + (5), where (5) is implied by (4). That should be it.

**Tags:** np-hardness, reductions, np, np-complete

> **Comments:**
> **username_1**: Are we allowed to add balls to a bin? Is "capping" sequential?  
> **username_2**: Do you have any $k$ for which you know the problem is NP-complete?  
> **username_3**: Can't the problem be reformulated as a graph problem: Input is an undirected graph $G$ of maximum degree $k$, with an integer weight $w(v)$ on every vertex $v$ and integer weight $w(e)$ for every edge $e$. The task is to find a permutation of $V(G)$ such that for every vertex the sum of its weight plus the weight of all edges ``towards the left" in the permutation is at least $Q$?  
> **username_0**: @username_1 Capping must be sequential.  I have updated (1) to reflect this.  My apologies.  Regarding adding balls... I'm not sure what you mean?  Once the initial ball counts are set, they may only ever be changed by capping other bins (leading to the punishments and rewards in terms of adding and withdrawing balls to other specified bins).  
> **username_0**: @PeterShor I am working on $k = 3$ at the moment, I will hopefully have more to report soon.  
> **username_0**: @username_3 Yes, however please note that we set all $w(v)$ to be equal (though $w(e)$ may be distinct).  Great, do you see a reduction from this to a known problem?  
> **username_3**: Why are all vertex weights same? I was thinking that $w(v_i) = c_i$ where $v_i$ is the vertex corresponding to bin $i$.  
> **username_0**: @username_3 That's correct.  I misunderstood your comment.  The threshold is always $Q$, however, the goal is to have the sum of $w(v_i)$ and the set of edges from $v_i$ to "capped" bins (within one edge traversal) equal or exceed $Q$.  

---

## 2 answers

### Answer by username_2 on 2014-11-29. Score: 3 | Accepted answer

Here's an argument that it's polynomial for $k=2$.

If $k=2$, each bin can only be connected to two other bins, and thus the graph falls into paths and cycles. We can thus just worry about a cycle. In fact, we can guess which bin is capped first. Since there are only a polynomial number of guesses, we can try all of them, and reduce the problem to the case where the graph is a path.

Now, whether a bin can be capped only depends on whether or not you've capped its neighbors. That is, for bin $1$, we have one of the following constraints:

1. bin $1$ can be capped only before you've capped bin $2$,
2. bin $1$ can be capped only after you've capped bin $2$,
3. bin $1$ can be capped any time,
4. bin $1$ can never be capped.

For case 1, you might as well cap bin $1$ as the first thing you do. Now, you have a path of length $n-1$, and you can use recursion.

For case 2, you might as well cap bin $1$ as the last thing you do. Now, you have a path of length $n-1$, and you can use recursion.

For case 3, capping bin $1$ will either add or subtract balls from bin $2$. If it adds them, make it the first bin you cap. If it subtracts them, make it the last bin you cap. In either case, you've reduced the problem to a path of length $n-1$.

For case 4, you've solved the problem: it's impossible to win.

This gives an algorithm of time $O(n^2)$. For a cycle of length $n$, we need to test $n$ different paths, breaking the cycle in every possible place. And for a path of length $n'$, in constant time, we can convert the problem to the same problem on a path of length $n'-1$.


---

### Answer by username_3 on 2014-11-30. Score: 2

We prove hardness for $k \geq 3$. First observe that the problem is equivalent to the following graph problem: Input is a graph $G$ of maximum degree $k$, with an integer demand $d\_v$ on every vertex $v$ and an integer weight $w\_e$ for every edge $e$. The task is to find an acyclic orientation of the edges (i.e resulting in a DAG) such that for every vertex, the sum of the weights of the incoming edges is at least the demand.

Here the demand of the vertex corresponding to bin $i$ is $Q-c\_i$, and the weight of an edge is the "reward" or "penalty" incurred on one bin when capping the other.

We prove hardness for $k \geq 3$. We reduce from $3$-SAT where every literal appears either $1$ or $2$ times. This variant of $3$-SAT is [known to be NP-complete](http://www.google.no/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&ved=0CDEQFjAD&url=http%3A%2F%2Fwww.cse.msu.edu%2F~torng%2FClasses%2FArchives%2Fcse830.07spring%2FLectures%2Fexample-reductions.pdf&ei=gmJ6VMGTFomGzAOtyIGIDg&usg=AFQjCNErSPH0f35uvm-P0biuzcI7WBKiDQ&sig2=nQbIUH6q97Tc0Q64uheoLg&bvm=bv.80642063,d.bGQ&cad=rja). Make one vertex for every clause and every literal. Connect every pair of literals corresponding to the same variable by an edge of weight $-2$. Connect every literal with the clauses that contain it by edges of weight $1$. Every clause gets demand $1$, and every literal gets demand $0$ if it appears in two clauses and $-1$ if it appears in one clause.

For the forward direction, if there is a satisfying assignment orient all
edges away from the literals set to true and into the literals set to false. This is clearly acyclic and it is easy to check that all vertex demands are satisfied.

For the reverse direction consider an acyclic orientation that satisfies all vertex demands. For every variable, look at the edge between the corresponding literals and set the variable accordingly: if the edge is oriented from $x$ to $\bar{x}$ set $x$ to ${\sf true}$, otherwise set $x$ to ${\sf false}$. Now, if the edge is oriented from $x$ to $\bar{x}$, then, in order to meet $\bar{x}$'s demand all other edges incident to $\bar{x}$ must also be oriented towards $\bar{x}$. The same holds for $x$ if the edge is oriented from $\bar{x}$ towards $x$. Since every vertex corresponding to a clause must have at least one edge oriented towards it it follows that every clause contains a literal set to true.

> **Comments:**
> **username_0**: By "Connect every pair of literals", you mean complementary pair of literals, right?  
> **username_3**: @username_0 Indeed! ("... corresponding to the same variable")  

---

