0
$\begingroup$

Consider array $A=(a_1,a_2,...,a_n)$ such that $a_i$s are positive integers. Moreover, we have $k$ binary tuples, each with length $n$. In each iteration, we choose one of those tuples, and decrease it from the array. For example, if $A=(5,7,4,2)$ and we decrease $(1,0,0,1)$ from it, it will become $(4,7,4,1)$. We cannot use a tuple more than one time. Moreover, we know that sum of all those $k$ tuples is $A$. What is the minimum number of tuples we need to decrease from $A$, in order that $A$ be sorted in decreasing order?

I want to know whether it is an NP-hard problem.

Example: $A=[2,3,4,5]$

tuples=$(0,1,1,1),(0,0,1,1),(1,0,0,1),(1,0,1,1),(0,1,1,1),(0,1,0,0)$

The answer is 4. By subtracting (0,1,1,1),(0,1,1,1),(0,0,1,1) and (1,0,0,1), we will have [1,1,1,1] which is decreasingly sorted. We used 4 tuples, and it is not possible with fewer tuples(at least, I could not).

$\endgroup$
2
  • $\begingroup$ You have to reduce the array down to (0,0,0,0)? "...A be sorted in decreasing order" -- at each step? $\endgroup$
    – TickaJules
    Feb 4 at 20:14
  • $\begingroup$ Not necessarily to (0,0,0,0). For example, if you can decrease the tuples in a way that [5,7,4,2] converts to [5,5,3,1], it is feasible. $\endgroup$ Feb 4 at 21:16

1 Answer 1

1
$\begingroup$

You can reduce from exact-cover by $3$-sets (X3C): given a set $X$ of $3n$ elements $x_1, \dots, x_n$, and a collection $S = \{S_1, \dots, S_m\}$ of $m$ sets each containing exactly $3$ elements, is there an exact cover, i.e., a subset $S'$ of $S$ such that $|S'|=n$ and $\cup_{S_j \in S'} S_j = X$?

Consider the instance of your problem where:

  • $A = (a_0, a_1, a_2, a_3, \dots a_{3n}) = (3n, 3n, 3n-1, 3n-2, \dots 1)$ is an array of length $3n+1$ (for ease of notation I'm indexing the array from $0$) where $a_0 = 3n$ and $a_i = 3n-i$ for $i \ge 1$
  • There is a tuple $t_j$ for each set $S_j$. The $i$-th entry (again, indexing from $0$) is set to $1$ in $t_j$ if and only if $x_i \in S_j$.
  • Suitably add a bunch of tuples, each with only a single entry set to $1$, in order to ensure that the sum of all tuples yields exactly $A$ (notice that only you need polynomially many tuples).

If there is an exact cover $S'$, then selecting all $t_j$ such that $S_j \in S'$ yields the array $(3n, 3n-1, 3n-2, \dots, 0)$.

If you can use $n$ tuples to transform $A$ into a decreasing vector, then each entry $a_i$ with $i \ge 1$ is decreased at least once. Moreover, since each tuple has at most $3$ entries set to $1$, each entry $a_i$ with $i \ge 1$ is decreased exactly once, while $a_0$ is never decreased. This means that the collection of sets $S_j$ such that $t_j$ is a selected tuple is an exact cover.

To summarize, there is a solution to the instance of your problem using at most $n$ tuples if and only if there a solution to the X3C instance.

$\endgroup$
3
  • $\begingroup$ Sorry but I do not understand. If A=(3n,3n,3n-1,3n-2,,,,,,1), It is already sorted in decreasing order, and the minimum number of tuples needed to be subtracted from it to be sorted decreasingly is 0. $\endgroup$ Feb 4 at 21:34
  • $\begingroup$ $(3n, 3n, 3n-1, \dots, 1)$ is not sorted in decreasing order because the first two entries are equal (it is sorted in non-increasing order though). If you are interested in transforming $A$ to a vector sorted in non-increasing order, then the same reduction works, you just need to start with $A= (2, 3,3,3, \dots, 3)$. $\endgroup$
    – Steven
    Feb 4 at 21:43
  • $\begingroup$ Thanks Steven. I appreciate your help. $\endgroup$ Feb 14 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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