The Hardness of Problems and Polynomial Time Reductions

CSE 421 Winter 2025 Lecture 22: Reductions Nathan Brunelle http://www.cs.uw.edu/421

Q: Does every problem have a polynomial time algorithm? A: NO. The Halting problem is undecidable so it doesn t have an algorithm at all [Turing] Q: If there is an algorithm for a problem is there is always one that runs in polynomial time? A: NO. There are problems that require exponential time to solve. (See CSE 431) Q: What about some of the problems we ve seen so far? 2

How do we know that a problem is hard? At this point in the quarter, you ve probably at least once been banging your head against a problem for so long that you began to think there s no way there s actually an efficient algorithm for this problem. That wasn t true for any of the problems we have assigned you to solve (so far). But we think that it is true for certain types of problems, including one where you showed how some algorithms failed to work. Over the next week we will look at how you can figure out that some problem you encounter is just as hard as those. 3

Some definitions Defn: A problemis a set of inputs and their associated correct outputs. Find a Minimum Spanning Tree is a problem. Input is a graph, output is the MST. Tell whether a graph is bipartite is a problem. Input is a graph, output is yes or no Find the maximum subarray sum is a problem. Input is an array, output is the number that represents the largest sum of a subarray. 4

Some definitions Defn: An instanceis a single input to a problem. A single, particular graph is an instance of the MST problem A single, particular graph is an instance of the bipartiteness-checking problem. A single, particular array is an instance of the maximum subarray sum problem. 5

Relative Hardness of Problems Want to comparethe hardness of problems Want to be able to say Problem B is solvable in polynomial time problem Ais solvable in polynomial time Problem B is at least as hard as problem A 6

Polynomial Time Reduction Defn: We write ? ?? iff there is an algorithm for ?using a black box (subroutine or method) that solves ? that uses only a polynomial number of steps, and makes only a polynomial number of calls to a method for ?. Theorem: If ? ?? then a poly time algorithm for ? poly time algorithm for ? Proof: Not only is the number of calls polynomial but the size of the inputs on which the calls are made is polynomial! Corollary: If you can prove there is no fast algorithm for ?, then that proves there is no fast algorithm for ?. Intuitionfor ? ?? : ? is at least as hard* as ? *up to polynomial-time slop. 7

Now the weird part We read ? ?? as ? is polynomial-time reducible to ? or ? can be reduced to ? in polynomial time It means we can solve ? using at most a polynomial amount of work on top of solving ?. But word reducible seems to go in the opposite direction of the sign. The general motivation for the terminology is: To solve ? we can reduce our attention from all possible things just to solving ?. Often we have easy problem ? harder problem. (e.g. bipartite matching ? flow) Sometimes we can show general case ? special case (e.g. stable matching) In this case we really use the extra polytime work we re allowed. 8

Some Previous Examples On Homework 1, you reduced stable matchings with different numbers of applicants and jobs with only some unacceptable to [standard] stable matching . On Homework 2, you (might have) reduced labelling bear photographs to 2-coloring . We reduced Bipartite Matching to Network Flow . 9

Getting the wording right Lots of people mess this up! Tl;dr check the direction you re going every time. It s going to take a while to be intuitive. 10

Reductions Shows how two different problems relate to each other 11

MacGyvers Reduction Problem we do know how to solve Problem we don t know how to solve Opening a door Lighting a fire Aim duct at door, insert keg ? ? How? Solution for ? Solution for ? Keg cannon battering ram Alcohol, wood, matches Put fire under the Keg Reduction 12

Using the word reduction Problem ?: open a door Problem ?: light a fire MacGyver reduced ? to ? Meaning he used a solution to ? to produce a solution for ? Which statements are correct? 1. ? ? 2. ? ? 3. ?is easier than ? 4. ?is easier than ?

Using the word reduction Problem ?: open a door Problem ?: light a fire MacGyver reduced ? to ? Meaning he used a solution to ? to produce a solution for ? Which statements are correct? 1. 1. ? ? 2. ? ? 3. 3. ?is easier than ? 4. ? is easier than ?

