21CS42 2023

C BYREGOWDA INSTITUTE OF TECHNOLOGY

Department of CSE & AIML

Module-5-Notes
Contents
Backtracking:

General method, solution using back tracking to N-Queens problem, Sum of subsets problem,
Graph coloring, Hamiltonian cycles Problems.

Branch and Bound:

Assignment Problem, Travelling Sales Person problem, 0/1 Knapsack problem

NP-Complete and NP-Hard problems:

Basic concepts, non- deterministic algorithms, P, NP, NP Complete, and NP-Hard classes.

Dept. of CSE AIML, CBIT, Kolar Page 1

 21CS42 2023

MODULE – 5

5.1. Backtracking

Many problems which deal with searching for a set of solutions or which ask for an optimal
solution satisfying some constraints can be solved using the backtracking formulation.
 Name was first coined by D H Lehmer in 1950s.
 The desired solution is expressible as an n-tuple (x1,….,xn) where, xi are chosen from
some finite set Si.
 The problem to be solved calls for finding one vector that maximizes (or minimizes or
satisfies) a criterion function P(x1,….,xn).Sometimes it seeks all vectors that satisfy P.
For example, sorting the array of integers in a[1:n] is a problem whole solution is
expressible by an n-tuple, where xi is the index in a of the ith smallest solution.
o The criterion function P is the inequality a[xi]<=a[xi+1] for 1<=i<n.
o The set Si is finite and includes integers 1 through n.
 Consider that miis the size of the set Si. There are m=m1m2…mn n-tuples that are
possible candidates for satisfying the function P. The backtracking algorithm
yields the same answer with far fewer than m trials.
Basic Idea
 Build up solution vector one component at a time.
 Use modified criterion functions Pi(x1,….,xi) called bounding functions to test
whether the vector being formed has any chance of success.
Advantage
If it is realized that the pal vector (x1,x2,….xi) can in no way lead to an optimal solution, then
mi+1…..mn possible test vectors can be ignored entirely.

5.1.1. General Approach

Definition 5.1
Explicit constraints are rules that restrict each xi to take on values only from a given set.
Common examples of explicit constraints are

The explicit constraints depend on the particular instance I of the problem being solved. All
tuples that satisfy the explicit constraints define a possible solution space for I.

Definition 5.2
The implicit constraints are rules that determine which of the tuples in the solution space of I
satisfy the criterion function. Thus, implicit constraints describe the way in which the xi must
relate to each other.

Dept. of CSE AIML, CBIT, Kolar Page 2

 21CS42 2023

Example 5.1: 8-queens

Place 8 queens on an 8×8 chessboard so that no two “attack”  no two are on the same
row, column, or diagonal.
- Number the rows and columns of the chessboard 1 through 8.
- Number the queens also 1 through 8.
- Assume that given queen i is to be placed on row i, since each queen must be
on different row.
 All solutions for 8-queens problem can be represented as 8-tuples (x1,….,x8). Here,
xi represents column on which queen i is placed.
 The explicit constraints are Si={1,2,3,4,5,6,7,8}, 1 ≤ i ≤ 8.
o The solution space consists of 88 8-tuples.
 The implicit constraints are that
o No two xi s can be the same.
o All queens must be on different columns,
o No two queens can be on the same diagonal.
 The first of these two constraint implies that all solutions are permutations of the 8-
tuple (1,2,3,4,5,6,7,8). Size of the solution space is reduced from 88 tuples to 8!
tuples.
 The solution in Figure 5.1 is (4,6,8,2,7,1,3,5) expresses as 8-tuple

Figure 5.1: One solution to the n-queens problem

Example 5.2: Sum of Subsets

Given the positive numbers wi, 1 ≤ i ≤ n, and m, find all the subsets of the wi whose sums are
m.
For examples, consider n=4, (w1,w2,w3,w4)=(11,13,24,7) and m=31,
The desired subsets are (11,13,7) and (24,7).
Rather than representing the solution vector by wi, represent the solution vector by giving
indices these wi which sum to m. Hence the solution vectors are (1,2,4) and (3,4). Therefore,
the solutions are k-tuples (x1,x2,….,xk), 1≤k≤n and different solutions have different sized
tuples.

Dept. of CSE AIML, CBIT, Kolar Page 3

 21CS42 2023

