Unit 6: Backtracking, Approximation, and Complexity Classes - Subjective Questions

Backtracking is a systematic search technique that constructs a solution incrementally and abandons a partial solution as soon as it determines that the partial solution cannot lead to a valid complete solution.

State-space-tree formulation

• The root represents an empty or initial solution.
• Each internal node represents a partial solution.
• Each edge represents a decision or choice.
• A leaf node represents either a complete solution or a dead end.
• A promising function checks whether a node can still lead to a valid solution.

A generic backtracking procedure is:

1. Choose one candidate for the next component.
2. Test whether the resulting partial solution is promising.
3. If promising, recursively extend it.
4. Otherwise, undo the choice and try another candidate.

Difference from exhaustive search

• Exhaustive search generates and checks every possible candidate.
• Backtracking prunes candidates that violate constraints before they are completed.
• Thus, backtracking often examines far fewer candidates, although its worst-case running time is generally exponential.

Backtracking is commonly used for the n-Queens problem, Hamiltonian circuit, subset-sum, graph coloring, and other constraint-satisfaction problems.

The n-Queens problem asks us to place queens on an chessboard so that no two queens attack each other.

Let denote the column in which the queen of row is placed. Since one queen is placed in each row, only column and diagonal conflicts need to be checked.

Promising condition

A queen placed at row and column is safe with respect to a queen at row if:

• They are not in the same column: .
• They are not on the same diagonal: .

Therefore, a partial solution is promising if, for every ,

Backtracking algorithm

1. Begin with the first row.
2. Try each column in that row.
3. Check whether the new queen conflicts with any previously placed queen.
4. If the placement is safe, recursively place a queen in the next row.
5. If no column is safe, backtrack to the previous row and change its placement.
6. When queens have been placed in all rows, report a solution.

Complexity

• Without pruning, there are row-column assignments.
• Since columns cannot repeat, the search can be bounded by candidate permutations.
• Each promising test may take time in a simple implementation.
• The worst-case time is therefore exponential, while the recursion and position array use auxiliary space.

The algorithm is effective in practice because column and diagonal conflicts prune large parts of the state-space tree.

A Hamiltonian circuit in a graph is a cycle that visits every vertex exactly once and returns to the starting vertex.

Let a graph be with vertices. Store a candidate circuit in an array . Fix one starting vertex, such as , to avoid equivalent rotations.

Backtracking procedure

For each position from to :

• Select a vertex that has not already appeared in the path.
• Verify that it is adjacent to the previously selected vertex.
• Add it to the partial path and recursively fill the next position.
• If no vertex can be selected, backtrack.

After all vertices have been added, verify that the final vertex is adjacent to .

Promising conditions

A vertex is promising at position if:

• .
• does not occur in .
• If , then .

Complexity

At most vertex orderings are examined after fixing the first vertex. Hence, the worst-case running time is , with auxiliary space for the path and recursion stack.

The method is faster than blindly generating all permutations because nonadjacent and repeated vertices are rejected immediately.

In the Subset-Sum problem, we are given positive integers and a target . The objective is to determine whether there is a subset whose sum is exactly .

At level of the state-space tree, the algorithm decides whether to include . Let:

• be the sum of the selected elements.
• be the sum of the unprocessed elements.

Recursive choices

• Include : continue with sum .
• Exclude : continue with sum .

A solution is obtained when .

Pruning conditions for positive inputs

A node can be rejected when:

• , because adding more positive values cannot reduce the sum.
• , because even selecting every remaining item cannot reach the target.

If the values are sorted, additional pruning can be performed when the next inclusion would make the sum exceed .

Complexity

The complete decision tree has up to leaves, so the worst-case time complexity is . The recursion requires auxiliary space.

Pruning may considerably reduce the practical search, but it does not change the exponential worst-case complexity.

Branch and Bound is an exact optimization technique that searches a state-space tree while eliminating subproblems that cannot improve the best solution found so far.

Main components

• Branching: Divides a problem into smaller subproblems by making a decision at each node.
• Bound: Estimates the best objective value that any completion of a partial solution could achieve.
• Incumbent: The best feasible complete solution found so far.
• Pruning: Removes an infeasible node or a node whose bound cannot improve the incumbent.

For a minimization problem, a node can be pruned when:

For a maximization problem, a node can be pruned when:

Node-selection strategies

• FIFO Branch and Bound: Uses a queue and explores nodes in breadth-first order.
• LIFO Branch and Bound: Uses a stack and resembles depth-first search.
• Least-cost or best-first Branch and Bound: Uses a priority queue and selects the node with the most favorable bound.

The method remains exact because it prunes only nodes that are infeasible or provably unable to produce a better solution.

