13
$\begingroup$

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.

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

4 Answers 4

4
$\begingroup$

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 .

$\endgroup$
0
$\begingroup$

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 :-)
$\endgroup$
1
  • $\begingroup$ @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 $\endgroup$ Jan 23, 2015 at 23:00
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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!

$\endgroup$

Your Answer

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

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