Oliver Braun
CSE 101 (Summer Session 2021)
Homework 4: Algorithmic Complexity and NP-complete Problems
Instructions
Homework questions will be similar to your future exam questions. The homework will not be graded,
however, you are highly recommended to practice using these questions for better preparations of the
exams.
Key Concepts Algorithms, Optimization Problems, Minimization: Assignment, Maximization: Knap-
sack, Greedy-Heuristics, Complete Enumeration, Branch-And-Bound, Lower and Upper Bounds.
A large class of problems consists of problems that are equivalent in the following sense: a polynomial-
time algorithm for any one of them would imply the existence of a polynomial-time algorithm for all of
these problems. These are the NP-complete problems. In 1971 Steve Cook [Coo71] proved the existence of
NP-complete problems by showing that the so called Satisfiability problem (Can a given boolean formula
be satisfied or not?) is NP-complete (and the notion of NP-completeness was first identified in the work
of Steve Cook). The notion NP-complete refers always to decision problems, whereas the corresponding
optimization problems are NP-hard. The guideline for the process of devising an NP-completeness proof
for a decision problem X is the recipe described in Garey and Johnson’s book [GJ79]:
1. Show that X is in NP,
2. select a known NP-complete problem Y ,
3. prove that the input of X can be computed in polynomial time from the input of Y ,
4. show that Y is reducible to X.
The first step (show that X is NP by verifying that a certificate for X, i.e. a solution to the problem
X, actually solves the problem), and to prove that the input of the problem X can be computed in
polynomial time from the input of Y are often trivial to see. The challenging parts are selecting a known
NP-complete problem Y and showing that Y is reducible to X. The recipe for doing this is as follows:
Take an instance of Y and add some more input so that it will be a special instance for X.
Show that the only way to solve this special instance for X is to solve problem Y .
We say that Y is polynomially reducible to X (denoted Y ∝ X) if it is possible to transform inputs for Y
into inputs for X in polynomial time such that we can solve Y if and only if we can solve X. Reducibility
among decision problems is transitive, so for an NP-completeness proof of a decision problem X ∈ NP
it is sufficient to show that a known NP-complete problem Y ∈ NP is polynomially reducible to X.
The literature about NP-complete problems is vast and we decided to select only some problems. The
formal description of these problems, sometimes together with problem instances, is described in what
follows.
[Subset Sum] Given a list of n positive integers s1, s2, . . . , sn and a positive integer z. Does there exist
a subset I ⊆ {1, . . . , n} such that
∑
i∈I si = z? (I can be considered as an index set.)
[Example 1] n = 9 positive integers 2, 3, 3, 5, 6, 7, 8, 9, 9, z = 35.
The answer to the decision problem is yes, such a subset exists: I = {2, 3, 4, 6, 7, 8} or si = 3, 3, 5, 7, 8, 9.
1
[Zero Subset Sum] Given a list of n integers s1, s2, . . . , sn. Does there exist a subset I ⊆ {1, . . . , n}
such that
∑
i∈I si = 0?
[Partition] Given a list of n positive integers s1, s2, . . . , sn with σ =
∑n
i=1 si and a positive integer
z = σ/2. Does there exist a subset I ⊆ {1, . . . , n} such that
∑
i∈I si =
∑
i 6∈I si = z? (It is interesting
that the problem remains NP-complete even if it is required that | I |= n/2 ([GJ79], p.223).)
[Example 2] n = 9 positive integers 2, 3, 3, 5, 6, 7, 8, 9, 9, z = 26.
The answer to the decision problem is yes, such a subset exists: I = {1, 6, 7, 8} or si = 2, 7, 8, 9.
Another yes-answer would be I = {7, 8, 9} or si = 8, 9, 9.
[3-Partition] Given a list of n = 3m positive integers s1, s2, . . . , sn with σ =
∑n
i=1 si and a positive
integer z = σ/m. Does there exist a partition of {1, . . . , n} into m disjoint sets I1, . . . , Im such that∑
i∈I1 si = . . . =
∑
i∈Im si = z? (Note that often it is assumed that z/4 < si < z/2 and that each set I1, . . . , Im must therefore contain exactly three elements of 1, . . . , n.) [Example 3] n = 12 positive integers 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6,∑n i=1 si = 56, m = n/3 = 4, z = 56/4 = 14 and 14/4 < si < 14/2. The answer to the decision problem is yes, such a partition exists: I1 = {4, 4, 6}, I2 = {4, 4, 6}, I3 = {4, 5, 5}, I4 = {4, 5, 5}. [Example 4] If we omit the assumption that z/4 < si < z/2, there might obviously be nevertheless a solution where each set I1, . . . , Im contains exactly three elements of 1, . . . , n: n = 12 positive integers 1, 2, 2, 3, 3, 3, 4, 6, 7, 7, 8, 10,∑n i=1 si = 56, m = n/3 = 4, z = 56/4 = 14. The answer to the decision problem is yes, such a partition exists: I1 = {2, 2, 10}, I2 = {3, 3, 8}, I3 = {1, 6, 7}, I4 = {3, 4, 7}. Note that another yes-solution is: I1 = {4, 10}, I2 = {6, 8}, I3 = {7, 7}, I4 = {1, 2, 2, 3, 3, 3}. [Example 5] When we add a sufficiently large number to each one of the si, then we can force that in the sets I1, . . . , Im there must be exactly 3 elements of 1, . . . , n: n = 12 positive integers 1 001, 1 002, 1 002, 1 003, 1 003, 1 003, 1 004, 1 006, 1 007, 1 007, 1 008, 1 010,∑n i=1 si = 12056, m = n/3 = 4, z = 12056/4 = 3014. The answer to the decision problem is yes, such a partition exists: I1 = {1 002, 1 002, 1 010}, I2 = {1 003, 1 003, 1 008}, I3 = {1 001, 1 006, 1 007}, I4 = {1 003, 1 004, 1 007}. Remark: 3-Partition is partitioning a set of n elements in n/3 subsets with equal sums. Partition is partitioning a set of n elements in 2 subsets with equal sums. [Sequencing within intervals: 1 | rj , dj | ] Given one processor, n jobs with positive integer processing times p1, . . . , pn, release times r1, . . . , rn and deadlines d1, . . . , dn. Does there exit a feasible schedule so that each job completes by its deadline? Garey and Johnson name this problem Sequencing within intervals (p. 70 in [GJ79]). It is as well known as Scheduling with release times and deadlines. [Minimum tardiness sequencing: 1 | rj , dj | ] Given a set T of tasks, each t ∈ T having processing time 1 and a deadline d(t) ∈ Z+, a partial order � on T , and a non-negative integer K ≤| T |. Is there a schedule σ : T → {0, 1, . . . , | T | −1} such that σ(t) 6= σ(t′) whenever t 6= t′, such that σ(t) < σ(t′) whenever t � t′, and such that | {t ∈ T : σ(t) + 1 > d(t)} |≤ K?
2
[Parallel processor scheduling (with m or m = 2 processors): P || Cmax, P2 || Cmax] Given
an arbitrary large number m (or m = 2) parallel and identical processors, n jobs with positive integer
processing times p1, p2, . . . , pn and a number z. Does there exit a schedule with makespan not more than
z?
[Flow-Shop Scheduling with 3 processors: F3 || Cmax] Given a Flow-Shop with three proces-
sors, n jobs with non-negative integer processing times of the operations p1,1, . . . , p1,n on processor P1,
p2,1, . . . , p2,n on processor P2, p3,1, . . . , p3,n on processor P3, and a number z. Does there exit a schedule
with makespan not more than z?
[Bin Packing] Given a finite set U of items, a size s(u) ∈ Z+ for each u ∈ U , a positive integer bin
capacity B, and a positive integer K. Is there a partition of U into disjoint subsets U1, U2, . . . , UK such
that the sum of the sizes of the items in each Ui is B or less?
Remarks: NP-complete in the strong sense. NP-complete and solvable in pseudo-polynomial time for each
fixed K ≥ 2. Solvable in polynomial time for any fixed B by exhaustive search (complete enumeration).
[Knapsack] Given positive integer weights w1, . . . , wn and values v1, . . . , vn, an integer weight constraint
W ≥ 1 and an integer value goal V ≥ 1. Does there exist a subset I ⊆ {1, . . . , n} such that
∑
j∈I wj ≤W
and
∑
j∈I vj ≥ V ?
[Zero-One Equations (ZOE)] Given an m × n matrix A with 0 − 1-entries. Find a 0 − 1-vector
x = (x1, . . . , xn) such that the m equations Ax = 1 are satisfied, where by 1 we denote the column
vector of all 1’s.
[3-Dimensional Matching (3DM)] Given a set M ⊆W ×X×Y , where W,X and Y are disjoint sets
having the same number q of elements. Does M contain a matching, that is, a subset M ′ ⊆M such that
|M ′ |= q and no two elements of M ′ agree in any coordinate?
[Vertex Cover (VC)] Given a graph G = (V,E) and a positive integer K ≤| V |. Is there a vertex
cover of size K or less for G, that is, a subset V ′ ⊆ V such that | V ′ |≤ K and, for each edge {u, v} ∈ E,
at least one of u and v belongs to V ′?
[Clique] Given a graph G = (V,E) and a positive integer J ≤| V |. Does G contain a clique of size J or
more, that is, a subset V ′ ⊆ V such that | V ′ |≥ J and every two vertices in V ′ are joined by an edge in
E?
NP-complete in the ordinary and in the strog sense
Subset Sum and Partition are NP-complete in the ordinary sense, i.e. the problems cannot be optimally
solved by algorithms with polynomial-time complexity but with algorithms of time complexity O (n · z)
(Subset Sum) and O (n ·
∑
sj) (Partition). When z and max sj are bounded by a polynomial function
of n, these are in fact a polynomial-time algorithms. In these cases, we say that the algorithms run
in pseudo-polynomial time to indicate that they run in time polynomial in the magnitude of the input
numbers, but not polynomial in the size of their representation. If a problem is NP-complete in the strong
sense, there is (unless P=NP) not even a polynomial time approximation scheme for this problem.
For example, the NP-hard knapsack problem can be solved by a dynamic programming algorithm re-
quiring a number of steps polynomial in the size of the knapsack and the number of items (assuming
that all data are scaled to be integers); however, the runtime of this algorithm is exponential time since
the input sizes of the objects and knapsack are logarithmic in their magnitudes. However, as Garey and
Johnson [GJ79] observed:
”A pseudo-polynomial-time algorithm () will display exponential behavior only when confronted with
instances containing exponentially large numbers, [which] might be rare for the application we are in-
terested in. If so, this type of algorithm might serve our purposes almost as well as a polynomial time
algorithm.”
Another example for a weakly NP-complete problem is the Subset Sum problem.
3
For example, Bin Packing is strongly NP-complete while the 0-1-Knapsack Problem is only weakly NP-
complete. Thus the version of Bin Packing where the object and bin sizes are integers bounded by
a polynomial remains NP-complete, while the corresponding version of the Knapsack problem can be
solved in pseudo-polynomial time by Dynamic Programming. While weakly NP-complete problems may
admit efficient solutions in practice as long as their inputs are of relatively small magnitude, strongly
NP-complete problems do not admit efficient solutions in these cases. From a theoretical perspective any
strongly NP-hard optimization problem with a polynomially bounded objective function cannot have a
fully polynomial-time approximation scheme (or FPTAS) unless P = NP.
Time complexity as a function of natural parameters [GJ79], pp.106–107. In practice, we
consider time complexity expressed in terms of natural problem parameters instead of the artificially
constructed input length. For example, consider Multiprocessor Scheduling (P2 || Cmax and P3 || Cmax).
Here a collection of natural parameters might consist of the number n of jobs, the number m of processors,
and the length L of the longest job.
The ordinary NP-completeness result for this problem will be proved in one of the questionsand implies
that, unless P=NP, P2 || Cmax cannot be solved in the three parameters n,m, and logL. However, one
can still ask whether it is possible to have an algorithm with time complexity polynomial in mn and
logL, or polynomial in nm and logL, or polynomial in n,m, and L, or even polynomial in (nL)m.
The original NP-completeness result for P2 || Cmax actually shows that the subproblem in which m
is restricted to the value 2 is NP-complete, thus ruling out an algorithm polynomial in nm and logL
(unless P=NP), since such an algorithm would be a polynomial time algorithm for this P2 || Cmax. The
NP-completeness result for P2 || Cmax does not rule out an algorithm polynomial in mn = 2n and logL,
and indeed exhaustive search algorithms having such a time complexity can be designed.
Analogously, the strong NP-completeness result for P3 || Cmax that will be proved in one of the questions
rules out an algorithm polynomial in n,m, and L (unless P=NP). It leaves open the possibility of an
algorithm polynomial in (nL)m (which would give a pseudo-polynomial time algorithm for each fixed
value of m), and such an algorithm can be shown to exist. Thus, considering the subproblems P2 || Cmax
and P3 || Cmax obtained by placing restrictions on one or more of the natural problem parameters, we
obtain useful information about what types of algorithms are possible for the general problem P || Cmax.
Thus the theory of NP-completeness can be used to guide our search not only for polynomial time
algorithms, but for exponential time algorithms as well.
References
[Coo71] Cook, S.A., The complexity of theorem-proving procedures, Proceedings of the 3rd ACM
Symposium on the Theory of Computing, 151–158, 1971.
[DPV08] Dasgupta, S., Papadimitriou, C., Vazirani, U., Algorithms, McGrawHill, 2008.
[GJS76] Garey, M.R., Johnson, D.S., Sethi, R., The complexity of flowshop and jobshop scheduling,
Mathematics of Operations Research 1, 117–129, 1976.
[GJ79] Garey, M.R., Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-
Completeness, Bell Labs, 1979.
[KT14] Kleinberg, J., Tardos, E., Algorithm Design, Pearson, 2014.
4
Problem 1. Prove: Knapsack is NP-complete.
Use: Proof by restriction to Partition.
Solution: Partition is a special case of Knapsack. We focus on the target problem (Knapsack) itself
and attempt to restrict away its inessential aspects until a known NP-complete problem (Partition)
appears [GJ79], p.64.
We restrict Knapsack to Partition as follows: We restrict Knapsack and allow only instances in
which wj = vj for all j = {1, . . . , n} and V = W =
(∑n
j=1 wj
)
/2. �
5
Problem 2. Prove: P2 || Cmax is NP-complete.
Use: Proof by restriction to Partition.
Solution: In this problem, we look at the decision version of the parallel processor scheduling
problem with two processors P2 || Cmax. The formal definition of this problem can be found
in Garey and Johnson [GJ79] on p.65, where they also give a straightforward way to prove the
NP-completeness of P2 || Cmax: We focus on the target problem (P2 || Cmax) itself and attempt
to restrict away its inessential aspects until a known NP-complete problem (Partition) appears
[GJ79], p.64.
We restrict P2 || Cmax to Partition as follows: We restrict P2 || Cmax and allow only instances in
which z =
(∑n
j=1 pj
)
/ 2. �
6
Problem 3. Prove: P2 || Cmax is NP-complete.
Use: Partition ∝ P2 || Cmax.
Solution:
1. P2 || Cmax is in NP.
A certifier takes as a certificate a schedule (given e.g. as starting times, processing times and
completion times for each job) and checks that the maximum completion time, i.e. the makespan,
is at most the given bound z.
2. Select a known NP-complete problem Y = Partition.
3. The input for X = P2 || Cmax can be computed in polynomial time from the input for Y =
Partition.
Consider an instance of Partition with n positive integers s1, s2, . . . , sn, σ =
∑n
j=1 sj and an integer
value z = σ/2. If σ is odd, then it would be impossible to find a partition and the answer to the
decision problem would be no. Thus, from now on, let us assume that σ is even. We construct (in
polynomial time) an equivalent instance of P2 || Cmax as follows: pj = si for i = j = 1, . . . , n and
the same z as in Partition.
4. Show that Y = Partition is reducible to X = P2 || Cmax.
Now we consider any feasible solution to this instance of P2 || Cmax. Let I be a subset of {1, . . . , n}.
In this solution, the jobs are scheduled on P1 (all pj , j ∈ I) and P2 (all pj , j /∈ I) such that the
makespan is equal to z = σ/2.
The only way to achieve this is to solve a Partition problem as out of the numbers p1, . . . , pn we
have to choose a subset I ⊆ {1, . . . , n} such that
∑
j∈I sj = z = σ/2. The numbers in I sum up
together to z = σ/2 and the numbers in {1, . . . , n} \ I sum up together to z = σ/2 as well.
P1 pj , j ∈ I
0 z = σ/2
P2 pj , j 6∈ I
0 z = σ/2
Figure 1: We have to solve Partition in order to solve P2 || Cmax.
Therefore, a solution to the specific problem instance of P2 || Cmax gives us implicitly a solution
for Partition.
Conversely: If there are numbers that add up to exactly z = σ/2 in the Partition instance, then
this leads directly to a solution of the P2 || Cmax instance.
Result.
Since P2 || Cmax is in NP, since the input for P2 || Cmax can be computed in polynomial time from
the input for Partition, and since we can reduce the NP-complete problem Partition to P2 || Cmax,
P2 || Cmax must also be NP-complete. �
7
Problem 4. Prove: P || Cmax is NP-complete in the strong sense.
Use: 3-Partition ∝ P || Cmax.
Solution: We proved already that the decision version of the parallel processor scheduling problem
with m = 2 processors (P2 || Cmax) is NP-complete. In this problem we look at the decision
version of the parallel processor scheduling problem with an arbitrary large number m of processors
P || Cmax.
1. P || Cmax is in NP.
A certifier takes as a certificate a schedule (given e.g. as starting times, processing times, completion
times for each job) and checks that the makespan is at most the given bound z.
2. Select a known (in the strong sense) NP-complete problem Y = 3-Partition.
3. The input for P || Cmax can be computed in polynomial time from the input for 3-Partition.
Consider an instance of 3-Partition with n = 3m positive integers s1, s2, . . . , sn, σ =
∑n
i=1 si and
a positive integer z = σ/m.
We construct (in polynomial time) an equivalent instance of P || Cmax as follows: pj = si (for
i = j), and the same z as in 3-Partition.
4. Show that Y = 3-Partition is reducible to X = P || Cmax.
Now we consider any feasible solution to this instance of P || Cmax. Let I be a subset of {1, . . . , n}.
In this solution, the jobs must be scheduled on the processors P1, . . . , Pm such that the completion
time of the jobs on each processor is equal to z = σ/m.
P1 pj , j ∈ I1
0 z = σ/m
P2 pj , j ∈ I2
0 z = σ/m
··
·
··
·
Pm pj , j ∈ Im
0 z = σ/m
Figure 2: We have to solve 3-Partition in order to solve Parallel processor scheduling.
The only way to achieve this is to solve a 3-Partition problem and answer the question if there exists
a partition of {1, . . . , n} into m disjoint sets I1, . . . , Im such that
∑
i∈I1 p2,i = . . . =
∑
i∈Im p2,i = z.
Note that we do not need for this proof that each partition contains exactly 3 elements, i.e. it is
not necessary to assume that z/4 < si < z/2.
Conversely: If there are numbers that add up to exactly z in the 3-Partition instance, then this
leads directly to a solution of P || Cmax.
Result.
P || Cmax is in NP, the input for P || Cmax can be computed in polynomial time from the input
for 3-Partition, the constructed instance of P || Cmax is polynomial related to the length of the
given 3-Partition instance, the largest number in the constructed instance is z and we can reduce
the strongly NP-complete problem 3-Partition to P || Cmax. Therefore, there exists a pseudo-
polynomial transformation from 3-Partition to P || Cmax and this proves that the latter problem
is NP-complete in the strong sense. �
8
Problem 5. Prove: Sequencing within intervals is NP-complete.
Use: Subset Sum ∝ Sequencing within intervals.
Solution: The proof can be found in similar form in the book of Kleinberg and Tardos [KT14], pp.
493–494.
1. X = Sequencing within intervals is in NP.
A certifier takes as a certificate a schedule (given e.g. as starting times for each job) and checks
that the job runs between its release time and deadline.
2. Select a known NP-complete problem Y = Subset Sum.
3. The input for X = Sequencing within intervals can be computed in polynomial time from
the input for Y = Subset Sum.
Consider an instance of Subset Sum with n positive integers s1, s2, . . . , sn, σ =
∑n
j=1 sj and a
positive integer z. We construct (in polynomial time) an equivalent instance of Sequencing within
intervals as follows: pj = sj , rj = 0, dj = σ+ 1 for all j ∈ {1, . . . , n}. In addition, we define for the
1 | rj , dj | instance one more job Jn+1 with pn+1 = 1, rn+1 = z, dn+1 = z + 1. Garey and Johnson
call this job the Enforcer (p. 69 in [GJ79]).
4. Show that Y = Subset Sum is reducible to X = Sequencing within intervals.
Now we consider any feasible solution to the specific instance of Sequencing within intervals. In
this solution, job Jn+1 must be run in the interval [z, z + 1]. This leaves σ available time units for
the first n jobs (that all have release time 0 and deadline σ+ 1). in two separate blocks, namely in
the range from 0 to z and from z + 1 to σ + 1, Thus, the processor must not have any idle time,
when no jobs are running.
P1 pj , j ∈ I pn+1 pj , j /∈ I
0 z z + 1 σ + 1
Figure 3: We have to solve Subset Sum in order to solve 1 | rj , dj |.
The only way to achieve this is to solve a Subset Sum problem as out of the first n numbers
s1, . . . , sn we have to choose a subset I ⊆ {1, . . . , n} such that
∑
j∈I sj = z. These jobs are
scheduled in the interval [0, z), and the remaining jobs are scheduled in the interval [z + 1, σ + 1).
The solution for the specific problem instance of Sequencing within intervals gives us implicitly a
solution for Subset Sum.
Conversely: If there are numbers that add up to exactly z in the Subset Sum instance, then this
leads directly to a solution of the Sequencing within intervals instance.
Result.
Since Sequencing within intervals is in NP, since the input for Sequencing within intervals can be
computed in polynomial time from the input for Subset Sum, and since we can reduce the NP-
complete problem Subset Sum to Sequencing within intervals, Sequencing within intervals must
also be NP-complete. �
9
Problem 6. Prove: Sequencing within intervals is NP-complete.
Use: Partition ∝ Sequencing within intervals.
Solution: Garey and Johnson gave a similar version of this proof in their book on pp. 70-71 [GJ79].
1. Sequencing within intervals is in NP.
A certifier takes as a certificate a schedule (given e.g. as starting times for each job) and checks
that the job runs between its release time and deadline.
2. Select a known NP-complete problem Y = Subset Sum.
3. The input for X = Sequencing within intervals can be computed in polynomial time from
the input for Y = Partition.
Consider an instance of Partition with n positive integers s1, s2, . . . , sn, σ =
∑n
i=1 si and a positive
integer z = dσ/2e. We construct (in polynomial time) an equivalent instance of Sequencing within
intervals as follows: pj = si (for i = j), rj = 0, dj = σ + 1 for all j ∈ {1, . . . , n}. In addition, we
define for the 1 | rj , dj | instance one more job (the Enforcer) Jn+1 with pn+1 = 1, rn+1 = z, and
dn+1 = z+1 if z is even and dn+1 = z if z is odd. If n is odd, then we would have rn+1 = dn+1 = z
so that Jn+1 could not possibly be scheduled. Thus, from now on, let us assume that z is even.
4. Show that Y = Partition is reducible to X = Sequencing within intervals.
Now we consider any feasible solution to this instance of Sequencing within intervals. In this
solution, job Jn+1 must be run in the interval [z, z + 1]. This leaves σ available time units for the
first n jobs (that all have release time 0 and deadline σ + 1) in two separate blocks, namely in the
range from 0 to z and from z + 1 to σ + 1.
P1 pj , j ∈ I pn+1 pj , j /∈ I
0 z = σ/2 z + 1 σ + 1
σ/2 time units σ/2 time units
Figure 4: We have to solve Partition in order to solve Sequencing within intervals.
Thus, the processor must not have any idle time, when no jobs are running. This can be done
only if we can solve the Partition problem, i.e. if there is a partition I ⊆ {1, . . . , n} such that∑
i∈I si =
∑
i 6∈I si = z = σ/2.
Conversely: If there are numbers that add up to exactly z in the Partition instance, then this leads
directly to a solution of the Sequencing within intervals instance.
Result.
Since Sequencing within intervals is in NP, since the input for Sequencing within intervals can
be computed in polynomial time from the input for Partition, and since we can reduce the NP-
complete problem Partition to Sequencing within intervals, Sequencing within intervals must also
be NP-complete. �
10
Problem 7. Prove: Sequencing within intervals is NP-complete in the strong sense.
Use: 3-Partition ∝ Sequencing within intervals.
Solution: We start questions related to prove that a problem is NP-complete in the strong sense
with the scheduling problem with release dates and deadlines that already has been considered
in previous problems. This time, we use 3-Partition to show that Sequencing within intervals is
NP-complete in the strong sense. Garey and Johnson gave a similar version of this proof in their
book on pp. 102-103 [GJ79].
1. Sequencing within intervals is in NP.
A certifier takes as a certificate a schedule (given e.g. as starting times for each job) and checks
that the job runs between its release time and deadline.
2. Select a known (in the strong sense) NP-complete problem Y = 3-Partition.
3. The input for X = Sequencing within intervals can be computed in polynomial time from
the input for Y = 3-Partition.
Consider an instance of 3-Partition with n = 3m positive integers s1, s2, . . . , sn, σ =
∑n
i=1 si and a
positive integer z = σ/m. We construct (in polynomial time) an equivalent instance of Sequencing
within intervals as follows: pj = si (for i = j), rj = 0, dj = σ + (m − 1) for all j ∈ {1, . . . , n}.
In addition, we define for the Sequencing within intervals instance m − 1 enforcers Ji as follows:
pi = 1, ri = iz + i− 1, di = iz + i for i = n+ 1, . . . , n+m− 1.
4. Show that Y = Partition is reducible to X = Sequencing within intervals.
Now we consider any feasible solution to this instance of Sequencing within intervals. In this
solution, the enforcer jobs Ji, i = n+ 1 . . . , n+m−1, must be run in the intervals [iz+ i−1, iz+ i]
as shown in Figure 5.
P1 Jn+1 Jn+2 · · · Jn+m−1
0 z z + 1 2z + 1 2z + 2 (m− 1)z
+m− 2
mz
+m− 1
z z z
Figure 5: We have to solve 3-Partition in order to solve Sequencing within intervals.
This leaves m separate blocks of time (marked gray), each of length exactly z, and since this is
just enough time in total to accommodate all the jobs Jj , j ∈ I = {1, . . . , n}, each block must be
completely filled. These blocks therefore play the same role as the sets I1, I2, . . . , In in the desired
partition of I. The solution for the specific problem instance of Sequencing within intervals gives
us implicitly a solution for 3-Partition.
Conversely: If there are numbers that add up to exactly z in the 3-Partition instance, then this
leads directly to a solution of Sequencing within intervals.
Result.
Sequencing within intervals is in NP, the input for Sequencing within intervals can be computed
in polynomial time from the input for 3-Partition, the constructed instance of Sequencing within
intervals is polynomial related to the length of the given 3-Partition instance, the largest number in
the constructed instance is mz+m− 1 (which is polynomial in z), and we can reduce the strongly
NP-complete problem 3-Partition to Sequencing within intervals. Therefore, there exists a pseudo-
polynomial transformation from 3-Partition to Sequencing within intervals and this proves that the
latter problem is NP-complete in the strong sense (see Lemma 4.1 on p. 101 in [GJ79]). �
11
Problem 8. Prove: F3 || Cmax is NP-complete.
Use: Partition ∝ F3 || Cmax.
Solution:
1. F3 || Cmax is in NP.
A certifier takes as a certificate a schedule (given e.g. as starting times, processing times and
completion times for each job) and checks that the maximum completion time, i.e. the makespan,
is at most the given bound zf .
2. Select a known NP-complete problem Y = Partition.
3. The input for X = F3 || Cmax can be computed in polynomial time from the input for Y =
Partition.
Consider an instance of Partition with n positive integers s1, s2, . . . , sn, σ =
∑n
i=1 si and a positive
integer z = σ/2. We construct (in polynomial time) an equivalent instance of F3 || Cmax as follows:
We are going to define n jobs J1, . . . , Jn, corresponding to s1, . . . , sn, and one additional job Jn+1.
Jobs J1, . . . , Jn: p1,j = 0, p2,j = sj , p3,j = 0 for j = 1, . . . , n (this means that we can schedule n
jobs with processing times that correspond to si whenever we want on processor P2).
In addition to these jobs we define an additional job Jn+1 with p1,n+1 = p2,n+1 = p3,n+1 = z.
Finally we set zf = 3 · z.
4. Show that Y = Partition is reducible to X = F3 || Cmax.
Now we consider any feasible solution to this instance of F3 || Cmax. Imagine, we would only have
to schedule the last job Jn+1 with processing times p1,n+1 = p2,n+1 = p3,n+1 = z on the three
processors P1, P2 and P3. The best we can do (in order to minimize the makespan) is to schedule
this job Jn+1 as depicted in Figure 6 and the resulting makespan is zf = 3 · z.
P1 p1,n+1
0 z = σ/2 3z = zf
P2 p2,n+1
0 z = σ/2 2z 3z = zf
P3 p3,n+1
0 2z 3z = zf
Figure 6: Jn+1 has processing times p1,n+1 = p2,n+1 = p3,n+1 = z.
The question is: Can we schedule the remaining n jobs without increasing the makespan? Again,
as the first n jobs have only operations on processor P2 we can schedule these jobs whenever we
want on processor P2.
P1 p1,n+1 /////////////////////////////////
0 z = σ/2 3z = zf
p2,j,j∈I p2,n+1 p2,j,j∈{1,...,n}\IP2
0 z = σ/2 2z 3z = zf
P3 ///////////////////////////////// p3,n+1
0 2z 3z = zf
Figure 7: We have to solve Partition in order to solve F3 || Cmax.
12
The only way to achieve this is to solve a Partition problem as out of the numbers p2,1, . . . , p2,n we
have to choose a subset I ⊆ {1, . . . , n} such that
∑
j∈I p2,j = z. The processing times p2,j,j∈I sum
up together to z and the processing times p2,j,j∈{1,...,n}\I , sum up together to z as well. Therefore,
a solution to the specific problem instance of F3 || Cmax gives us implicitly a solution for Partition.
Conversely: If there are numbers that add up to exactly z = σ/2 in the Partition instance, then
this leads directly to a solution of the F3 || Cmax instance as show in Figure 7 on page 12.
Result.
Since F3 || Cmax is in NP, since the input for F3 || Cmax can be computed in polynomial time from
the input for Partition, and since we can reduce the NP-complete problem Partition to F3 || Cmax,
F3 || Cmax must also be NP-complete. �
13
Problem 9. Prove: F3 || Cmax is NP-complete in the strong sense.
Use: 3-Partition ∝ F3 || Cmax.
Solution: We proved already that the Flow-Shop Scheduling with three processors (F3 || Cmax)
is NP-complete. In this problem we show that F3 || Cmax is not only NP-complete, it is even
NP-complete in the strong sense. This result has been published by Garey, Johnson, and Sethi in
1976 [GJS76].
1. F3 || Cmax is in NP.
A certifier takes as a certificate a schedule (given e.g. as starting times, processing times, completion
times for each job) and checks that the maximum completion time, i.e. the makespan, is at most
the given bound z.
2. Select a known (in the strong sense) NP-complete problem Y = 3-Partition.
3. The input for X = F3 || Cmax can be computed in polynomial time from the input for
3-Partition.
Consider an instance of 3-Partition with n positive integers s1, s2, . . . , sn, σ =
∑n
i=1 si and a
positive integer z = σ/m.
We construct (in polynomial time) an equivalent instance of F3 || Cmax as follows: Jobs J1, . . . , Jn:
p1,j = 0, p2,j = sj , p3,j = 0 for j = 1, . . . , n (this means that we can schedule n jobs with processing
times that correspond to si whenever we want on the second processor). In addition to these n = 3m
jobs we define m + 1 additional jobs Jn+1, . . . , J4m+1 with p1,n+1 = 0, p2,n+1 = z, p3,n+1 = 2z,
p1,t = 2z, p2,t = z, p3,t = 2z (for t = n + 2, . . . , 4m), p1,4m+1 = 2z, p2,4m+1 = z, p3,4m+1 = 0.
Finally we set zf = (2m+ 1) · z.
4. Show that Y = 3-Partition is reducible to X = F3 || Cmax.
Now we consider any feasible solution to this instance of F3 || Cmax. Imagine, we would only have
to schedule the jobs Jn+1, . . . , J4m+1. The best we can do (in order to minimize the makespan)
is to schedule them in the given order as depicted in Figure 8 and the resulting makespan is
zf = (2m+ 1) · z. Note that a makespan of value < (2m+ 1) · z cannot be achieved for these m+ 1
jobs as each one of these jobs will incur a delay of at least z at the start of processor P3 and the
sum of the processing times of the jobs Jn+1, . . . , J4m+1 on P3 is 2m · z.
P1 Jn+2 Jn+3 . . . J4m+1 /////
0 2z 4z 2mz (2m+ 1)z
P2 Jn+1 Jn+2 Jn+3 . . . J4m+1
0 z 2z 3z 4z 5z 2mz (2m+ 1)z
P3 ///// Jn+1 Jn+2 Jn+3 J4m
0 z 3z 5z (2m− 1)z (2m+ 1)z
Figure 8: Schedule for F3 || Cmax.
The question is: Can we schedule the first n = 3m jobs without increasing the makespan? Again, as
the first n jobs J1, . . . Jn have only operations on processor P2 we can schedule these jobs whenever
we want on processor P2. On P2, there are m gaps of idle time of length z each (marked gray
in Figure 8) and if we do not want to increase the makespan, there must be a way to split the
first n jobs into these gaps. The only way to achieve this is to solve a 3-Partition problem and
answer the question if there exists a partition of {1, . . . , n} into m disjoint sets I1, . . . , Im such that∑
i∈I1 p2,i = . . . =
∑
i∈Im p2,i = z. These subsets will fit into the gaps in our schedule. Note that
we do not need for this proof that each partition contains exactly 3 elements, i.e. it is not necessary
to assume that z/4 < si < z/2.
Conversely: If there are numbers that add up to exactly z in the 3-Partition instance, then this
leads directly to a solution of F3 || Cmax.
14
Result.
F3 || Cmax is in NP, the input for F3 || Cmax can be computed in polynomial time from the input
for 3-Partition, the constructed instance of F3 || Cmax is polynomial related to the length of the
given 3-Partition instance, the largest number in the constructed instance is (2m + 1)z (which is
polynomial in z), and we can reduce the strongly NP-complete problem 3-Partition to F3 || Cmax.
Therefore, there exists a pseudo-polynomial transformation from 3-Partition to F3 || Cmax and
this proves that the latter problem is NP-complete in the strong sense. �
[Example 6] Consider the problem instance of F3 || Cmax in Table 1.
J1 J2 J3 J4 J5 J6 J7 J8 J9 J10 J11 J12 J13 J14 J15 J16 J17
P1 0 0 0 0 0 0 0 0 0 0 0 0 0 28 28 28 28
P2 1 2 2 3 3 3 4 6 7 7 8 10 14 14 14 14 14
P3 0 0 0 0 0 0 0 0 0 0 0 0 28 28 28 28 0
Table 1: Problem instance of F3 || Cmax that is used for the reduction from 3-Partition.
The schedule as described in the proof is displayed in Figure 9.
P1 J14 J15 J16 J17 /////
0 2z 4z 6z 8z 9z
P2 Jn+1 Jn+2 Jn+3 . . . J4m+1
0 z 2z 3z 4z 5z 6z 7z 8z 9z
P3 ///// J13 J14 J15 J16
0 z 3z 5z 7z 9z
Figure 9: Schedule for a specific problem instance of F3 || Cmax.
In this instance, we have n = 3m = 12, m = 4, σ = 56, z = 56/4 = 14. Jobs Jn+1, . . . , J4m+1 =
J13, . . . , J17 are the enforcers that are used in the proof as a framework in which 3-Partition must
be included. A makespan of value < (2m + 1 = 9) · z cannot be achieved for these m + 1 = 5
jobs as each one of these jobs will incur a delay of at least z = 14 at the start of processor P3
and the sum of the processing times of the jobs Jn+1, . . . , J4m+1 on P3 is 2m · z = 8z. The
question is: Can we schedule the first n jobs J1, . . . J12 without increasing the makespan? As the
first n = 12 jobs have only operations on processor P2, we can schedule these jobs whenever we
want on processor P2. On P2, there are m = 4 gaps of idle time of length z = 14 each (marked
white in Figure 9) If we do not want to increase the makespan, there must be a way to split these
n = 12 jobs into these gaps. The only way to achieve this is to solve a Partition problem and
answer the question if there exists a partition of {1, . . . , n = 12} into m = 4 disjoint sets I1, . . . , I4
such that
∑
i∈I1 p2,i =
∑
i∈I2 p2,i =
∑
i∈I3 p2,i =
∑
i∈I4 p2,i = z = 14. One possible partition is
{10, 4}, {8, 6}, {7, 3, 3, 1}, {7, 3, 2, 2} with the corresponding index sets I1 = {12, 7}, I2 = {11, 8},
I3 = {10, 6, 5, 1}, I4 = {9, 4, 3, 2}.
15
Problem 10. Prove: Zero Subset Sum is NP-complete.
Use: Subset Sum ∝ Zero Subset Sum.
Why does proof by restriction not work?
Solution: Proof by restriction does not work because Zero Subset Sum does NOT contain Subset
Sum as a special case (it is the other way around). Therefore we cannot focus on the target problem
(Zero Subset Sum) itself and attempt to restrict away its inessential aspects until a known NP-
complete problem (Subset Sum) appears [GJ79], p.64.
1. X = Zero Subset Sum is in NP.
Given a list of n integers s1, s2, . . . , sn with σ =
∑n
i=1 si. A certifier takes as a certificate the subset
I ⊆ {1, . . . , n} that is purported to add up to 0. In polynomial time (at most n− 2 additions and
1 comparison between the sum and 0), we can compute the sum of these integers and verify that
this sum is equal to 0.
2. Select a known NP-complete problem Y = Subset Sum.
3. The input for X = Zero Subset Sum can be computed in polynomial time from the input for
Y = Subset Sum.
We construct a specific problem instance of Zero Subset Sum as follows: Consider an instance of
Subset Sum with n positive integers s1, s2, . . . , sn, σ =
∑n
i=1 si and a value z. s1, . . . , sn (Zero
Subset Sum) = s1, . . . , sn (Subset Sum). Add some more input so that it will be a special problem
instance for Zero Subset Sum: sn+1 (Zero Subset Sum) = −z. Garey and Johnson call this job the
Enforcer (p. 69 in [GJ79]). in fact, the main idea for the proof is to come up with this additional
integer sn+1 = −z in the Zero Subset Sum Problem instance.
Clearly, the input for Zero Subset Sum can be computed in polynomial time from the input for
Subset Sum.
4. Show that Y = Subset Sum is reducible to X = Zero Subset Sum.
Now we consider any feasible solution to this specific instance of Zero Subset Sum. In this solution,
a subset I ⊆ {1, . . . , n} of the the integers s1, . . . , sn must sum up to z, so that
∑
i∈I si − z = 0.
Therefore, a solution to the specific problem instance of Zero Subset Sum gives us implicitely a
solution for Subset Sum.
Conversely: If there are numbers that add up to exactly z in the Subset Sum instance, then
this yields directly to a solution of the specific problem instance of Zero Subset Sum as then∑
i∈I si − z = 0.
Result.
Since Zero Subset Sum is in NP, since the input for Zero Subset Sum can be computed in polynomial
time from the input for Subset Sum, and since we can reduce the NP-complete problem Subset
Sum to Zero Subset Sum, Zero Subset Sum must also be NP-complete. �
16
Problem 11. Prove: Partition is NP-complete.
Use: Subset Sum ∝ Partition.
Why does proof by restriction not work?
Solution: Proof by restriction does not work because Partition does NOT contain Subset Sum as
a special case (it is the other way around). Therefore we cannot focus on the target problem
(Partition) itself and attempt to restrict away its inessential aspects until a known NP-complete
problem (Subset Sum) appears [GJ79], p.64.
1. X = Partition is in NP.
Given a list of n positive integers s1, s2, . . . , sn with σ =
∑n
i=1 si and a positive integer z = σ/2.
A certifier takes as a certificate the subset I ⊆ {1, . . . , n} that is purported to add up to z = σ/2.
In polynomial time (at most n− 2 additions and 1 comparison between integers), we can compute
the sum of these integers and verify that this sum is equal to z.
2. Select a known NP-complete problem Y = Subset Sum.
3. The input for X = Partition can be computed in polynomial time from the input for Y =
Subset Sum.
Consider an instance of Subset Sum with n positive integers s1, s2, . . . , sn and a value z. We
construct an equivalent instance of Partition as follows: s1, . . . , sn (Partition) = s1, . . . , sn (Subset
sum). σ =
∑n
i=1 si. In addition, we define for the Partition instance two more NUMBERS (not
jobs!) (Garey and Johnson introduce the term Enforcer for such jobs [GJ79], p. 69) as follows.
Then we set sn+1 = 2σ − z and sn+2 = σ + z. Clearly, the input for Partition can be computed in
polynomial time from the input for Subset Sum.
4. Show that Y = Subset Sum is reducible to X = Partition.
The following is clear: Partition is just a special case of Subset Sum (the target value z, that is
flexible in Subset Sum, is always z = σ/2 in Partition). And when we therefore can solve Subset
Sum for an arbitrary value of z, then we can as well solve Partition for z = σ/2.
But the other direction is not so obvious: How can we show that there are problem instances where
we have to solve Partition in order to solve Subset Sum?
Now we consider any feasible solution to this special problem instance of Partition. In this solution,
the jobs sn+1 and sn+2 cannot be in the same subset A as their sum (3σ) is too big to be part of
the same partition (all other jobs add up to just σ and the sum of all of the numbers s1, . . . , sn+2
is exactly 4σ).
Partition 1 sn+1 sj , j ∈ A
0 2σ − z 2σ
Partition 2 sn+2 sj , j 6∈ A
0 σ + z 2σ
Figure 10: We have to solve Subset Sum in order to solve Partition.
The only way to achieve this is to solve a Subset Sum problem as out of the first n numbers
s1, . . . , sn we have to choose a subset I ⊆ {1, . . . , n} such that
∑
j∈I sj = z. The numbers in I
sum up together with sn+1 to 2σ and the numbers in {1, . . . , n} \ I sum up together with sn+2 to
2σ as well.
Therefore, a solution to the specific problem instance of Partition gives us implicitely a solution
for Subset Sum.
Conversely: When we therefore can solve Subset Sum for an arbitrary value of z, then we can as
well solve Partition for z = σ/2.
Result.
Since Partition is in NP, since the input for Partition can be computed in polynomial time from the
input for Subset Sum, and since we can reduce the NP-complete problem Subset Sum to Partition,
Partition must also be NP-complete. �
17
Problem 12. Prove: Minimum Tardiness Sequencing is NP-complete.
Use: Clique ∝ Minimum Tardiness Sequencing.
Solution:
The proof is from Garey and Johnson [GJ79], pp. 73–74.
18
Problem 13. Prove: Clique is NP-complete.
Use: Vertex Cover ∝ Clique.
Solution
Garey and Johnson [GJ79] show that Clique and Vertex Cover are ”really just different ways of
looking at the same problem” [GJ79], p.53. in what follows we provide a reduction from Vertex
Cover to Clique (@Arth: this proof must be checked.)
1. Clique is in NP.
If a subset of vertices is given as the solution to the clique problem, it can be verified that the
number of vertices is k and that they are all pairwise connected, in polynomial time. Hence, the
clique problem is in NP.
2. Select a known NP-complete problem Y = Vertex Cover.
3. The input for X = Clique can be computed in polynomial time from the input for Y =
Vertex Cover.
Let G consist of all possible edges between vertices in G that are not present in G i.e., G = (V,
E), where E = (u,v) : u,v ∈ V, u 6= v, (u,v) /∈ E.
We need to scan over all pairs of vertices in the graph G, and generate an edge if there isn’t an edge
between the pair, to generate the complement graph G. This operation can be done in polynomial
time.
4. Show that Y = Vertex Cover is reducible to X = Clique.
Now we consider any feasible solution to this specific instance of Vertex Cover.
(i) Assume that there is a clique C of size k in G. Then if C = V - C, then C has size | V | - k.
However, we know that C forms a clique in G, so there are no edges between vertices of C in G.
Thus, every edge of G is adjacent to some vertex of C, which means that it is a feasible vertex
cover. So we have a vertex cover of size | V | - k.
(ii) Assume that we have a vertex cover V’ of size k in G. Let V ′ = V - V’, which has size | V ′ | -
k. Every edge in G is connected to some vertex of V’ since it is a vertex cover. This means if u,v
∈ V ′, there can be no edge (u,v) ∈ E. But if there are no such edges in E, then (u,v) ∈ E for any
such u,v ∈ V ′. Thus, V ′ forms a clique in G, and we have a clique of size | V ′ | - k.
Thus, we can change any instance of vertex cover problem into an instance of the clique problem.
Given a graph G = (V, E) and integer k, we just need to determine whether a clique of size | V |
- k exists in G. If it exists then G has a vertex cover of size k, else it does not.
Conversely, when there is a solution to the specific problem instance of Clique, then this yields
directly to a solution of the specific problem instance of Vertex Cover.
Result.
Since Clique is in NP, since the input for Clique can be computed in polynomial time from the
input for Vertex Cover, and since we can reduce the NP-complete problem Vertex Cover to Clique,
Clique must also be NP-complete. �
19