Understanding NP-Hard Problems and Reductions

Lecture 24 Classical NP-hard Problems

Outline Hamiltonian Path to TSP Cycle 3-SAT to Quadratic Program Tripartite Matching to SUBSET SUM

General Recipe for reductions In order to prove B is NP-hard, given that we know A is NP hard. Reduce A to B. What is a complete reduction? 1. Given an instance X of A, construct an instance Y of B. 2. 3. Prove that if answer to X is YES, answer to Y is also YES. Prove that if answer to X is NO, answer to Y is also NO. (Usually: prove the contrapositive: if answer to Y is YES, answer to X is also YES)

Hamiltonian Path Given a graph G, a starting vertex s and an ending vertex t. A Hamiltonian path from s to t is a path from s to t that visits every vertex in G exactly once. Hamiltonian Path problem asks if there exists a Hamiltonian path from s to t.

Travelling Salesman Problem Given a weighted graph G, a salesman wants to start at vertex s, visit all vertices in the graph, and then come back to s. Given a threshold L, TSP cycle problem asks whether there is a way to visit all vertices (and come back to s) with total edge length at most L. (Starting vertex does not matter, so s is not part of input)

Reduction from Hamiltonian Path to TSP cycle Step 1: Given an instance X of Hamiltonian Path, construct an instance Y of TSP cycle. Idea: Find similarities/differences of the problems. Similarities: visit every vertex in graph. Differences: 1. No weights in Hamiltonian Path 2. Path vs. cycle.

Outline Hamiltonian Path to TSP Cycle 3-SAT to Quadratic Program Tripartite Matching to SUBSET SUM

3-SAT Literals: A variable (?1), or the negation of a variable (?1). Clause: Logic OR of literals (?1 ?3 ?5) Conjunctive Normal Form: and of or s. ?1 ?3 ?5 ?2 ?3 ?4 ?1 ?4 ?5 3-SAT: Given a conjunctive normal form, where each clause contains at most 3 literals, decide whether there is a value of variables such that the formula is satisfied (A clause is satisfied if one of its literals is true; The formula is satisfied if ALL clauses are satisfied.)

Quadratic Programming Same as linear programming, except you are allowed to have quadratic constraints (e.g. x12+x2x3+ 3x4 3) Decision problem: Given a set of quadratic constraints, decide whether there is a feasible solution.

Reduction from 3-SAT to Quadratic Programming Step 1: Given an instance X of 3-SAT, construct an instance Y of Quadratic Programming. Two problems are very different, needs to use gadgets.

Gadget for variables Variable xi: either true or false Gadget: A variable in quadratic program that can only take two values (say 0 or 1) yi2= yi xi= true yi= 1; xi= false yi= 0 Negation of a variable: (1-yi)

Gadget for Clauses Clause: (?1 ?3 ?5) Interpretation: x1= true or x3= true or x5= false y1= 1 or y3= 1 or (1-y5) = 1 Can we write this as a constraint? y1+y3+(1-y5) 1

Outline Hamiltonian Path to TSP Cycle 3-SAT to Quadratic Program Tripartite Matching to SUBSET SUM

Tripartite Matching There are three sets of vertices U, V, W, each of size n. A hyper-edge is a 3-tuple (u,v,w) where u, v, w are vertices in U, V, W respectively. A tripartite matching is a way of selecting n hyper- edges, so that every vertex is adjacent to a hyper- edge. The decision version of the problem asks whether a tripartite matching exists.

SUBSET SUM/KNAPSACK In the SUBSET SUM problem, you are given n numbers a1, a2, , an, and a target m. The answer is YES if and only if there is a subset of these n numbers that sums up to m.

Reduction from Tripartite Matching to SUBSET SUM Step 1: Given an instance X of Tripartite Matching, construct an instance Y of SUBSET SUM. Similarity: Tripartite Matching wants to select hyper-edges, SUBSET SUM wants to select numbers. Question: how to map a hyper-edge to a number?

Idea: Use an intermediate problem SUBSET VECTORS Given n vectors v1, v2, , vn, and a target u. The answer is YES if and only if there is a subset of these n vectors that sums up to u. Reduce Tripartite Matching to SUBSET VECTORS Reduce SUBSET VECTORS to SUBSET SUM