Reduction Algorithm

A reduction algorithm transforms a complex problem into a simpler problem. By reducing to a solved problem, it enables reuse of existing solutions.

Some examples:

Sorting by reduction to min/max problem
Shortest paths via reduction to min weight edge problem
NP-completeness reductions between problems

Java - Reduce sorting to min/max:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
int[] minSort(int[] arr) {
  if (arr.length <= 1) return arr;
  
  // Find min 
  int minIndex = findMinIndex(arr);

  // Move to first position
  swap(arr, 0, minIndex);

  // Recursively sort rest
  int[] sortedRest = minSort(Arrays.copyOfRange(arr, 1, arr.length));

  // Combine
  int[] result = new int[arr.length];
  result[0] = arr[0];
  System.arraycopy(sortedRest, 0, result, 1, sortedRest.length);

  return result;
}

C++ - Shortest paths via minimum edge:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int dijkstra(Graph graph, int src) {

  // Min heap
  priority_queue<Edge> pq; 
  
  // Initialize

  while (!pq.empty()) {
    Edge e = pq.top(); // Next min weight edge 
    // Process edge
  }
}

Python - 3-SAT to Vertex Cover:

1
2
3
4
5
6
7
8
from vertex_cover import minVertexCover

def reduce3SATtoVC(formula):
  # Construct graph 
  # Vertices = clauses + literals
  # Edges based on relationship

  return minVertexCover(graph) # Returns min # clauses unsatisfied

Reduction allows reusing existing solutions by transforming problems into simpler forms.

Reduction is a technique used to solve one problem by transforming it into another problem, which is already known to be solvable. It’s like saying, “If we can solve problem B and we can reduce problem A to problem B, then we can solve problem A.” This is a cornerstone in computational theory, often employed to prove that specific problems are hard to solve.

Example Code in Java

Let’s consider the problem of finding the greatest common divisor (GCD) to reduce the problem of finding the least common multiple (LCM).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class ReductionExample {
    public static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    public static void main(String[] args) {
        int a = 12, b = 18;
        System.out.println("LCM of " + a + " and " + b + " is: " + lcm(a, b));
    }
}

Example Code in C++

The C++ version uses the same logic for GCD and LCM.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}

int main() {
    int a = 12, b = 18;
    cout << "LCM of " << a << " and " << b << " is: " << lcm(a, b) << endl;
    return 0;
}

Example Code in Python

In Python, we follow the same reduction logic to find the LCM using the GCD.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return (a * b) // gcd(a, b)

a = 12
b = 18
print(f"LCM of {a} and {b} is: {lcm(a, b)}")

Here, we’ve reduced the problem of finding the LCM to the problem of finding the GCD. This is a classic example of algorithmic reduction.