1

CS61B, Spring 2025 @ UC Berkeley

Slides credit: Josh Hug

Directed Acyclic Graphs

Lecture 26 (Graphs 5)

Goals of Today

Today, to practice our problem solving skills, we’ll work through some very challenging A-level problems using the tools we’ve already learned about.

​

Will focus on graphs, but the ideas today are more general.

Graph Problems So Far

Graph Problems So Far

Topological Sorting

Lecture 26, CS61B, Spring 2025

Topological Sorting

Shortest Paths on DAGs

Longest Paths

Reductions

• Definition
• Reduction to 3SAT (Optional CS170 Preview)

Topological Sort

Suppose we have tasks A through H, where an arrow from v to w indicates that v must happen before w.

• What algorithm do we use to find a valid ordering for these tasks?
• Valid orderings include: [A, C, B, D, F, E, H, G], [C, A, D, F, B, E, G, H], …

Solution (Spoiler Alert)

Perform a DFS traversal from every vertex with indegree 0, NOT clearing markings in between traversals.

• Record DFS postorder in a list.
• Topological ordering is given by the reverse of that list (reverse postorder).

Topological Sort (Demo 1/2)

Topological Sort (Demo 2/2)

Solution (Spoiler Alert)

Perform a DFS traversal from every vertex with indegree 0, NOT clearing markings in between traversals.

• Record DFS postorder in a list: [H, E, B, D, A, G, F, C]
• Topological ordering is given by the reverse of that list (reverse postorder):
• [C, F, G, A, D, B, E, H]

Topological Sort

The reason it’s called topological sort: Can think of this process as sorting our nodes so they appear in an order consistent with edges, e.g. [C, F, G, A, D, B, E, H]

• When nodes are sorted in diagram, arrows all point rightwards.

A

B

C

D

E

F

G

H

A

B

C

D

E

F

G

H

Depth First Search

Be aware, that when people say “Depth First Search”, they sometimes mean with restarts, and they sometimes mean without.

​

For example, when we did DepthFirstPaths for reachability, we did not restart.

​

For Topological Sort, we restarted from every vertex with indegree 0.

​

​

Question

What is the runtime to find all vertices of indegree 0?

• Interesting thing I did not tell you: You don’t have to.

​

Another better topological sort algorithm:

• Run DFS from an arbitrary vertex.
• If not all marked, pick an unmarked vertex and do it again.
• Repeat until done.

​

​

Test Your Understanding

Give a topological ordering for the graph below (a.k.a. topological sort).

Test Your Understanding

Give a topological ordering for the graph below (a.k.a. topological sort)

• A, D, B, C, E, F (because DFS postorder was FECBDA)

B

D

C

E

F

A

s

4

2

6

1

1

1

3

1

Recall that we can think of topological sort as an ordering of “tasks”.

Directed Acyclic Graphs

A topological sort only exists if the graph is a directed acyclic graph (DAG).

• For the graph below, there is NO possible ordering where all arrows are respected.

​

​

​

​

​

​

​

DAGs appear in many real world applications, and there are many graph algorithms that only work on DAGs.

​

Graph Problems

Shortest Paths on DAGs

Lecture 26, CS61B, Spring 2025

Topological Sorting

Shortest Paths on DAGs

Longest Paths

Reductions

• Definition
• Reduction to 3SAT (Optional CS170 Preview)

Shortest Paths Warmup

What is the shortest paths tree for the graph below, using s as the source? In what order will Dijkstra’s algorithm visit the vertices?

Graph from Algorithms, by Vazirani/Papadimitriou

Shortest Paths Warmup

What is the shortest paths tree for the graph below, using s as the source? In what order will Dijkstra’s algorithm visit the vertices?

• A, B, D, E, F, C

1

2

5

7

6

6

Shortest Paths Warmup

If we allow negative edges, Dijkstra’s algorithm can fail.

• For example, below we see Dijkstra’s just before vertex C is visited.

1

1

2

7

3

Shortest Paths Warmup

If we allow negative edges, Dijkstra’s algorithm can fail.

• For example, below we see Dijkstra’s just before vertex C is visited.
• Relaxation on E succeeds, but distance to F will never be updated.

1

1

2

7

3

-13

Shortest Paths Warmup

