2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are we allowed to add balls to a bin? Is "capping" sequential? $\endgroup$ – Aravind Nov 29 '14 at 14:02
  • $\begingroup$ Do you have any $k$ for which you know the problem is NP-complete? $\endgroup$ – Peter Shor Nov 29 '14 at 15:43
  • $\begingroup$ 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$? $\endgroup$ – daniello Nov 29 '14 at 16:20
  • $\begingroup$ @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). $\endgroup$ – Htr2 Nov 29 '14 at 16:26
  • $\begingroup$ @PeterShor I am working on $k = 3$ at the moment, I will hopefully have more to report soon. $\endgroup$ – Htr2 Nov 29 '14 at 16:28
3
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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. 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.

$\endgroup$
  • $\begingroup$ By "Connect every pair of literals", you mean complementary pair of literals, right? $\endgroup$ – Htr2 Nov 30 '14 at 4:41
  • $\begingroup$ @Htr2 Indeed! ("... corresponding to the same variable") $\endgroup$ – daniello Nov 30 '14 at 11:14

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.