In the Assignment Problem, workers must be assigned to jobs. If assigning worker to job costs , the objective is to find a one-to-one assignment minimizing

where is a permutation of the jobs.

State-space tree

• Level represents the job selected for worker .
• A child assigns an unused job to the next worker.
• A leaf represents a complete assignment.

Lower-bound calculation

Suppose a partial assignment has fixed the first workers and has current cost . A simple lower bound is

where is the set of currently unassigned jobs.

This bound may select the same remaining job as the minimum for multiple workers, so it may not be feasible. Nevertheless, it is a valid lower bound because it optimistically underestimates the completion cost.

A tighter bound can be obtained by performing row and column reductions on the remaining cost matrix or by solving a relaxed assignment problem.

Algorithm

1. Insert the root into a min-priority queue.
2. Remove the node with the smallest lower bound.
3. Generate assignments for the next worker.
4. Compute each child's lower bound.
5. Prune infeasible children and those with bounds not better than the incumbent.
6. Continue until the optimal complete assignment is established.

The worst-case complexity is exponential, although good lower bounds can prune many of the possible assignments.

The 0/1 Knapsack Problem contains items with profit and weight , and a knapsack of capacity . Each item is either fully selected or not selected. The objective is

subject to

State-space tree

At level , branch into:

• A child that includes item .
• A child that excludes item .

Items are normally sorted in nonincreasing order of the ratio .

Fractional upper bound

For a node with current profit and weight :

1. Add remaining items completely while the capacity permits.
2. If the next item does not fit, add the fraction that fills the remaining capacity.
3. The resulting fractional-knapsack profit is an upper bound on any feasible 0/1 completion.

If item is the first item that does not fit, the bound has the form

where is the set of remaining items added completely.

Pruning

A node is discarded if:

• Its weight exceeds .
• Its upper bound is no greater than the profit of the incumbent solution.

The algorithm is exact but has worst-case time . The fractional upper bound often makes it much faster in practice.

In the Traveling Salesman Problem (TSP), a salesperson must visit every city exactly once, return to the starting city, and minimize the total travel cost.

Branching

A node represents a partial tour or a set of included and excluded edges. Children are generated by choosing the next unvisited city or by deciding whether a selected edge belongs to the tour.

Reduced-matrix lower bound

Given a cost matrix :

1. Set diagonal entries to infinity because a city cannot be followed immediately by itself.
2. Subtract the smallest finite entry of each row from every finite entry in that row.
3. Add all row minima to the bound.
4. Perform the same operation on columns and add all column minima.

The total reduction cost is a lower bound because any complete tour must choose one outgoing and one incoming edge for every city.

When an edge is selected:

• Add its reduced cost to the node's bound.
• Set row and column to infinity.
• Set the reverse or premature-cycle edge to infinity when necessary.
• Reduce the remaining matrix again.

Search and pruning

• Expand the live node with the smallest lower bound.
• Maintain the cost of the best complete tour as the incumbent.
• Prune any node whose lower bound is at least the incumbent cost.

The algorithm produces an optimal tour, but its worst-case running time remains exponential, commonly described as .

An approximation algorithm is a polynomial-time algorithm that produces a feasible solution with a provable guarantee on how close its objective value is to the optimum. Such algorithms are mainly used for NP-hard optimization problems.

Let denote the optimal value for instance , and let denote the value returned by algorithm .

Minimization problem

An algorithm is a -approximation, where , if

for every instance .

Maximization problem

An algorithm is a -approximation if

An equivalent unified definition is

Important points

• The result must be feasible.
• The algorithm must run in polynomial time.
• A smaller indicates a better guarantee.
• When , the algorithm always returns an optimal solution.

Approximation algorithms differ from ordinary heuristics because an approximation algorithm provides a mathematically proven quality bound.

Given an undirected graph , a vertex cover is a set such that every edge has at least one endpoint in .

Algorithm

1. Initialize .
2. While an uncovered edge remains:
   • Add both and to .
   • Remove all edges incident on either or .
3. Return .

The edges selected by the algorithm form a maximal matching , since no two selected edges share an endpoint and no additional edge can be selected after termination.

Proof of approximation ratio

Any vertex cover must contain at least one endpoint of every edge in . Since the matching edges are vertex-disjoint,

where is an optimal vertex cover.

The algorithm selects both endpoints of every matching edge, so

Therefore,

Hence, the algorithm is a 2-approximation.

The algorithm can be implemented in time using suitable adjacency data structures.

In the Set-Covering Problem, a universe and a family of subsets are given. The objective is to choose as few subsets as possible so that their union is .

Unweighted greedy algorithm

