Pop desired elements on stacks of bounded capacity

Question

Consider there are $k$ stacks containing a total of $n$ elements. Each element is either red or blue. We have complete knowledge of each element's location and color. Only push and pop are allowed on the stacks.

We are interested in removing all the red elements from the stacks while maintaining the blue elements. That is, if we pop a blue element, we have to immediately push it into another stack before any other operation. Each stack has an upper bound capacity $b$, so it cannot hold more than $b$ elements.

We are interested in the minimum number of pop operations to remove all red elements from the stack (or respond it is infeasible).

One can devise a polynomial time algorithm when $k$ is a constant. Is there a polynomial time algorithm with respect to $n$ and $k$?

If we replace stacks with queues, then the problem is trivial.

Answer 1

Here's a simple algorithm:

We repeatedly pick a stack with a red element and execute a subroutine (to be described below) that tries to pop the topmost red element out of the stack. Either we will end up popping every red element or at some point every stack with a red element will have the subroutine failing. In the former case, it is clearly possible to pop all the red elements. In the later case, every topmost red element can't be popped, so in fact no more red elements can be popped, and so popping all the red elements is impossible.

The subroutine:

Simply pop elements out of the stack in question (pushing blue elements into other stacks) until either a red element is popped (success) or until the blue elements being popped cannot fit into the other stacks (failure).

Runtime

The subroutine requires at most $n$ operations, and the subroutine must be executed at most $k$ times in order to either conclude that a solution is impossible or to pop one red element. Since there are at most $n$ red elements. The overall runtime is $O(kn^2)$, which is polynomial in $n$ and $k$.

Correctness

Certainly if this procedure pops all the red elements then popping all the red elements is possible.

Now suppose the subroutine fails on a stack. Define the "blocking" elements in a stack to be all blue elements above the topmost red element. Subroutine failure can only happen if all the blocking elements in the stack and all the elements in all other stacks cannot fit in the other stacks. Thus, this topmost red element cannot be removed until the count of blocking elements plus elements in other stacks decreases. In other words, the topmost red element cannot be the next red element popped.

If the subroutine fails for every stack with a red element, then no red element can be the next red element popped. In other words, no remaining red element can be popped at all.

Since every operation is either reversible (moving a blue element between stacks) or purely beneficial (popping a red element), reaching a state where the subroutine fails for every stack implies that all along the problem could not be solved.