If we allow negative edges, Dijkstra’s algorithm can fail.

• For example, below we see Dijkstra’s just before vertex C is visited.
• Relaxation on E succeeds, but distance to F will never be updated.

1

1

7

3

-13

distTo is wrong!

Challenge

Try to come up with an algorithm for shortest paths on a DAG that works even if there are negative edges.

• Hint: You should still use the “relax” operation as a basic building block.

∞

∞

∞

∞

∞

Challenge

Try to come up with an algorithm for shortest paths on a DAG that works even if there are negative edges.

• Hint: You should still use the “relax” operation as a basic building block.

One simple idea: Visit vertices in topological order.

• On each visit, relax all outgoing edges.
• Each vertex is visited only when all possible info about it has been used!

∞

∞

∞

∞

∞

The DAG SPT Algorithm: Relax in Topological Order

First: We have to find a topological order, e.g. ADBCEF. Runtime is O(V + E).

B

D

C

E

F

A

s

25

1

6

1

-20

1

1

1

∞

∞

∞

∞

∞

The DAG SPT Algorithm: Relax in Topological Order

Second: We have to visit all the vertices in topological order, relaxing all edges as we go. Let’s see a demo.

B

D

C

E

F

A

s

1

6

1

-20

1

1

1

25

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

distTo edgeTo

A 0 -

B ∞ -

C ∞ -

D ∞ -

E ∞ -

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

1

1

Fringe: [A, D, B, C, E, F]

0

∞

∞

∞

∞

∞

25

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

distTo edgeTo

A 0 -

B ∞ -

C ∞ -

D ∞ -

E ∞ -

F ∞ -

B

D

C

D

F

A

s

1

6

1

-20

1

1

1

0

∞

∞

∞

∞

∞

Fringe: [A, D, B, C, E, F]

25

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

distTo edgeTo

A 0 -

B 1 A

C ∞ -

D 1 A

E ∞ -

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

1

1

0

∞

∞

∞

∞

∞

1

1

Fringe: [A, D, B, C, E, F]

25

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

distTo edgeTo

A 0 -

B 1 A

C ∞ -

D 1 A

E ∞ -

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

1

1

0

∞

∞

∞

1

1

Fringe: [A, D, B, C, E, F]

25

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

distTo edgeTo

A 0 -

B 1 A

C ∞ -

D 1 A

E 2 D

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

1

1

0

∞

∞

∞

1

1

2

Fringe: [A, D, B, C, E, F]

25

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

distTo edgeTo

A 0 -

B 1 A

C ∞ -

D 1 A

E 2 D

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

1

1

0

∞

∞

1

1

2

Fringe: [A, D, B, C, E, F]

25

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

distTo edgeTo

A 0 -

B 1 A

C 7 B

D 1 A

E 2 D

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

1

1

0

∞

∞

1

1

7

2

Fringe: [A, D, B, C, E, F]

25

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

distTo edgeTo

A 0 -

B 1 A

C 7 B

D 1 A

E 2 D

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

1

1

0

∞

1

1

7

2

Fringe: [A, D, B, C, E, F]

25

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

distTo edgeTo

A 0 -

B 1 A

C 7 B

D 1 A

E -13 C

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

1

1

0

∞

1

1

7

2

-13

8

Fringe: [A, D, B, C, E, F]

25

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

distTo edgeTo

A 0 -

B 1 A

C 7 B

D 1 A

E -13 C

F ∞ -

B

D

C

E

F

A

s

1

6

1

-20

1

1

1

0

1

1

7

-13

8

Fringe: [A, D, B, C, E, F]

25

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

distTo edgeTo

A 0 -

B 1 A

C 7 B

D 1 A

E -13 C

F -12 E

B

D

C

E

F

A

s

1

6

1

-20

1

1

1

0

∞

1

1

7

-13

-12

Fringe: [A, D, B, C, E, F]

25

DAG SPT Algorithm

Visit vertices in topological order.

• When we visit a vertex: relax all of its going edges.

distTo edgeTo

A 0 -

B 1 A

C 7 B

D 1 A

E -13 C

F -12 E

B

D

C

E

F

A

s

1

6

1

-20

1

1

1

0

1

1

7

-13

-12