Formulation 1
 The explicit constraints require xiϵ{j|j is an integer and 1≤j≤n}
 The implicit constraints require that
o No two be the same and
o The sum of the corresponding wi’s be m.
 Avoid generating multiple instances of the same subset (example, (1,2,4) &
(1,4,2) represent same solution). Hence, another implicit constraint is
xi<xi+1,1≤i≤k.
Formulation 2
 Each solution subset is represented by an n-tuple (x1,x2,…,xn) such that
xiϵ{0,1},1≤i≤n.
o xi=0 if wi is not chosen
o xi=1 if wi is chosen.
 Therefore, the solutions for the above instances are (1,1,0,1) and (0,0,1,1).
Solution using a fixed tuple.
 The solution space consists of 2n distinct tuples.

5.1.2. n-Queens Problem

Problem: place n queens on an n×n chessboard so that no two queens attack each other by
being in the same row or in the same column or on the same diagonal.
 For n=1,the problem has a trivial solution
 There is no solution for n=2 and n=3.
 Consider 4-queens problem and solve by backtracking.
Since each of the four queens has to be placed in its own row, all we need to do
is to assign a column for each queen on the board presented in Figure 5.2.

Figure 5.2: Board for the 4-queens problem

i. Start with the empty board
ii. Place queen 1 in the first possible position of its row, which is in column 1 of
row 1
iii. Place queen 2, after trying unsuccessfully columns 1 and 2, in the first
acceptable position for it, which is square (2, 3), the square in row 2 and
column 3.
This proves to be a dead end because there is no acceptable position for queen 3.
iv. The algorithm backtracks and puts queen 2 in the next possible position at (2, 4)
v. Then queen 3 is placed at (3, 2), which proves to be another dead end.
vi. The algorithm then backtracks all the way to queen 1 and moves it to (1, 2).
vii. Queen 2 then goes to (2, 4), queen 3 to (3, 1), and queen 4 to (4, 3), which is a
solution to the problem.

Dept. of CSE AIML, CBIT, Kolar Page 4

 21CS42 2023

Figure 5.3: State-space tree of solving the four-queen problem by backtracking.

To find other solution, the algorithm can simply resume its operations at the leaf at which it
stopped.

NOTE: A single solution to the n-queens problem for any n ≥ 4 can be found in linear time.

5.1.3. Sum of Subsets Problem

Problem: find a subset of a given set S = {S1, S2,….., ,Sn } of n positive integers whose sum is
equal to a given positive integer d.
For example, A = {1, 2, 5, 6, and 8} and d = 9, there are two solutions:
 {1, 2, 6} and
 {1, 8}
Procedure:
Sort the set’s elements in increasing order.
Assume, a1<a2<….<an
The state-space tree can be constructed as a binary tree like that in Figure 5.4 for the
instance A= {3, 5, 6, 7} and d = 15.

Dept. of CSE AIML, CBIT, Kolar Page 5

 21CS42 2023

Figure 5.4: Complete state-space tree of the backtracking algorithm applied to the instance
A={3, 5, 6, 7} and d=15of the subset-sum problem. The number inside a node is the sum of
the elements already included in the subsets represented by the node. The inequality below a
leaf indicates the reason for its termination.

 The root of the tree represents the starting point, with no decisions about the given
elements made
 Its left and right children represent, respectively, inclusion and exclusionofa1 in a set
being sought.
 Going to the left from a node of the first level corresponds to inclusion ofa2while
going to the right corresponds to its exclusion, and so on.
A path from the root to a node on the ith level of the tree indicates which of the first i numbers
have been included in the subsets represented by that node.
Record the value of s, the sum of these numbers, in the node.
 If s is equal to d, we have a solution to the problem.
 If all the solutions need to be found, continue by backtracking to the node’s parent.
 If s is not equal to d terminate the node as non-promising if either of the following
two inequalities hold.

Backtracking Algorithm

An output of a backtracking algorithm can be thought of as an n-tuple (x1,x2,...,xn) where each

coordinate xi is an element of some finite linearly ordered set Si. Each Si is the set of integers
(column numbers) 1 through n.
 The tuple may need to satisfy some additional constraints. Depending on the
problem, all solution tuples can be of the same length and of different lengths.
A backtracking algorithm generates, explicitly or implicitly, a state-space tree; its nodes
represent partially constructed tuples with the first i coordinates defined by the earlier actions
of the algorithm.

