# List of strongly NP-hard problems with numerical data

I am looking for strongly NP-hard problems for a reduction. So far I have found the following problems:

• 3-partition problem
• bin-packing problem
• Numerical 3-dimensional matching
• TSP
• Any NP-complete problem without numerical data, e.g., SATISFIABILITY, HAMILTONIAN CYCLE, 3-COLOURABILITY.

Does anyone know of a list of strongly NP-hard problems?

If not, let's build one here. Do you know of other problems with numerical data that are strongly NP-hard?

I'm particularly interested in strongly NP-hard problems on weighted graphs.

• Make your question self-contained by defining "strongly". Jan 28 '13 at 13:03
• Longest path is a generalization of Hamiltonian Path, so it's strongly NP-hard. Jan 28 '13 at 13:30
• (1) Is “strongly NP” a typo for “strongly NP-hard”? (2) I do not think that “we can make one here.” Jan 29 '13 at 3:40
• rainbow coloring seems to be hard wrt treewidth, maybe strongly NP hard also...?
– vzn
Jan 24 '15 at 19:51

Here is a strongly $NP$-complete problem (with numerical data as you requested):

Schur Triples problem:

Input: list of 3N distinct positive integers

Question: Is there a partition of the list into N triples $(a_i, b_i, c_i)$ such that $a_i + b_i= c_i$ for each triple $i$?

The condition that all numbers must be distinct makes the problem very interesting and McDiarmid calls it a surprisingly troublesome .

While thinking about possible answers I came up with this simple numeric strongly NP-complete problem:

SQUARE FREE SUBSET PRODUCT: Given $3N$ integers, find $N$ of them whose product is square free.

Proof sketch: starting from a an Exact Cover by 3 sets (X3C) instance (strongly NPC) label each element of the universe with a distinct prime (you can generate $3|X|$ of them in polynomial time); then convert every triple $(x,y,z)$ of the subsets to $xyz$.

I didn't find it anywhere, so it can be somewhat "original".

It obviously resembles the better known SUBSET PRODUCT (which is not strongly NPC due to the presence of the target product $B$, see David S. Johnson: The NP-Completeness Column: An Ongoing Guide. 393-405).

It can also be hacked a little bit to get other variants, like:

• Given $3N$ integers, find $N$ of them whose product is a perfect $21$-th power;
• Given $N$ integers, find a subset whose product is the 3N-th primorial. (kind of cheating :-)
• @domotorp: I deleted the question;I copy/paste here your comment about transforming the constraint into "...find a subset whose product is a square free number greater than M...":"First consider that you multiply each number by a different,very large prime, such that all these are about the same size. Then selecting N numbers would become equivalent to obtaining a large product. We cannot (yet) generate large primes in P, but in fact we don't need them - instead of each prime we can use relative prime square-free numbers,and those we can generate by computing the first polynomially many primes Jan 23 '15 at 23:00

Cieliebak in his Ph.D. Dissertation proved several problems to be strongly NP-complete. Specifically, the Double Digest problem and k-Equal Sum Subsets problem (when $k= \Omega(n)$ ) are strongly $NP$-complete.

Here's another strongly $NP$-hard problem: From the domain of theoretic scheduling and combinatorial optimization, the makespan problem on identical parallel machines (denoted commonly as $P||C_{max}$ in the literature). Note that some of the hardest scheduling problems almost all have this as a special case (e.g., the makespan problem on unrelated parallel machines.

It's strongly $NP$-hard, because you can reduce from the $3$-partition problem (,see http://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec10.pdf section 10.5).

Hope this helps!