CSE 373 Autumn 2024�Fun With Reductions!

Reductions

2

Shows how two different problems relate to each other

​

​

​

​

​

MOVIE TIME!

MacGyver’s Reduction

3

Input: Closed Door

Problem we don’t know how to solve

Lighting a fire

Problem we do know how to solve

Aim duct at door, insert keg

Opening a door

Output: Open Door

Combining all three arrows gives an algorithm for opening a door

Seam Finding Reduces to Shortest Path

4

Problem we don’t know how to solve

Finding a Seam

Problem we do know how to solve

Single-Source Shortest Path

Dijkstra’s Algorithm

Pixels to nodes, edges to neighbors, weight is energy, add source and sink

Reduction

Input: Graph

Input: Image

Output: Single-source Shortest Path Tree

Find shortest path from source to sink

Output: A Seam

Patch Finding Reduces to Cycle Detection

5

Problem we don’t know how to solve

Finding a Patch

Problem we do know how to solve

Cycle Detection

DFS

Solution to Exam 3

Reduction

Input: Graph

Input: Image

Output: All Cycles

Solution to Exam 3

Output: All Patches

Detect Melanoma (Group Analysis 3)

6

Problem we don’t know how to solve

Detect Melanoma

Problem we do know how to solve

Finding a Patch

Identify high-energy

and low-energy pixels

Reduction

Photo of a patient’s skin

1

Input: Image

Output: All Patches

Patches are melanoma?

Detect Melanoma (Group Analysis 3)

7

Detect Melanoma

Find Patches

​

​

Reduction

DFS

Reduction

Cycle Detection

All Cycles

Photo of a patient’s skin

1

Reductions Enable New Algorithms!

• Create an algorithm for a new problem by using one you already know!
• More algorithms = More opportunities!
• The problem you reduced to could itself be solved using a reduction!

​

Sorting “Reduces To” Priority Queue ADT

9

Problem we don’t know how to solve

Sorting a List

Problem we do know how to solve

Priority Queue ADT

Add/RemoveMax Algorithms

Add all items

Reduction

Input: A List

removeMax until empty, move value to the end of the list

Output: A Sorted List

Binary Max Heap

We named this entire path “Heap Sort”

Exam 2 Impossible Data Structure

Another use of Reductions

11

Reduction

An algorithm for A

Suppose I knew a worst-case lower bound for Problem A

This path’s running time must be at least that lower bound

Fast running time

Fast running time

Slow Running time

Unknown Running time

Two Ways to use Reductions

Suppose we have a “fast” reduction from A to B

​

​

1. A “fast” algorithm for B gives a fast algorithm for A

​

​

• If we have a worst-case lower bound for A, we also have one for B

fast

fast

If B is fast

Then A is fast

If A is slow

Then B is slow

fast

Pairing Problem

Sorting Reduces to Pairing

14

Problem with a known lower bound

Sorting a List

Problem without a known lower bound

Pairing

Create the list:

​

Reduction

Input: Two Lists

Output: A Pairing

Add the item paired with 0, then 1, then 2, …

Input: A List

Output: A Sorted List

Sorting Reduces to Pairing

15

Problem with a known lower bound

Sorting a List

Problem without a known lower bound

Pairing

Create the list:

​

Reduction

Input: Two Lists

Output: A Pairing

Add the item paired with 0, then 1, then 2, …

Input: A List

Output: A Sorted List

A “Hard” Problem: Finding Duplicates

False

True

Finding Duplicates Reduces to Sorting

17

Sorting

​

​

Reduction

Input: A List

Check if the any adjacent items are equal

Input: A List

Output: A Sorted List

Merge Sort

Find Duplicates

Output: True/False

This gives us no information about a lower bound for Find Duplicates!

A “Hard” Problem: Finding Duplicates

False

True

Closest Pair of Points

19

1

2

3

4

5

6

7

8

Given:

A list of points

​

Return:

Pair of points with smallest distance apart

Reducing Find Duplicates to CPP

6,6

Running time?

How to we find the answer to Element Uniqueness from Closest Pair?

Check if closest pair’s distance is 0

Running time?

Reductions for Lower-Bound on CPP

21

True/False

Reduction

Closest Pair

of Points

Find Duplicates

Is closest distance > 0?

Two Ways to use Reductions

Suppose we have a “fast” reduction from A to B

​

​

1. A “fast” algorithm for B gives a fast algorithm for A

​

​

• If we have a worst-case lower bound for A, we also have one for B

fast

fast

If B is fast

Then A is fast

If A is slow

Then B is slow

fast

Party Problem

23

Draw Edges between people who don’t get along

How many people can I invite to a party if everyone must get along?

Independent Set

24

Example

25

Independent set of size 6

Generalized Baseball

26

Generalized Baseball

27

Need to place defenders on bases such that every edge is defended

How many defenders would suffice?

Vertex Cover

28

Example

29

Vertex cover of size 5

Relating Independent Set to Vertex Cover

30

Independent Set

Vertex Cover

Relating Vertex Cover to Independent Set

31

Independent Set

Vertex Cover

Independent Set Reduces to Vertex Cover

32

Independent Set

Vertex Cover

Solution for Vertex Cover

Solution for Independent Set

Reduction

Any Algorithm for Vertex Cover

Take the opposite

set of nodes

Input: A graph and a number

Independent Set Reduces to Vertex Cover

33

Vertex Cover

Independent Set

Solution for Independent Set

Solution for Vertex Cover

Reduction

Any Algorithm for Independent Set

Take the opposite

set of nodes

Input: A graph and a number

Solving Vertex Cover and Independent Set

Either both problems have a fast algorithm or neither does!