Data Structures

Reductions

In the previous article, we learned about the relationship between Complexity Classes in DAA, In this article, we will learn about the reductions (complexity).

Harshit Brijwasi

Dec 15, 2022

408

Before discussing reductions, let us consider the following scenario. Assume that we want to solve problem X but feel it’s very complicated. In this case, what do we do? The first thing that comes to mind is, if we have a similar problem to that of X (let us say Y), then we try to map X to Y and use Y’s solution to solve X also. This process is called reduction.

process of reduction

In order to map problem X to problem Y, we need some algorithm and that may take the linear time or more. Based on this discussion the cost of solving problem X can be given as: Cost of solving X = Cost of solving Y + Reduction time Now, let us consider the other scenario.

For solving problem X, sometimes we may need to use Y’s algorithm (solution) multiple times. In that case, the Cost of solving X = Number of Times * Cost of solving X + Reduction time The main thing in NP-Complete is reducibility. That means, we reduce (or transform) given NP-complete problems to other known NP-Complete problems. Since the NP-Complete problems are hard to solve and in order to prove that a given NP-Complete problem is hard, we take one existing hard problem (which we can prove is hard) and try to map the given problem to that and finally we prove that the given problem is hard.

Note: It’s not compulsory to reduce the given problem to a known hard problem to prove its hardness. Sometimes, we reduce the known hard problem to a given problem.

Important NP-Complete Problems (Reductions) –

Satisfiability Problem:

A boolean formula is in conjunctive normal form (CNF) if it is a conjunction (AND) of several clauses, each of which is the disjunction (OR) of several literals, each of which is either a variable or its negation. For example (a ∨ b ∨ c ∨ d ∨ e)∧(b ∨ ~c ∨ ~d) ∧ (~a ∨ c ∨ d) ∨ (a ∨ ~b) A 3-CNF formula is a CNF formula with exactly three literals per clause. The previous example is not a 3-CNF formula, since its first clause has five literals and its last clause has only two.

2-SAT Problem: 3-SAT is just SAT restricted to 3-CNF formulas: Given a 3-CNF formula, is there an assignment to the variables so that the formula evaluates to TRUE? 2-SAT Problem: 2-SAT is just SAT restricted to 2-CNF formulas: Given a 2-CNF formula, is there an assignment to the variables so that the formula evaluates to TRUE?

Circuit-Satisfiability Problem:

Given a boolean combinational circuit composed of AND, OR and NOT gates, is it satisfiable?. That means, given a boolean circuit consisting of AND, OR and NOT gates properly connected by wires, the Circuit-SAT problem is to decide whether there exists an input assignment for which the output is TRUE.

Hamiltonian Path Problem (Ham-Path):

Given an undirected graph, is there a path that visits every vertex exactly once?

Hamiltonian Cycle Problem (Ham-Cycle):

Given an undirected graph, is there a cycle (where start and end vertices are same) that visits every vertex exactly once?

Directed Hamiltonian Cycle Problem (Dir-Ham-Cycle):

Given a directed graph, is there a cycle (where start and end vertices are same) that visits every vertex exactly once?

Travelling Salesman Problem (TSP):

Given a list of cities and their pair-wise distances, the problem is to find the shortest possible tour that visits each city exactly once.

Shortest Path Problem (Shortest-Path):

Given a directed graph and two vertices s and t, check whether there is a shortest simple path from s to t.

Graph Coloring:

A k-coloring of a graph is to map one of k ‘colors’ to each vertex, so that every edge has two different colors at its endpoints. The graph coloring problem is to find the smallest possible number of colors in a legal coloring.

3-Color problem:

Given a graph, is it possible to color the graph with 3 colors in such a way that every edge has two different colors?

Clique (also called complete graph):

Given a graph, the CLIQUE problem is to compute the number of nodes in its largest complete subgraph. That means, we need to find the maximum subgraph which is also a complete graph.

Independent Set Problem (Ind_Set):

Let G be an arbitrary graph. An independent set in G is a subset of the vertices of G with no edges between them. The maximum independent set problem is the size of the largest independent set in a given graph.

Vertex Cover Problem (Vertex-Cover):

A vertex cover of a graph is a set of vertices that touches every edge in the graph. The vertex cover problem is to find the smallest vertex cover in a given graph.