Dept. of CSE AIML, CBIT, Kolar Page 6

 21CS42 2023

 If such a tuple (x1,x2,...,xi) is not a solution, the algorithm finds the next element in
Si+1 that is consistent with the values of (x1,x2,...,xi) and the problem’s constraints,
and adds it to the tuple as its (i+1)st coordinate.
 If such an element does not exist, the algorithm backtracks to consider the next
value of xi , and so on.
To start a backtracking algorithm, the following pseudocode can be called for i=0;
X[1..0] represents the empty tuple.

Tricks to reduce the size of a state-space tree

i. Exploit the symmetry often present in combinatorial problems, or
ii. Pre-assign values to one or more components of a solution

Estimate the size of the state-space tree of a backtracking algorithm

Generating a random path from the root to a leaf and using the information about the number
of choices available during the path generation to estimate the size of the tree.

NOTE on BACKTRACKING
i. It is typically applied to difficult combinatorial problems for which no efficient
algorithms for finding exact solutions possibly exist
ii. Backtracking at least holds a hope for solving some instances of nontrivial sizes
in an acceptable amount of time.
iii. Even if backtracking does not eliminate any elements of a problem’s state space
and ends up generating all its elements, it provides a specific technique for doing
so, which can be of value in its own right.

5.1.4. Graph Coloring

Let G be a graph and m be a given positive integer.

Problem: Color the node of G in such a way that no two adjacent nodes have the same color
yet only m colors are used.m-color ability decision problem

If d is the degree of the given graph, then it can be colored with d+1 colors. m-color ability
optimization problemconsiders smallest integer m for which the graph G can be colored.
Where m is chromatic number of the graph.

Dept. of CSE AIML, CBIT, Kolar Page 7

 21CS42 2023

Consider the graph in Figure 5.5.

Figure 5.5: An example graph and its coloring.

 The above graph can be colored with three colors 1,2, and 3 represented next to
each node.
 Three colors are needed to color this graph and hence its chromatic number is 3.
Planar graph
A planar graph can be drawn in a plane such that no two edges cross each other.
Consider an example for m-color ability decision problem i.e. 4-color problem for planar
graph.

Problem: Given any map, can the regions be colored in such a way that no two adjacent
regions have the same color, yet only 4 colors are needed.
Each region of the map becomes a node, and if two regions are adjacent, then the
corresponding nodes are joined by an edge.

Figure 5.6: A map and its planar graph representation.

Figure 5.6 shows a map with 5 regions and its corresponding graph. This map requires 4
colors.

NOTE: No map that required more than 4 colors had ever been found. Consider, representing
a graph by its adjacency matrix G[1:n, 1:n], where G[i,j]=1 if (i,j) is an edge of G, and
G[i,j]=0 otherwise.

The colors are represented by the integers 1,2,…,m and the solutions are given by the n-tuple
(x1,x2,…,xn), where xi is the color of the node i. Using the recursive backtracking algorithm,
the resulting algorithm is mColoring as given below.

Dept. of CSE AIML, CBIT, Kolar Page 8

 21CS42 2023

State space tree used  degree m

height n+1

Each node at level i has m children corresponding to m possible assignments to xi, 1≤i≤n.
 Nodes at level n+1 are leaf nodes

Figure 5.7: State space tree for m Coloring when n=3 and m=3.
M Coloring
 First assign the graph to its adjacency matrix, setting the array x[ ] to 0.
 Invoke the statement mColoring(1).
 The main loop of mColoring
o Repeatedly picks an element from the set of possibilities,
o Assigns it to xk, and
o Calls mColoring recursively.

Dept. of CSE AIML, CBIT, Kolar Page 9

 21CS42 2023

Figure 5.8: A 4-node graph and all possible 3-colorings

In Figure 5.8, the tree is generated by m Coloring.
 Each path to leaf represents a coloring using at most 3 colors.
 After choosing x1=2 and x2=1, the possible choices for x3 are 2 and 3.
 After choosing x1=2 and x2=1, and x3=2, possible values for x4 are 1 and 3. And so
