Approximation Algorithm for Vertex Cover

Definition

A vertex cover of an undirected graph G = (V, E) is a subset V' ⊆ V such that for every edge (u, v) ∈ E, at least one of u or v belongs to V'.

The optimization problem is to find the vertex cover with the fewest vertices. The approximation problem is to find a vertex cover with few vertices (not necessarily minimum, but within a guaranteed bound).

Approximation Algorithm (APPROX-VERTEX-COVER)

APPROX-VERTEX-COVER(G):
1. C = {}  (empty set - will hold the vertex cover)
2. E' = E[G]  (copy of all edges)
3. while E' is not empty:
      a. Pick any edge (u, v) from E'
      b. Add both u and v to C
         C = C ∪ {u, v}
      c. Remove from E' every edge incident to u or v
4. return C

Key Properties

• Time Complexity: O(V + E)
• Approximation Ratio: This algorithm is a 2-approximation, meaning:

|C| ≤ 2 × |C*|

where C* is the optimal (minimum) vertex cover.

Reason: Each edge picked in step 3(a) belongs to an optimal cover (at least one endpoint must be in C*). Since both endpoints are added, we add at most twice the optimal number of vertices.

Example

Consider the following graph:

Vertices: {1, 2, 3, 4, 5, 6, 7}
Edges: {(1,2), (1,3), (2,4), (3,4), (4,5), (4,6), (5,7)}

Step-by-step execution:

Result: C = {1, 2, 3, 4, 5, 7} → size = 6

Optimal cover: C* = {1, 4, 5} or {2, 3, 4, 7} → size = 3 or 4

Here |C| = 6 ≤ 2 × 3 = 6, which satisfies the 2-approximation guarantee.

Conclusion

The approximation algorithm for vertex cover guarantees a solution no worse than twice the optimal. It is efficient and practical because finding the exact minimum vertex cover is NP-hard, while this approximation runs in polynomial time O(V + E).

Selection Sort: Algorithm and Complexity Analysis

Definition

Selection Sort is a simple comparison-based sorting algorithm that works by repeatedly selecting the minimum element from the unsorted portion of the array and placing it at the correct position.

Algorithm (Steps)

1. Start.
2. Let array A have n elements (index 0 to n-1).
3. For each position i from 0 to n-2:
   • Assume the current position i holds the minimum element (set min_index = i).
   • Scan the remaining unsorted portion (j from i+1 to n-1).
   • If A[j] < A[min_index], update min_index = j.
   • After scanning, swap A[i] with A[min_index].
4. Repeat step 3 until the array is fully sorted.
5. Stop.

Pseudocode

SelectionSort(A, n)
  for i = 0 to n-2
    min_index = i
    for j = i+1 to n-1
      if A[j] < A[min_index]
        min_index = j
    swap(A[i], A[min_index])

Example Trace

Sort: A = {64, 25, 12, 22, 11}

Time Complexity Analysis

Using the RAM model (each comparison and memory reference counts as 1 step):

• The outer loop runs (n - 1) times.
• For each pass i, the inner loop runs (n - 1 - i) times.
• Total comparisons:

$$T(n) = (n-1) + (n-2) + (n-3) + \ldots + 1 = \frac{n(n-1)}{2}$$

Unlike Bubble Sort (which has O(n) best case), Selection Sort always performs O(n²) comparisons because it must scan the entire unsorted portion to find the minimum, even if the array is already sorted.

Space Complexity Analysis

• Selection Sort sorts the array in-place.
• Only a constant number of extra variables are used: i, j, min_index, and a temporary swap variable.
• The array A itself takes n memory references, but no additional array is needed.

$$\text{Space Complexity} = O(1)$$

This is consistent with the approach used in Bubble Sort (O(1) extra space) as noted in the course notes, since both are in-place sorting algorithms.

Summary Table