Fringe: [A, D, B, C, E, F]

25

The DAG SPT Algorithm: Relax in Topological Order

Second: We have to visit all the vertices in topological order, relaxing all edges as we go.

• Runtime for step 2 is also O(V + E).

​

Occasional question: why isn’t it O(V*E)? We’re relaxing all edges from each vertex.

• Keep in mind that E is the total number of edges in the entire graph, not the number of edges per vertex.�Example: for the graph below, E = 8.

B

D

C

E

F

A

s

1

1

6

1

-20

1

1

1

Graph Problems

Note: The DAG shortest paths solution uses the topological sort solution as a subroutine.

Longest Paths

Lecture 26, CS61B, Spring 2025

Topological Sorting

Shortest Paths on DAGs

Longest Paths

Reductions

• Definition
• Reduction to 3SAT (Optional CS170 Preview)

The Longest Paths Problem

Consider the problem of finding the longest path tree (LPT) from s to every other vertex. The path must be simple (no cycles!).

B

C

D

E

F

G

A

s

5

2

1

15

3

2

11

5

1

1

4

1

The Longest Paths Problem

Consider the problem of finding the longest path tree (LPT) from s to every other vertex. The path must be simple (no cycles!).

Some surprising facts:

• Best known algorithm is exponential (extremely bad).
• Perhaps the most important unsolved problem in mathematics.

Two potentially interesting exercises after lecture:

• Find an example where the obvious algorithm (Dijkstra’s but pick the biggest edge first) fails.
• Figure out: Is the longest path to every other vertex always a tree (i.e. does an LPT exist for all graphs)?

B

C

D

E

F

G

A

s

5

2

1

15

3

2

11

5

1

1

4

1

2

13

7

15

22

20

The Longest Paths Problem on DAGs

Difficult challenge for you.

• Solve the LPT problem on a directed acyclic graph.
• Algorithm must be O(E + V) runtime.

6

2

12

14

13

0

The Longest Paths Problem on DAGs

DAG LPT solution for graph G:

• Form a new copy of the graph G’ with signs of all edge weights flipped.
• Run DAGSPT on G’ yielding result X.
• Flip signs of all values in X.distTo. X.edgeTo is already correct.

-6

-2

-12

-14

-13

0

The Longest Paths Problem on DAGs

DAG LPT solution for graph G:

• Form a new copy of the graph G’ with signs of all edge weights flipped.
• Run DAGSPT on G’ yielding result X.
• Flip signs of all values in X.distTo. X.edgeTo is already correct.

B

D

C

E

F

A

s

6

2

12

14

13

0

A Note on “Mathematical Maturity”

If you have a very high degree of so-called “mathematical maturity”, this algorithm should seem plainly correct.

​

There’s no real need to prove anything or show demos.

• We know DAG SPT works on graphs with negative edge weights.
• We also know that -(-a + -b + -c + -d) = a + b + c + d.

​

Part of what you’re learning in your intense technical education here at Berkeley is mathematical maturity. Hasn’t been a major focus in 61B, but will be in other courses like 16A, 16B, 70, 170, ...

Highly Recommended Exercise For Later

Play around with the longest paths problem and convince yourself that it is actually very hard.

• Try to develop an intuition for why it is hard. Even better if you try to put it into english.
• Try searching the internet for “why longest paths hard” or similar if you’re having trouble really pinning down what’s so hard about it.

Graph Problems

Reductions: Definition

Lecture 26, CS61B, Spring 2025

Topological Sorting

Shortest Paths on DAGs

Longest Paths

Reductions

• Definition
• Reduction to 3SAT (Optional CS170 Preview)

DAG Longest Paths

The problem solving we just used probably felt a little different than usual:

• Given a graph G, we created a new graph G’ and fed it to a related (but different) algorithm, and then interpreted the result.

G

DAG-LPT

Preprocess

DAG-SPT

G’

SPT of G’

Postprocess

LPT of G

Reduction

This process is known as reduction.

• Since DAG-SPT can be used to solve DAG-LPT, we say that “DAG-LPT reduces to DAG-SPT”.

G

DAG-LPT

Preprocess

DAG-SPT

G’

SPT of G’

Postprocess

LPT of G

Reduction Analogy

This process is known as reduction.