on.
Computing time for m Coloring:
The number of internal nodes in the state space tree is 𝑛−1 𝑖
𝑖=0 𝑚 . At each internal node, O(mn)
time is sent by Next Value to determine the children corresponding to legal coloring.
The total time is bounded by.

Dept. of CSE AIML, CBIT, Kolar Page 10

 21CS42 2023

5.1.5. Hamilton Cycles

Let G=(V,E) be a connected graph with n vertices. A Hamilton Cycle is a round-trip path
along ‘n’ edges of ‘G’ that visits every vertex once and returns to its starting position. Sir
William Hamilton
If a Hamilton Cycle begins at some vertexv1ϵG and the vertices of G are visited in order v1,
v2,…,vn+1, then the edges (vi,vi+1) are in E, 1in and the vi are distinct except for v1 and
vn+1which are equal.

Figure 5.9: Two graphs, one containing a Hamilton Cycle.

In Figure 5.9,
 The graph G1 contains a Hamilton Cycle 1,2,8,7,6,5,4,3,1
 The graph G2 contains no Hamilton Cycle.

To find whether a graph contains Hamilton Cycle

Solution: Backtracking algorithm. The graph is either directed or undirected.

Output: Distinct cycles.

The backtracking solution vector (x1,….,xn) is defined so that xi represents the ith visited vertex
of the proposed cycle.

To compute the set of possible vertices for xk if(x1,..,xk-1)is already chosen,

 If k=1, then x1 can be any one of the n vertices.
 Set x1=1 to avoid printing same cycle n times.
 If 1<k<n, the xk can be any vertex v that is distinct from x1,x2,…xk-1, and v is
connected by an edge to xk-1.
 The vertex xn can only be the one remaining vertex, and it must be connected to
xn-1 and x1.
The Next Value(k)given below determines next vertex for the proposed cycle.

Dept. of CSE AIML, CBIT, Kolar Page 11

 21CS42 2023

Using Next Value a recursive backtracking schema can be particularized to find

all Hamilton Cycles as shown in algorithm given below:

 The algorithm starts by first initializing the adjacency matrix G[1:n,1:n]

 Then sets x[2:n] to zero and x[1] to 1
 Then execute Hamiltonian (2).

5.2. Branch and Bound

A feasible solution is a point in the problem’s search space that satisfies all the problem’s
constraints.
An optimal solution is a feasible solution with the best value of the objective function
Compared to backtracking, branch-and-bound requires two additional items:
 A way to provide, for every node of a state-space tree, a bound on the best value of
the objective function on any solution that can be obtained by adding further
components to the partially constructed solution represented by the node.

Dept. of CSE AIML, CBIT, Kolar Page 12

 21CS42 2023

 The value of the best solution seen so far.

With this information, compare a node’s bound value with the value of the best
solution seen so far.
The principal idea of the branch-and-bound technique.
 If the bound value is not better than the value of the best solution seen so far, the
node is non-promising and can be terminated.
 No solution obtained from it can yield a better solution than the one already available
A search path is terminated at the current node in a state-space tree of a branch-and-bound
algorithm for any one of the following three reasons:
i. The value of the node’s bound is not better than the value of the best solution seen so
far.
ii. The node represents no feasible solutions because the constraints of the problem are
already violated.
iii. The subset of feasible solutions represented by the node consists of a single point
and hence no further choices can be made

5.2.1. Assignment Problem

Problem: assigning n people to n jobs so that the total cost of the assignment is as small as
possible.
An instance of the assignment problem is specified by an n×n cost matrix C so that we can
state the problem as follows:
“Select one element in each row of the matrix so that no two selected elements are in the same
column and their sum is the smallest possible.”
Consider C as follows:

To find a lower bound on the cost of an optimal selection without actually solving the
problem:
 The cost of any solution, including an optimal one, cannot be smaller than the sum of
the smallest elements in each of the matrix’s rows.
 For the instance sum is 2+3+1+4=10.
 For any legitimate selection that selects 9 from the first row, the lower bound will be
9+3+1+4=17.

The problem’s state space tree deals with the order in which the tree nodes will be generated.
Rather than generating a single child of the last promising node as in backtracking, generate
all the children of the most promising node among on terminated leaves in the current tree.
Which of the nodes is most promising?
 Compare the lower bounds of the live nodes.
 Consider a node with the best bound as most promising,

Dept. of CSE AIML, CBIT, Kolar Page 13

 21CS42 2023

