# Is the following problem decidable in polynomial time?

We are given an initial set of tuples $S_0=\{(x_i,y_i)|i\in [n], \forall i:x_i,y_i\in \mathbb{N}\}$ and a number $B\in \mathbb{N}$.

At time $t$ we are allowed to remove ($S_t := S_{t-1} \setminus \{(x_i,y_i)\}$)

a pair $(x_i,y_i)\in S_{t-1}$: if $$x_i + \Sigma_{j:(x_j,y_j)\in S_{t-1}, j\neq i} y_j \geq B$$.

(That is if the sum of $x_i$ and the rest of the $y_j$'s is at least $B$ we're allowed to remove tuple $i$).

The problem is finding a sequence of tuples which can be legally removed, and leave a minimal cardinality set (i.e. remove as many tuples as possible).

Is this problem in $P$ as it is?

What if we know that $\forall i:y_i\leq x_i$?

Example: Assume $S_0 = \{(5,3),(5,5),(1,1),(6,0),(2,2)\}, B=10$ then $(<1,1>,<6,0>,<2,2>,<5,3>)$ is an example of a maximal output sequence.

• I can't understand your notation in the definition of $S_0$. Is $S_0$ a set of pairs of natural numbers? What's going on with $i$ -- it is both bound and unbound on the right hand side? The notation doesn't make any sense to me. Also your notation $j \in S_{t-1}$ is messed up, since $S_{t-1}$ is a set of pairs, not indices. I suggest proof-reading the question a bit more. Also, I don't understand the problem. The input is $S_0$. What is the desired output? You want to find a final set of smallest possible cardinality, among all possible sequences?
– D.W.
Commented May 24, 2014 at 19:22
• Once you've clarified the statement of the problem, the next thing for you to work on: What have you tried? Where did you get stuck? I suggest you edit the question (click the "edit" button underneath the question) to clarify the problem statement, show us what you've tried, and address these questions. Also, it would help if you can pick a more descriptive title.
– D.W.
Commented May 24, 2014 at 19:24
• Hi @D.W. and thanks for your comments. I can't see the problem $S_0$'s definition. It is consisted of $n$ pairs of natural numbers. I've edited the notation of $j\in S_{t-1}$. While I understand it was an abuse of notation I thought it would be understandable and leave it more readable. The output should be a (longest possible) sequence of pairs that could be legally removed. Does this make sense? How'd you title the question?
– R B
Commented May 24, 2014 at 19:34
• This is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. If you are uncertain how to improve your question, why not ask around in Computer Science Chat?
– D.W.
Commented May 24, 2014 at 20:14

This is a nice exercise, such as one might find in an undergrad-level algorithms class. (Congratulate your professor on selecting such a nice exercise.) Since it's your exercise, I'm going to let you solve it, but I'll give you a series of hints.

Important: Spend at least an hour exploring each hint, before moving on to the next hint.

Hint #1:

When given an algorithms problem, it is often very helpful to look at some small examples and work out what's going on by hand.

So, pick a sample problem instance with 3 items (generate the $x_i,y_i$'s arbitrarily); map out all possible timelines (all possible sequences of item removals); and see what you see. Do another example with 3 items. Try one with 4 items. Do a few such examples, and see if you can build some intuition. I suspect you'll spot what is going on, and then from that you might be able to figure out how to solve the problem.

Hint #2:

What chapter of the textbook are you currently in? This is often a good heuristic to help you select a type of algorithm to try.

Hint #3:

A natural algorithmic approach is to use a greedy algorithm: if multiple items are currently eligible for removal, select the item whose $y_i$ value is _____. (You fill in the blank.) So, see if you can determine whether you can find any way to fill in the blank that provides a correct algorithm for your problem. This gives you a few candidate algorithms; for each candidate, see if you can prove or disprove its correctness. To do that, try some small examples. See if you can find a proof of correctness or a counterexample demonstrating it is incorrect. Once you've worked out whether there is any algorithm of this form that is correct, you should be able to answer your question.

Hint #4:

If you've tried all of the above diligently, show us your work and where you got stuck and I'll give you one more hint.