Polynomial Time Reductions ?(??) Problem ? Problem ? ? ? Procedure for converting instances of ? into instances of ? Algorithm for solving ? Procedure for converting solutions of B into solutions of ? Solution for ? Solution for ? ? ? Reduction 15

Decision Problems Defn: A decision problem is a problem that has a YES or NO answer. A correct algorithm has a Boolean return type Example: Is this polytope empty? Problems can be rephrased in terms of very similar decision problems. Instead of Find the shortest path from ? to ? ask Is there a path from ? to ? of length at most ?? Can do binary search to find exact value. If a problem is easy then all of its individual output bits must be easy If a problem is hard then at least one of its output bits must be hard. 16

Polynomial Time Reductions (Decision Problems) ?(??) Decision Problem ? Decision Problem ? ? ? Procedure for converting instances of ? into instances of ? Algorithm for solving ? Use the same answer Solution for ? Solution for ? Yes/No Yes/No Reduction 17

A Special Kind of Polynomial-Time Reduction We will often use a restricted form of ? ?? often called a Karp or many-one reduction... ??iff there is an algorithm for ?given a black box solving ? that on input ? that Runs for polynomial time computing ? = ?(?) Makes ? call to the black box for ?on input ? Returns the answer that the black box gave We say that the function ? is the reduction. Defn: ? ? 18

Lets do a reduction 4 steps for reducing (decision problem) ? to problem ? 1. Describe the reduction itself i.e., the function that converts the input for ? to the one for problem ?. i.e., describe what the top arrow in the pink box does 2. Make sure the running time would be polynomial In lecture, we ll sometimes skip writing out this step. Argue that if the correct answer (to the instance for ?) is YES, then the input we produced is a YES instance for ?. 3. Argue that if the correct answer (to the instance for ?) is NO, then the input we produced is a NO instance for ?. 4. 19

Lets do a reduction 4 steps for reducing (decision problem) ? to problem ? 1. Describe the reduction itself i.e., the function that converts the input for ? to the one for problem ?. i.e., describe what the top arrow in the pink box does 2. Make sure the running time would be polynomial In lecture, we ll sometimes skip writing out this step. Argue that if the correct answer (to the instance for ?) is YES, then the input we produced is a YES instance for ?. 3. Argue that if the input we produced is a YES instance for ? then the correct answer (to the instance for ?) is YES. 4. Contrapositive 20

Reduce 2Color to 3Color Defn: A undirected graph ? = (?,?) is ?-colorable iff we can assign one of ? colors to each vertex of ? s.t. for (?,?) ?, their colors, ?(?) and ?(?), are different. edges are not monochromatic 2Color: Given: an undirected graph ? Is ? 2-colorable? 3Color: Given: an undirected graph ? Is ? 3-colorable? 21

Reduce 2Color to 3Color Defn: A undirected graph ? = (?,?) is ?-colorable iff we can assign one of ? colors to each vertex of ? s.t. for (?,?) ?, their colors, ?(?) and ?(?), are different. edges are not monochromatic 2Color: Given: an undirected graph ? Is ? 2-colorable? No Yes 3Color: Given: an undirected graph ? Is ? 3-colorable? Yes No 22

2Color ? 3Color Given a graph ? figure out whether it can be 2-colored, by using an algorithm that figures out whether it can be 3-colored. Usual outline: Transform ? into an input for the 3Color algorithm Run the 3Color algorithm Use the answer from the 3Color algorithm as the answer for ? for 2Color 23

Reducing 2Color 2Color to 3Color 3Color ?(??) 3Color 2Color ? ? Transform given graph ? such that the output graph ? was 3-colorable if and only if ? was 2-colorable Algorithm for solving 3Color Use the same answer Solution for 2Color Solution for 3Color Yes/No Yes/No Reduction 24

Reduction If we just ask the 3Color algorithm about ?, if ? is 3-colorable but not 2- colorable it will give the wrong answer because it has the 3rd color available. Idea: Add extra vertices and edges to to G to force the 3rd color to be used there but not on ? Reduction ?: Add one extra vertex ? and attach it to everything in ?. Write ? = ?(?). (? is polynomial time computable.) 25