• Since DAG-SPT can be used to solve DAG-LPT, we say that “DAG-LPT reduces to DAG-SPT”.

​

As a real-world analog, suppose we want to climb a hill. There are many ways to do this:

• “Climbing a hill” reduces to “riding a ski lift.”
• “Climbing a hill” reduces to “being shot out of a cannon.”
• “Climbing a hill” reduces to “riding a bike up the hill.”

​

Reduction Definition (Informal)

This process is known as reduction.

• Since DAG-SPT can be used to solve DAG-LPT, we say that “DAG-LPT reduces to DAG-SPT”.

​

Algorithms by Dasgupta, Papadimitriou, and Vazirani defines a reduction informally as follows:

• “If any subroutine for task Q can be used to solve P, we say P reduces to Q.”

​

Can also define the idea formally, but way beyond the scope of our class.

• If you’re curious, you can read more about Karp and Cook reductions.

​

Reduction to 3SAT (Optional CS170 Preview)

Lecture 26, CS61B, Spring 2025

Topological Sorting

Shortest Paths on DAGs

Longest Paths

Reductions

• Definition
• Reduction to 3SAT (Optional CS170 Preview)

The Independent Set Problem

An independent set is a set of vertices in which no two vertices are adjacent.

​

The Independent-set Problem:

• Does there exist an independent set of size k?
• i.e. color k vertices red, such that none touch.

​

Example for the graph on the right and k = 9

• For this particular graph, N=24.

The 3SAT Problem

3SAT: Given a boolean formula, does there exist a truth value for boolean variables that obeys a set of 3-variable disjunctive constraints?

​

​

​

​

Example: (x1 || x2 || !x3) && (x1 || !x1 || x1) && (x2 || x3 || x4)

• Solution: x1 = true, x2 = true, x3 = true, x4 = false

3 variable disjunctive constraint�

3SAT Reduces to Independent Set

Proposition: 3SAT reduces to Independent-set.

​

Proof. Given an instance ϕ of 3-SAT, create an instance G of Independent-set:

• For each clause in ϕ, create 3 vertices in a triangle.
• Add an edge between each literal and its negation (can’t both be true in 3SAT means can’t be in same set in Independent-set)

​

Φ = (x1 or x2 or x3) and (! x1 or ! x2 or x4) and (! x1 or x3 or ! x4) and (x1 or x3 or x4)

x2

x1

x3

! x2

x4

! x1

! x4

x3

! x1

x3

x1

x4

k = number of variables = 4

3SAT Reduces to Independent Set

Find an independent set of size k = 4. Use this set to generate a solution to the 3SAT problem.

• Reminder: An independent set of size 4 is a set of 4 (red) vertices that do not touch.

Φ = (x1 or x2 or x3) and (! x1 or ! x2 or x4) and (! x1 or x3 or ! x4) and (x1 or x3 or x4)

x2

x1

x3

! x2

x4

! x1

! x4

x3

! x1

x3

x1

x4

k = number of variables = 4

3SAT Reduces to Independent Set

Find an independent set of size k = 4. Use this set to generate a solution to the 3SAT problem.

• Reminder: An independent set of size 4 is a set of 4 (red) vertices that do not touch.

Φ = (x1 or x2 or x3) and (! x1 or ! x2 or x4) and (! x1 or x3 or ! x4) and (x1 or x3 or x4)

x2

x1

x3

! x2

x4

! x1

! x4

x3

! x1

x3

x1

x4

k = number of variables = 4

Reduction

Since IND-SET can be used to solve 3SAT, we say that “3SAT reduces to IND-SET”.

• Note: 3SAT is not a graph problem!
• Note: Reductions don’t always involve creating graphs.

​

3SAT

Preprocess

IND-SET

G

IND-SET for G

Postprocess

Assignment so

that Φ gives true.

Φ

x1: true

x2: false

x3: true

x4: true

Reductions and Decomposition

Arguably, we’ve been doing something like a reduction all throughout the course.

​

These examples aren’t reductions exactly.

• We aren’t just calling a subroutine.
• A better term would be decomposition: Taking a complex task and breaking it into smaller parts. This is the heart of computer science.
• Using appropriate abstractions makes problem solving vastly easier.

Generational Changes in the Human Mind