Chapter 8

Beyond NP-completeness

At the conclusion of Chapter 6, we stated that proving a problem is NP-

complete does not make it go away. The subject of this chapt er is to go

beyond NP-completeness and to describe the various approaches that can be

taken when confronted with an NP-complete problem.

The ﬁrst approach (see Section 8.1) is the most elegant. When deriving

approximation algorithms, we search for an approximate solution, but we also

guarantee that it is of good quality. Of course, the approximated solution

must be found in polynomial time.

The second approach (see Section 8.2) is less ambitious. Given an NP-

complete problem, we show how to characterize particular instances that have

polynomial complexity.

The third approach (see Section 8.3) often provides useful lower bounds.

The idea is to cast the optimization problem under study in terms of a lin-

ear program. While solving a linear program with integer variables is NP-

complete, solving a linear program with rational variables has polynomial

complexity (we are restricted to rational variables because of the impossibil-

ity of eﬃciently encoding real numbers). The diﬃculty is then to reconstruct

a solution of the integer linear program from an optimal solution of that pro-

gram with rational variables. This is not always possible, but this method at

least provides a lower bound on any optimal integer solution.

We brieﬂy introduce, in Section 8.4, randomized algorithms as a fourth ap-

proach that solves “most” instances of an NP-complete problem in polynomial

time.

Finally, we pr ovide in Section 8.5 a detailed discussion of branch-and-bound

and backtracking strategies, where one explores the space of all potential so-

lutions in a clever way. While the worst-case exploration may require expo-

nential time, on average, the optimal solution is found in “reasonable” time.

8.1 Approximation results

In this section, we ﬁrst deﬁne polynomial-time approximation algorithms and

(fully) polynomial-time approximation schemes (PTAS and FPTAS). Then,

179

© 2014 by Taylor & Francis Group, LLC

180 Chapter 8. Beyond NP-completeness

we give some examples of approximation and inapproximability results.

8.1.1 Approximation algorithms

In Chapter 6, we have deﬁned the NP-completeness of problems and exhibited

several NP-complete decision problems. As discussed in Section 6.3.4, the

target problem is often an optimization problem that has been restricted to a

decision problem so that we can prove its NP-completeness.

If the optimal solution of an optimization problem cannot be found in poly-

nomial time, one may want to ﬁnd an approximate solution in polynomial

time.

DEFINITION 8.1. A λ-approximation algorithm is an algorithm whose

execution time is polynomial in the instance size and that returns an approx-

imate solution guaranteed to be, in the worst case, at a factor λ away from

the optimal solution.

For instance, for each instance I of a minimization pr oblem, the solution

of the approximation algorithm f or instan ce I must be smaller than or equal

to λ times the optimal solution for instance I.

The closer λ to 1, the better the approximation algorithm. We catego-

rize some particular approximation algorithms for which λ is close to 1 as

polynomial-time approximation schemes.

DEFINITION 8.2. A Polynomial-Time Approximation Scheme (PTAS) is

such that for any constant λ = 1 + ε > 1, there exists a λ-approximation algo-

rithm, i.e., an algorithm that is polynomial in t he instance size and guaranteed

at a factor λ.

Note that the algorithm may not be polynomial in 1/ε and thus have a

high complexity when ε gets close to zero. A Fully PTAS is such that the

algorithm is polynomial both in the instance size and in 1/ε.

DEFINITION 8.3. A Fully Polynomial-Time Approximation Scheme, or

FPTAS, is such that for any constant λ = 1 + ε > 1, there exists a λ-

approximation algori thm that is polynomial in the instance size and in 1/ε.

The diﬀerence between PTAS and FPTAS is simply that the ∀ε quantiﬁer

changes sides. For a PTAS, ε is a ﬁxed constant, so that 2

1

ε

is a constant as

well. On the contrary, the complexity of an FPTAS scheme must be polyno-

mial in

1

ε

. Of course, having an FPTAS is a stronger property than having

a PTAS (i.e., FPTAS ⇒ PTAS).

Finally, we deﬁne asymptotic PTAS and FPTAS, which add a constant to

the approximation scheme. We deﬁne formally only the APTAS for a mini-

mization problem, and the deﬁnition can easily be extended for maximization

problems and AFPTAS.

© 2014 by Taylor & Francis Group, LLC

Start Free Trial

No credit card required