Reducing 2Color 2Color to 3Color 3Color ?(??) 3Color 2Color ? ? Add a new node to ?, connect every node to it Algorithm for solving 3Color Use the same answer Solution for 2Color Solution for 3Color Yes/No Yes/No Reduction 26

Lets do a reduction 4 steps for reducing (decision problem) ? to problem ? 1. Describe the reduction itself i.e., the function that converts the input for ? to the one for problem ?. 2. Make sure the running time would be polynomial In lecture, we ll sometimes skip writing out this step. Argue that if the correct answer (to the instance for ?) is YES, then the input we produced is a YES instance for ?. 3. Argue that if the input we produced is a YES instance for ? then the correct answer (to the instance for ?) is YES. 4. 27

Correctness Two statements to prove (two directions): If ? is a YES for 2Color (? is 2-colorable) then ? is a YES for 3Color (? is 3-colorable) Suppose ? is 2-colorable: ? has a 2-coloring ? so edges of ? have different colored endpoints. We get a 3-coloring of ? by using ? for all the copies of original vertices of ? and a 3rd color for the extra vertex ?: Original edges of ? in ? have different colored endpoints; the extra edges too. So ? is 3-colorable. If ? is a YES for 3Color (? is 3-colorable) then ? is a YES for 2Color on (? is 2-colorable) Suppose ? is 3-colorable: Consider a 3-coloring ? of ?. Consider the extra vertex ? in ? that was added to ?. For every vertex ? of ?, we have an edge (?,?) so ? ? ? (?). This means that every vertex ? of ? is colored with one of the two colors other than ? (?). So we can use ? as a 2-coloring of ? since all those edges had different colored endpoints in ?. So ? is 2-colorable. 28

Write two separate arguments The two directions we covered actually prove an if and only if. To make sure you handle both directions, I strongly recommend: Always do two separate proofs! (Don t try to prove both directions at once, don t refer back to the prior proof and say for the same reason . There are usually subtle differences.) Don t use contradiction! (It s easy to start from the wrong spot and accidentally prove the same direction twice without realizing it.) 29

Another proof of 2Color ? 3Color We had an ?(? + ?) time algorithm for 2Color based on BFS. Simply solve the 2Color problem without making any calls to a 3Color method! 30

Reducing 2Color 2Color to 3Color 3Color ?(??) 3Color 2Color ? ? Check if graph is bipartite, if so then select a pre-chosen 3- colorable graph. If not then select a pre-chosen non-3- colorable graph Algorithm for solving 3Color Use the same answer Solution for 2Color Solution for 3Color Yes/No Yes/No Reduction 31

Two Simple Reductions Independent-Set: Given a graph ? = (?,?) and an integer ? Is there a ? ? with ? ?such that no two vertices in ? are joined by an edge? (? is called an independent set.) Clique: Given a graph ? = (?,?) and an integer ? Is there a ? ? with ? ?such that every pair of vertices in ? is joined by an edge? (? is called a clique.) Claim:Independent-Set ? Clique 32

Examples Independent Set ? = 3 ? = 2 Clique ? = 4 ? = 3

Examples Independent Set ? = 3 ? = 2 Yes No Clique ? = 4 ? = 3 Yes No

Reducing Independent Set Independent Set to Clique Clique ?(??) Clique Independent Set ? ? ? , ? ? = 2 ? = 3 Transform given graph ? and number ? into ? and ? such that ? has an Independent Set of size ? iff ? has a Clique of size ? Algorithm for solving Clique Solution for Independent Set Use the same answer Solution for Clique Yes/No Yes/No Reduction 35

Set ? Clique Independent Independent- -Set Given: (?,?) as input to Independent-Set where ? = (?,?) Clique Use function ? that transforms (?,?) to (? ,?) where ? = (?,? ) has the same vertices as ? but ? consists of precisely those edges on ? that are not edges of ?. graph complement From the definitions,? is an independent set in ? ? is a clique in ? 36

Reducing Independent Set Independent Set to Clique Clique ?(??) Clique Independent Set ? ? ? ? ? = 2 ? = 3 ? = 2 ? = 3 Set ? to be the complement graph of ?. Set ? = ? Algorithm for solving Clique Solution for Independent Set Use the same answer Solution for Clique Yes/No Yes/No Reduction 37

