1 of 13

Reductions and Decomposition

Solving problems by reducing them to other problems.

1

Kevin Lin, with thanks to many others.

2 of 13

DAG Shortest Paths

Given a weighted DAG (possibly negative edge weights), find the single-source shortest paths tree from s to every other vertex in the graph.

Your algorithm should be faster than Dijkstra’s algorithm.

2

B

C

A

s

1

5

D

-4

2

4

0

1

2

4

Q

3 of 13

DAG Shortest Paths

  • Our algorithm should explore A ⇒ C ⇒ B
  • Dijkstra’s explores A ⇒ B

Topological ordering.

  • We want to put C before B.
  • Final result: A, C, B, D.
  • Once we reach a node, only process it once�we’ve seen all of its incoming edges.

Topological ordering algorithm:

  • DFS postorder: D, B, C, A.
  • Reverse of that: A, C, B, D.

3

B

C

A

s

1

5

D

-4

2

4

0

1

2

4

A

4 of 13

Positive Integer-Weighted Shortest Paths

Given a weighted, directed graph (possibly cyclic) with positive integer edge weights, find the single-source shortest paths tree from s to every other vertex in the graph.

Your algorithm should be asymptotically faster than Dijkstra’s algorithm on cyclic graphs.

Dijkstra’s: O(E log V) because of PQ operations (log V) part of the runtime.

O(log V)? O(E)?

4

Q

B

C

A

s

5

5

D

1

2

1

0

1

2

4

5 of 13

Positive Integer-Weighted Shortest Paths

Given a weighted, directed graph (possibly cyclic) with positive integer edge weights, find the single-source shortest paths tree from s to every other vertex in the graph.

Your algorithm should be asymptotically faster than Dijkstra’s algorithm on cyclic graphs.

​

Two contrasting ways of approaching the problem: algorithmic or reduction.

Both result in O(E) runtime.

See the external demo link in the upper-righthand corner.

5

A

6 of 13

DAG Longest Paths

Given a weighted DAG (possibly negative edge weights), find the single-source longest paths tree from s to every other vertex in the graph.

Give the runtime of your algorithm.

6

Q

B

C

A

s

5

5

D

1

2

1

0

1

2

4

7 of 13

DAG Longest Paths

Given a weighted DAG (possibly negative edge weights), find the single-source longest paths tree from s to every other vertex in the graph.

Give the runtime of your algorithm.

​

Reduction approach:

  • Negate the edges in the graph.
  • Run the DAG shortest paths algorithm.
  • Shortest paths tree returned from the algorithm is the longest paths tree we want.

7

A

8 of 13

Vertex Weights in Shortest Paths

How would you model vertex weights for shortest paths problems?

8

Q

v

b

e

x

Shortest Paths (Robert Sedgewick, Kevin Wayne/Princeton)

a

c

d

9 of 13

Vertex Weights in Shortest Paths

How would you model vertex weights for shortest paths problems?

The answer to this will help with seam carving since the energy function is defined per pixel.

Place weights on c, d, and e. (Why doesn’t it work to only place weights on a and b instead?)

Other answers might depend on the particular problem you want to solve.

9

A

v

b

e

x

Shortest Paths (Robert Sedgewick, Kevin Wayne/Princeton)

a

c

d

10 of 13

Q14 from COS 226 14sp Final (Solution)

10

11 of 13

Q12 from COS 226 15sp Final (Solution)

11

12 of 13

Longest Simple Paths in Arbitrary Graphs

It turns out that finding the longest simple path (containing no cycles) in a directed graph (possibly cyclic) is a “hard” problem. Best known algorithms involve brute force search.

Based on what we know about DAG longest paths, explain why this is much harder.

12

Q

13 of 13

Longest Simple Paths in Arbitrary Graphs

It turns out that finding the longest simple path (containing no cycles) in a directed graph (possibly cyclic) is a “hard” problem. Best known algorithms involve brute force search.

Based on what we know about DAG longest paths, explain why this is much harder.

13

A