1. Mark every element of as uncovered.
2. Repeatedly select the set containing the largest number of currently uncovered elements.
3. Mark those elements as covered.
4. Stop when every element has been covered.

For the weighted version, where set has cost , select the set minimizing

where is the set of uncovered elements.

Approximation guarantee

If , the greedy algorithm achieves an approximation ratio of

Thus, its solution costs at most times the optimal cost.

Reason for the bound

At each step, the greedy set has no worse cost per newly covered element than the average cost per uncovered element in an optimal cover. Charging each newly covered element this marginal cost and summing the charges gives the harmonic bound.

In the Bin Packing Problem, items of sizes , where , must be packed into the minimum number of unit-capacity bins.

Next Fit

• Maintains only one open bin.
• Places the next item in the current bin if it fits; otherwise, closes that bin and opens a new one.
• It is fast but may waste considerable space.
• Its asymptotic approximation ratio is .

First Fit

• Scans bins in their opening order.
• Places an item into the first bin with enough remaining space.
• Opens a new bin only when no existing bin can hold the item.

Best Fit

• Places an item into the bin that will have the least remaining capacity after insertion.
• It attempts to fill bins as tightly as possible.
• Its worst-case guarantee is similar to that of First Fit.

First Fit Decreasing (FFD)

• Sorts items in nonincreasing order of size.
• Applies First Fit to the sorted list.
• It has the well-known bound

and is often stated using the integer form .

Sorting improves packing because large items, which are difficult to place later, are handled first. FFD takes time with an efficient implementation.

P is the class of decision problems that can be solved by a deterministic algorithm in polynomial time. Formally, a problem is in P if an input of size can be decided in time for some constant .

Examples include:

• Graph connectivity
• Minimum spanning tree decision versions
• Shortest-path decision versions
• Bipartite-graph testing

NP is the class of decision problems for which every yes-instance has a polynomial-size certificate that can be verified in polynomial time by a deterministic algorithm.

Equivalently, NP is the class of problems solvable in polynomial time by a nondeterministic Turing machine.

Example

For the Hamiltonian Circuit problem, a certificate is an ordering of the vertices. A verifier checks in polynomial time that:

• Every vertex occurs exactly once.
• Consecutive vertices are connected by edges.
• The last vertex is connected to the first.

Relationship

Every problem in P is also in NP because a problem that can be solved in polynomial time can certainly have its answer verified in polynomial time. Thus,

Whether remains an unresolved question.

NP

A decision problem is in NP if a proposed solution to every yes-instance can be verified in polynomial time.

NP-Hard

A problem is NP-Hard if every problem in NP can be reduced to in polynomial time:

An NP-Hard problem:

• Need not be a decision problem.
• Need not belong to NP.
• May even be undecidable.

The optimization version of TSP is an example of an NP-Hard problem.

NP-Complete

A decision problem is NP-Complete if:

1. .
2. is NP-Hard.

Examples include:

• SAT and 3-SAT
• Hamiltonian Circuit
• Vertex Cover decision problem
• Subset-Sum decision problem
• TSP decision problem

Key consequence

If any NP-Complete problem is solved in polynomial time, then every problem in NP can be solved in polynomial time, implying

Therefore, NP-Complete problems are regarded as the hardest decision problems within NP.

A polynomial-time reduction from decision problem to decision problem , written , is a polynomial-time computable transformation such that

Thus, an algorithm for can be used to solve after applying the transformation.

Procedure for proving NP-Completeness

To prove that a new problem is NP-Complete:

1. Show that .

   • Identify a polynomial-size certificate.
   • Give a polynomial-time verification procedure.

2. Choose a known NP-Complete problem .

3. Construct a reduction from to .

   • The correct direction is .
   • The transformation must take polynomial time.

4. Prove correctness in both directions.

   • If the original instance is a yes-instance, the transformed instance must be a yes-instance.
   • If the transformed instance is a yes-instance, the original instance must also be a yes-instance.

5. Conclude NP-Hardness and NP-Completeness.

   • The reduction proves that is NP-Hard.
   • Together with , this proves that is NP-Complete.

Reducing to a known NP-Complete problem does not prove that is NP-Hard; the reduction direction is essential.

The decision version asks: given a graph , does contain a cycle that visits every vertex exactly once and returns to the starting vertex?

Membership in NP

A certificate is an ordered sequence

A verifier checks that:

• Every vertex of occurs exactly once in the sequence.
• for .
• .

Using a Boolean array and an adjacency matrix or adjacency lookup structure, these checks take polynomial time. Therefore, Hamiltonian Circuit belongs to NP.

NP-Hardness

NP-Hardness is established by a polynomial-time reduction from a known NP-Complete problem, such as 3-SAT. The reduction constructs graph gadgets representing variables and clauses so that:

• A choice of route through each variable gadget corresponds to a truth assignment.
• Clause gadgets can be visited consistently exactly when the corresponding clauses are satisfied.
• The resulting graph has a Hamiltonian circuit if and only if the original Boolean formula is satisfiable.

Since Hamiltonian Circuit is both in NP and NP-Hard, it is NP-Complete.

The existence of exponential backtracking algorithms does not itself prove NP-Completeness; polynomial verification and a valid NP-Hardness reduction are both required.

The decision version of Subset-Sum asks whether a set of integers contains a subset whose sum is exactly a target .

Membership in NP

A certificate can be an -bit vector , where means that item is selected. A verifier computes

and checks whether it equals . This requires polynomial time in the encoded input size.

NP-Completeness

Subset-Sum is NP-Hard through a polynomial-time reduction from a known NP-Complete problem, such as 3-SAT. Since it also belongs to NP, its decision version is NP-Complete.

Optimization form

An optimization variant may ask for a subset whose sum is as large as possible without exceeding . This form is NP-Hard rather than being described directly as NP-Complete, because NP-Completeness is defined for decision problems.

Pseudo-polynomial algorithm

Dynamic programming solves positive-integer Subset-Sum in time. This is not polynomial in the binary input length because the encoding of needs only bits. Hence, Subset-Sum is called weakly NP-Complete.

Backtracking takes time in the worst case, while dynamic programming is useful when is not very large.

Backtracking and Branch and Bound both explore a state-space tree, but they are designed for different purposes.

Goal

• Backtracking: Primarily finds feasible solutions to constraint-satisfaction or decision problems.
• Branch and Bound: Finds an optimal solution to an optimization problem.

Pruning

• Backtracking: Prunes a node when the partial solution violates a constraint or cannot be extended to a valid solution.
• Branch and Bound: Prunes a node when it is infeasible or when its objective bound cannot improve the incumbent solution.

Search order

• Backtracking: Usually uses depth-first search and recursion.
• Branch and Bound: May use FIFO, LIFO, or best-first search with a priority queue.

Use of objective values

• Backtracking: An objective function is not essential.
• Branch and Bound: Requires an objective value, an incumbent solution, and lower or upper bounds.

Typical applications

• Backtracking: n-Queens, Hamiltonian Circuit, Subset-Sum, graph coloring.
• Branch and Bound: Assignment, 0/1 Knapsack, TSP, scheduling.

Similarity

Both methods avoid complete enumeration by pruning subtrees and both may still require exponential time in the worst case.

In metric TSP, travel costs satisfy:

• Nonnegativity: .
• Symmetry: .
• Triangle inequality:

MST-based 2-approximation

1. Compute a minimum spanning tree .
2. Double every edge of to obtain an Eulerian multigraph.
3. Find an Euler tour.
4. Shortcut repeated vertices to obtain a Hamiltonian tour.

Since deleting an edge from an optimal TSP tour gives a spanning tree,

Doubling the tree gives cost . Shortcutting does not increase cost because of the triangle inequality. Therefore, the final tour has cost at most .

A stronger algorithm, Christofides' algorithm, gives a approximation for symmetric metric TSP.

General TSP

If arbitrary edge costs are allowed and the triangle inequality is absent, shortcutting can drastically increase the cost. Unless , general TSP has no polynomial-time approximation algorithm with any fixed constant approximation ratio.

Thus, structural assumptions such as the triangle inequality are essential for useful TSP approximation guarantees.

A bound estimates the best objective value obtainable from a partial solution. Its quality directly determines the amount of pruning performed by Branch and Bound.

Properties of a useful bound

• Validity: It must never incorrectly eliminate an optimal solution.
• Tightness: It should be close to the best completion value.
• Efficiency: It should be inexpensive to compute.

A tighter bound usually prunes more nodes, but if it is too expensive, the overall algorithm may become slower.

Assignment Problem

For a minimization problem, use a lower bound consisting of:

• The cost of fixed assignments.
• The minimum possible costs for unassigned workers.

Matrix row and column reduction gives a stronger lower bound than simply taking independent row minima.

0/1 Knapsack

For this maximization problem, solve the remaining problem fractionally. The fractional-knapsack profit is an upper bound because allowing fractions can only improve the result compared with the 0/1 restriction.

Traveling Salesman Problem

A lower bound may be obtained from:

• Row and column reduction of the cost matrix.
• A minimum spanning tree on unvisited cities plus connection costs.
• Minimum required incident-edge costs.

Trade-off

A weak bound is fast but may cause a large search tree. A strong bound reduces the tree but costs more per node. Effective implementations balance these two factors.