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.

  • 5
    Make your question self-contained by defining "strongly". – Tyson Williams Jan 28 '13 at 13:03
  • 3
    Longest path is a generalization of Hamiltonian Path, so it's strongly NP-hard. – Michael Lampis 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.” – Tsuyoshi Ito 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 – Marzio De Biasi 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!

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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