Discovering surprises in
the face of intractability.
BY fEDoR V. foMin AnD PETTERi KAsKi
Man Y CoMPUTa TionaL ProbLeMs have been shown to be
intractable, either in the strong sense that no
algorithm exists at all—the canonical example being
the undecidability of the Halting Problem—or that no
efficient algorithm exists. From a theoretical
perspective perhaps the most intriguing case occurs
with the family of NP-complete problems, for which it
is not known whether the problems are intractable.
That is, despite extensive research, neither is an
efficient algorithm known, nor has the existence of
one been rigorously ruled out.
To cope with intractability, advanced techniques
such as parameterized algorithms10, 13, 31 (that isolate the
exponential complexity to a specific structural
parameter of a problem instance) and approximation
algorithms34 (that produce a solution whose value
is guaranteed to be within a known factor of the
value of an optimum solution) have been developed.
But what can we say about finding exact solutions
of non-parameterized instances of intractable problems? At first glance, the
general case of an NP-complete problem is a formidable opponent: when
faced with a problem whose instances
While it remains open whether or not
P equals NP, significant progress in
the area of exhaustive search has been
made in the last few years. in particular,
many NP-complete problems can
now be solved significantly faster by
exhaustive search. The area of exact
exponential algorithms studies the
design of such techniques.
While many exact exponential
algorithms date back to the early days
of computing, a number of beautiful
surprises have emerged recently.