Exact algorithms for NP-complete problems are sometimes feasible, if the input is small enough.

I’ve also came across some algorithms which are not practical even for very small inputs, and their importance is questionable.

I’m wondering what's the "hardest" (time complexity-wise) problems people have worked on its exact solution:

  1. The problem is in NP.
  2. A non-trivial exact algorithm is known for the problem (preferably from the last few years).
  3. No better algorithm is known.

For example, the minimum dominating set of queens has an algorithm which runs in $O(39.51^n\cdot poly(n))$ time.

  • $\begingroup$ Somehow, many fixed-parameterized algorithms fall into this category. For example: doi.org/10.1145/1411509.1411511; doi.org/10.1145/1993636.1993699 $\endgroup$
    – Yixin Cao
    Jan 19 '14 at 19:18
  • $\begingroup$ having trouble following how these criteria would distinguish any NP complete problem from any other. it seems many/most NP complete problems can be solved exactly for small inputs. also, the listed criteria dont match the intro, no mention of small inputs is given in the listed criteria, is that an omission? and, all problems have a "nontrivial exact algorithm". as far as the theory is concerned, there seem to be few ways to discriminate any particular NP complete problem from any other... and there is the still-open "isomorphism conjecture" that in some deep senses they are "alike"... $\endgroup$
    – vzn
    Jan 19 '14 at 20:31
  • 2
    $\begingroup$ I really cannot understand what's a usage of this question in cstheory. Would you explain it? By the way, if you looking for problem which has a very big running time, may be is not bad to look at maximum parsimony problem which inspired in bioinformatic. As I know, best known exact algorithm for this is bigger than n!!. $\endgroup$
    – Saeed
    Jan 20 '14 at 10:27
  • 1
    $\begingroup$ @Saeed - I'm trying to understand how much interest people have in exact algorithms which seems impractical. If someone spent time constructing a non-trivial algorithm with runtime n!! I find it interesting, and I'm trying to understand how much research is done on such problems. $\endgroup$
    – R B
    Jan 20 '14 at 12:54
  • 1
    $\begingroup$ ok. re your last clarification think you are looking for something along lines of what RJLipton calls galactic algorithms ie basically they have significant research value but are [currently] not used in practice [ie not implemented in running code] due to impracticality. see also powerful algorithms too complex to implement $\endgroup$
    – vzn
    Jan 20 '14 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.