This variation of the strategy is called the best-first branch-and-bound.

Start with the root that corresponds to no elements selected from the cost matrix C.
 The lower-bound value for the root, denoted lb, is 10.
 The nodes on the first level of the tree correspond to selections of an element in the
first row of the matrix, i.e., a job for person a (Figure 5.10).

Figure 5.10: Levels 0 and 1 of the state-space tree for the instance of the assignment
problem being solved with the best-first branch-and-bound algorithm. The number above a
node shows the order in which the node was generated. A node’s fields indicate the job
number assigned to person a and the lower bound value, lb, for this node.

 There are four live leaves—nodes 1 through 4—that may contain an optimal
solution
 The most promising of them is node 2 because it has the smallest lower-bound value.
 Using best-first search strategy, branch out from that node first by considering the
three different ways of selecting an element from the second row and not in the
second column—the three different jobs that can be assigned to person b (Figure
5.11)

Figure 5.11: Levels 0, 1, and 2 of the state-space tree for the instance of the
assignment problem being solved with the best-first branch-and-bound algorithm.

 Of the six live leaves—nodes 1, 3, 4, 5, 6, and 7—that may contain an optimal

solution, choose the one with the smallest lower bound, node 5.

Dept. of CSE AIML, CBIT, Kolar Page 14

 21CS42 2023

o First, we consider selecting the third column’s element from c’s row, this leaves us
with no choice but to select the element from the fourth column of d’s row.
o This yields leaf 8 (Figure 5.12) which corresponds to the feasible solution
{a→2,b→1,c→3,d→4}with the total cost of 13.

Figure 5.12: Complete state-space tree for the instance of the assignment problem
solved with the best-first branch-and-bound algorithm.

 Its sibling, node 9, corresponds to the feasible solution {a→2, b→1,c→4,d→3}with

the total cost of 25. Since its cost is larger than the cost of the solution represented by
leaf 8, node 9 is simply terminated.

 The lower-bound values of nodes1, 3, 4, 6, and 7 are not smaller than 13, the value
of the best selection seen so far (leaf 8).
Hence, terminate all of them and recognize the solution represented by leaf 8 as
the optimal solution to the problem

5.2.2. Travelling Sales Person Problem

It is possible to apply the branch-and-bound technique to instances of the traveling salesman

problem with a reasonable lower bound on tour lengths. To obtain lower bound find the
smallest element in the intercity distance matrix D and multiply it by the number of cities n.

Dept. of CSE AIML, CBIT, Kolar Page 15

 21CS42 2023

Figure 5.13: (a) weighted graph. (b) State-space tree of the branch-and-bound
algorithm to find a shortest Hamiltonian circuit in this graph. The list of vertices in a
node specifies a beginning part of the Hamiltonian circuits represented by the node.

It is possible compute a lower bound on the length l of any tour as follows.

i. For each cityi,1 ≤ i ≤ n, find the sums i of the distances from city i to the two
nearest cities
ii. Compute the sum s of these n numbers
iii. Divide the result by 2, and
iv. if all the distances are integers, round up the result to the nearest integer:
(5.1)
For the instance in Figure 5.12a, formula 5.1) yields

v. For any subset of tours that must include particular edges of a given graph,
modify lower bound (lb) accordingly.

For example, for all the Hamiltonian circuits of the graph in Figure 5.12a that must include
edge (a, d) by summing up the lengths of the two shortest edges incident with each of the
vertices, with the required inclusion of edges (a, d)and(d, a), the lower bound is:

Apply the branch-and-bound algorithm; with the bounding function given by formula 5.1.to
find the shortest Hamiltonian circuit for the graph in Figure 5.12a.

To reduce the amount of potential work

i. Without loss of generality, consider only tours that start at a.
ii. Since the graph is undirected, generate only tours in which b is visited before c.
iii. After visitingn−1=4 cities, a tour has no choice but to visit the remaining
unvisited city and return to the starting one. The State space tree is given in
Figure 5.12b.

Dept. of CSE AIML, CBIT, Kolar Page 16

 21CS42 2023

5.2.3. 0/1 Knapsack Problem

Problem: given items of known weights wi and values vi, i=1,2,. . .,n, and a knapsack of
capacity W, find the most valuable subset of the items that fit in the knapsack.
 Order the items of a given instance in descending order by their value-to-weight