Clique Clique ? Independent Set Independent Set Given: (?,?) as input to Clique where ? = (?,?) Use function ? that transforms (?,?) to (? ,?) where ? = (?,? ) has the same vertices as ? but ? consists of precisely those edges on ? that are not edges of ?. From the definitions,? is an clique in ? ? is an independent set in ? 38

Reducing Clique Clique to Independent Set Independent Set ?(??) Independent Set Clique ? ? ? ? ? = 2 ? = 3 ? = 2 ? = 3 Set ? to be the complement graph of ?. Set ? = ? Algorithm for solving Independent Set Use the same answer Solution for Clique Solution for Independent Set Yes/No Yes/No Reduction 39

Another Reduction Vertex-Cover: Given a graph ? = (?,?) and an integer ? Is there a ? ? with ? ?such that every edge of ? has an endpoint in ?? (? is a vertex cover, a set of vertices that covers ?.) Claim: Independent-Set ? Vertex-Cover Lemma: In a graph ? = (?,?) and ? ? ? is an independent set ? ? is a vertex cover 40

Examples Independent Set ? = 3 ? = 2 Yes No Vertex Cover ? = 2 ? = 3 Yes No

Reducing Independent Set Independent Set to Vertex Cover Vertex Cover ?(??) Vertex Cover Independent Set ? ? ? ? ? = 3 ? = 2 ? = 2 ? = 3 Set ? = ?. Set ? = ? ? Algorithm for solving Vertex Cover Solution for Independent Set Use the same answer Solution for Vertex Cover Yes/No Yes/No Reduction 42

Reducing Vertex Cover Vertex Cover to Independent Set Independent Set ?(??) Independent Set Vertex Cover ? ? ? ? ? = 2 ? = 3 ? = 3 ? =2 Set ? = ?. Set ? = ? ? Algorithm for solving Independent Set Solution for Vertex Cover Use the same answer Solution for Independent Set Yes/No Yes/No Reduction 43

Reduction Idea Lemma: In a graph ? = (?,?) and ? ? ? is an independent set ? ? is a vertex cover Proof: ( ) Let ? be an independent set in ? Then for every edge ? ?, ? contains at most one endpoint of ? So, at least one endpoint of ? must be in ? ? So, ? ? is a vertex cover ( ) Let ? = ? ? be a vertex cover of ? Then ? does not contain both endpoints of any edge (else ? would miss that edge) So? is an independent set ? ? ? 44

Reduction for Clique Clique ? Vertex Vertex- -Cover Cover Clique: Given a graph ? = (?,?) and an integer ? Is there a ? ? with ? ?such that every pair of vertices in ? is joined by an edge? (? is called a clique.) Vertex-Cover: Given a graph ? = (?,?) and an integer ? Is there a ? ? with ? ?such that every edge of ? has an endpoint in ?? (? is a vertex cover, a set of vertices that covers ?.) Claim: Clique ? Vertex-Cover Idea: Use Clique ? Independent-Set and Independent-Set ? Vertex-Cover 45

Reducing Clique Clique to Vertex Cover Vertex Cover ?(??) ?(??) Independent Set ? Vertex Cover ? Clique ? ? = 3 ? = 2 ? = 2 Set ? = ? . Set ? = ? ? Set ? to be the complement graph of ?. Set ? = ? ? ? ? ? = 2 ? = 3 ? = 3 Algorithm for solving Independent Set Algorithm for solving Vertex Cover Use the same answer Use the same answer Solution for Independent Set Solution for Vertex Cover Solution for Clique Yes/No Yes/No Yes/No Reduction Reduction 46

Reducing Clique Clique to Vertex Cover Vertex Cover ?(??) Vertex Cover Clique ? ? ? ? ? = 2 ? = 3 ? = 3 ? = 2 Set ? to be the complement graph of ?. Set ? = ? ? Algorithm for solving Vertex Cover Use the same answer Solution for Clique Solution for Vertex Cover Yes/No Yes/No Reduction 47