ratios.
 The first item gives the best payoff per weight unit and the last one gives the worst
payoff per weight unit, with ties resolved arbitrarily:

Structure the state-space tree for this problem as a binary tree constructed as follows:
 Each node on the ith level of this tree, 0≤i≤n, represents all the subsets of n items that
include a particular selection made from the first i ordered items.
 This is the path from root to the node: a branch going to the left indicates the
inclusion of the next item, and a branch going to the right indicates its exclusion.

Figure 5.14: State-space tree of the best-first branch-and-bound algorithm for the
instance of the knapsack problem.

 Record the
o Total weight w and
o The total value v of this selection in the node,
o Upper bound ub on the value of any subset that can be obtained by adding
zero or more items to this selection.
 To compute the upper bound ub: add to v,
o The total value of the items already selected,
o the product of the remaining capacity of the knapsack W−wand

Dept. of CSE AIML, CBIT, Kolar Page 17

 21CS42 2023

o the best per unit payoff among the remaining items, which isvi+1/wi+1
(5.2)
For example, apply the branch-and-bound algorithm to the following
instance of knapsack problem:

In Figure 5.14,
 At the root no items have been selected as yet. Hence, both the total weight of the
items already selected w and their total value v are equal to 0.
 The value of the upper bound computed by formula (5.2) is $100.
 Node 1, the left child of the root, represents the subsets that include item 1.
o The total weight and value of the items already included are 4 and $40,
respectively; the value of the upper bound is 40 + (10−4)∗6 = $76.
 Node 2 represents the subsets that do not include item 1.
o w=0, v=$0, and ub=0+(10−0)∗6 = $60.
Since node 1 has a larger upper bound than the upper bound of node 2,
it is more promising for this maximization problem and hence, branch from
node 1 first.
 Its children—nodes 3 and 4—represent subsets with item 1 and with and without item
2, respectively
o The total weight w of every subset represented by node 3 exceeds the
knapsack’s capacity; node 3 can be terminated immediately.
o Node 4 has the same values of w and v as its parent; the upper bound ub is
equal to 40 + (10−4)∗5 = $70.
o Selecting node 4 over node 2 for the next branching, nodes 5 and 6 by
respectively are obtained including and excluding item3.
The total weights and values as well as the upper bounds for these nodes are
computed in the same way as for the preceding nodes.
 Branching from node 5 yields node 7, which represents no feasible solutions, and node
8, which represents just a single subset {1, 3} of value $65.
 The remaining live nodes 2 and 6 have smaller upper bound values than the value of
the solution represented by node 8.
Hence, both can be terminated making the subset {1, 3} of node 8 the optimal solution to the
problem.

Dept. of CSE AIML, CBIT, Kolar Page 18

 21CS42 2023

5.2.3.1. LC Branch and Bound solution

Example [LCBB]:

Figure 5.15: LC branch and bound tree

The Computation of u(1) and c(1) is done as follows:
 The bound u(1) has a value UBound(0,0,0,15).
o UBound scans through the objects from left to right starting from j,
o it adds these objects into the knapsack until the first object that doesn’t fit is
encountered.
o This returns the negation of the total profit of all the objects in the knapsack plus
cw.
 In function UBound,
o C and b start with the value of zero.
o For i=1,2, and 3
 c gets incremented by 2,4, and 6 respectively.
 b gets decremented by 10,0, and 12 respectively.
o When i=4, the test (c + w[i] ≤ m) fails and return value -32.
 Function Bound is similar to UBound, except that it also considers a fraction of the first
object that doesn’t fit the knapsack. Example, the object 4 doesn’t fit and value is 9.
Bound considers a fraction 3/9 of the object 4 and returns -32-3/9*18=-38
 LCBB sets ans = 0 and upper = -32.

Dept. of CSE AIML, CBIT, Kolar Page 19

 21CS42 2023

o The E-node is expanded and two children 2 and 3 are generated. live nodes.
o The cost c(2)=-32, c(3)=-32, u(2)=-32, and u(3)=-27.
o Node-2 is next E-node. Expand and generate 4 and 5. live nodes.
o 4 has least c value and is next E-node. Generate 6 and 7. live nodes.
o Upper is -38.
o Assume 7is next E-node. Generate 8 and 9.
o Node 8 is a solution node. Update upper to -38. Set 8 as live node.
o Node 9 with c(9) > upper is terminated.
o Node 6 and 8 are two live nodes with least c.
o Search terminates at node 8 as answer node.
o Value is -38 with the path 8,7,4,2,1
 Assign values to xi such that .
 To extract values of xi:
o Associate with each node, a one bit field, tag, such that the sequence of the tag bits
from answer node to the root gives xi values.
o Example, tag(2)=tag(4)=tag(6)=tag(8)=1
o Tag sequence for the path 8, 7, 4, 2, 1 is 1011. x4=1,x3=0,x2=1, and x1=1.
To solve knapsack problem using LCBB, specify
i. The structure of nodes in the state space tree being searched.
ii. How to generate the children of a given node.
iii. How to recognize a solution node
iv. A representation of a list of live nodes and a mechanism for adding anode into
the list as well as identifying the least cost node.
To generate x’s children:
 Identify the level of x in state space tree. field used level.
 Set xlevel(x)=1 for left child and xlevel(x)=0 for right child.
 Retain the value cu (capacity unused)
 The evaluation of c(x) and u(x) requires value of profit.
 This value can be retained in the field pe.
 In order to determine the live node, with least c value , compute c(x).
 The c(x) is explicitly stored in ub.
We need nodes with six fields: parent, level, tag, cu, pe, and ub using which the
children of any node can be easily determined.
 The left child is feasible iff cu(x)>= wlevel(x).
o Parent(y)=x
o Level(y)=level(x)+1
o cu(y)=cu(x)-wlevel(x).
o pe(y)=pe(x)+Plevel(x).
o tag(y)=1, and
o ub(y)=ub(x)
The functions to be performed on list of live nodes:
i. test if the list is empty
ii. add nodes, and
iii. Delete a node with a least ub.

Dept. of CSE AIML, CBIT, Kolar Page 20

 21CS42 2023

5.2.3.2. FIFO Branch and Bound solution

Example

Figure 5.16: FIFO branch and bound example

 Initially, node 1 is the E-node and queue of live nodes is empty. upper is
initialized to u(1)= -32.
 Generate nodes from left to right.
 Generate 2 and 3 and add to the queue. Upper value unchanged.
 Node 2 is next E-node. Generate 4 and 5 and add into queue.
 Expand node 3, the next E-node. Generate 6 and 7. C (7) > upper so node 7
immediately killed.
 Expand node 4.generate 8 and 9 and add to queue.
 Update upper to -38.
 5 and 6 are next. Both are not expanded since there c value is > upper.
 Node 8 is next E-node. Generate nodes 10 and 11.
o Node 10 is killed due to infeasibility.
o Node 11’s c value is > upper so killed.
 Expand node 9. Generate 12and 13.
o 13 is killed. its c value > upper.
o Add 12 in queue. It has no children and the search is terminated.
 Output the value of upper and path from node 12 to root.

Dept. of CSE AIML, CBIT, Kolar Page 21

 21CS42 2023

5.3. NP-Complete and NP-Hard problems

5.3.1. Basic Concepts

The best algorithms for their solutions have computing times that cluster into two
groups:
i. Problems whose solutions times are bounded by polynomials of small degree
(O(log n), O(n)).
ii. Problems whose best-known algorithms are non-polynomial (O(n22n), O(2n/2)).
NOTE:
 Algorithms whose computing times are greater than polynomial very quickly
require vast amounts of time to execute.
 Many of the problems for which there are no known polynomial time algorithms
are computationally related. NP-Hard and NP-Complete Problems.
NP-Complete and NP-Hard Problems
 A problem that is NP-Complete has the property that it can be solved in
polynomial time if and only if all other NP-Complete problems can also be
solved in polynomial time.
 If an NP-Hard problem can be solved in polynomial time, then all NP-Complete
problems can be solved in polynomial time.
 All NP-Complete problems are NP-Hard but some NP-Hard problems are not
known to be NP-Complete.

5.3.2. Nondeterministic Algorithms

The algorithms for which the result of every operation is uniquely defined are called
deterministic algorithms.
Algorithms may be made to contain operations whose outcomes are not uniquely defined but
are limited to specified sets of possibilities. The machine executing such operations is allowed
to choose any one of these outcomes subject to a termination condition. Such algorithms are
named as nondeterministic algorithms.

To specify nondeterministic algorithms, three new functions are introduced:

i. Choice(S)  arbitrarily chooses one of the elements of set S.
ii. Failure( )  signals an unsuccessful completion
iii. Success ( )  signals a successful completion
The assignment statement x:=Choice(1,n) can result in x being assigned any of the integers in
range [1,n].
The Failure() and Success() signals are used to define computation of the algorithm. Cannot
be used to affect a return.
NOTE:
 A nondeterministic algorithm terminates unsuccessfully if and only if there exists
no set of choices leading to a success signal.
 The computation times for Choice, Success, and Failure is taken as O(1).

Dept. of CSE AIML, CBIT, Kolar Page 22

 21CS42 2023

 Machine capable of executing a nondeterministic is called a nondeterministic

machine.
Example:

Algorithm : Nondeterministic Search

 No=umber 0 can be output if and only if there is no j such that A[j]= x.

 The complexity of above algorithm isO(1).
Example [Sorting]:

Dept. of CSE AIML, CBIT, Kolar Page 23

 21CS42 2023

Algorithm: Nondeterministic Sorting

Definition:
Any problem for which the answer is zero or one is called a decision algorithm. Any
algorithm that involves the identification of an optimal value of a given cost function is
known as an optimization problem. An optimization algorithm is used to solve
optimization problem
Many optimization problems can be recast into decision problems with the
property that the decision problem can be solved in polynomial time if and only if the
corresponding optimization problem can.
Example: Maximum Clique

Example: 0/1 Knapsack Problem

Let n be the length of the input to the algorithm. Consider that all inputs are integers.
 The length of the input is measured assuming a binary representation. Example,
10 is represented as 1010 whose length is 4.
 A positive integer k has a length of bits when represented in
binary. The length of binary representation of 0 is 1.
 The size n of the input to an algorithm is the sum of the lengths of the individual
numbers being input.

Dept. of CSE AIML, CBIT, Kolar Page 24

 21CS42 2023

Consider a radix r for an input with different representation. Then the length of the
positive number kis .
Since, , the length of any input using radix r (r>1)
representation is c(r)n.
Note: Input is unary form if r=1. Length of positive integer k is k.
Example: Max Clique

Example: 0/1 Knapsack

Definition:
The time required by a nondeterministic algorithm performing on any given input is the
minimum number of steps needed to reach a successful completion if there exists a
sequence of choices leading to such a completion. If not, the time required is O(1).
The complexity of nondeterministic algorithm is O(f(n)) for the inputs of size n.

Example: Knapsack Decision Problem

Dept. of CSE AIML, CBIT, Kolar Page 25

 21CS42 2023

Algorithm: Nondeterministic knapsack algorithm

Example: Max Clique

Algorithm: Nondeterministic clique pseudocode

Example: Satisfiability

Dept. of CSE AIML, CBIT, Kolar Page 26

 21CS42 2023

Algorithm: Nondeterministic satisfiability

5.3.3. The Classes NP-hard and NP-Complete

An algorithm A is polynomial complexity if there exists a polynomial p() such that the
computing time of A is O(p(n)) for every input of size n.
Definition
P is the set of all decision problems solvable by deterministic algorithms in polynomial
time. NP is the set of all decision problems solvable by nondeterministic algorithms in
polynomial time.
Conclusion:

Figure 5.14: Commonly believed relationship between P and NP

Figure 5.14 assumes that P≠NP
Theorem [Cook]: Satisfiability is in P if and only if P=NP.
Definition:

Here, α is a transitive relation.

Definition

Dept. of CSE AIML, CBIT, Kolar Page 27

 21CS42 2023

Figure 5.15: Commonly believed relationship among P, NP, NP-Complete and NP-
Hard problems
 There are NP-hard problems that are not NP-complete.
 Only a decision problem can be NP-complete.
 An optimization problem can be NP-hard.
 Optimization problem cannot be NP-complete whereas decision problem can.
 There also exist NP-hard decision problems that are not NP-complete.
Example:

Definition:
Two problems L1 and L2 are said to be polynomials equivalent if and only if L1αL2 and
L2αL1.

Dept. of CSE AIML, CBIT, Kolar Page 28