Lecture 8

Greedy graph approximation algorithms (max-cut)

CSE 421 Autumn 2026

1

Previously…

2

Minimum spanning trees

Input: A connected graph , edge weights

Output: A tree , with , such that every vertex is connected and is minimized. This is called a minimum spanning tree.

3

Greedy Minimum MST algorithms

4

Build up the set of edges according to a simple rule.

Never go back and change.

Possible rules?

• Starting from a source vertex , add the edge of minimum weight that connects to an unvisited vertex.
• Simply add the edge of minimum weight that doesn’t create a cycle. Without requiring that the edge connects to the previous vertex set.

Prim’s algorithm

Kruskal’s algorithm

A unified argument for proving correctness

Of both Prim’s and Kruskal’s algorithm

Definition: An edge is safe for some subset of edges if there is some compatible cut such that is the minimum weight edge crossing the cut.

Theorem: Greedy algorithms that always choose edges that are safe for the current set of selected edges correctly compute an MST.

5

We proved this powerful theorem.

Then, all that was left to do was to argue that Prim’s and Kruskal’s always pick a safe edge.

Greedy algorithm proof strategies

• “Greedy algorithm stays ahead”: Show that after each step of the greedy algorithm, its solution is at least as good as any other algorithms
• Structural: Show the greedy algorithm produces a solution with a certain useful property. And any solution with this property must be optimal.
• Exchange argument: We can gradually transform any solution into the one found by the greedy algorithm with each transformation only improving or maintaining the value of the current solution.

6

What we did to prove correctness of greedy algorithm that adds safe edges.

Today

7

• Greedy graph algorithms:
• Wrapping up Prim’s and Kruskal’s implementation
• Greedy graph approximation algorithm for Max-Cut
• Start on Divide and Conquer

Greedy Minimum MST algorithms

8

Build up the set of edges according to a simple rule.

Never go back and change.

Possible rules?

• Starting from a source vertex , add the edge of minimum weight that connects to an unvisited vertex.
• Simply add the edge of minimum weight that doesn’t create a cycle. Without requiring that the edge connects to the previous vertex set.

Prim’s algorithm

Kruskal’s algorithm

Implementation of Prim’s & runtime

We need a data structure to quickly find the minimal-weight edge from the current vertex set to .

Similar to Dijkstra’s. We can use a priority queue (binary heap) keyed by, for each vertex , the weight of the minimum edge connecting to .

This allows us to efficiently:

• Extract the vertex with minimum key, i.e. the mimimum-weight edge leaving
• Update keys when we add new vertices to .

Both of these operations can be done in time. So, with this implementation,�Prim’s runtime: .�

9

Greedy Minimum MST algorithms

10

Build up the set of edges according to a simple rule.

Never go back and change.

Possible rules?

• Starting from a source vertex , add the edge of minimum weight that connects to an unvisited vertex.
• Simply add the edge of minimum weight that doesn’t create a cycle. Without requiring that the edge connects to the previous vertex set.

Prim’s algorithm

Kruskal’s algorithm

Implementation of Kruskal’s & runtime

We need a data structure to quickly find minimal-weight edges that don’t create a cycle.

For this, we can use a “disjoint-set data structure” (also called union-find) to keep a partition of the vertex set into connected components based on the current edge set. ��So, initially, when the edge set is empty, each vertex is its own connected component. These components get merged as we add more edges.

The union-find data structure allows us to efficiently:

• Determine if two vertices are in different connected components.
• Merge two components together.

11

Implementation of Kruskal’s & runtime

The union-find data structure allows us to efficiently:

• Determine if two vertices are in different connected components.
• Merge two components together.

​

We can proceed as follows:

• Start by sorting the edges in increasing order of weight.
• Process each edge : check if it creates a cycle by checking if and lie in the same component. If they don’t, add the edge to the set, and merge the two components.

​

With union-find, checking and merging both take almost constant time, so the runtime of the algorithm is dominated by the sorting of the edges: .

12

Applications of MST

• Network design — minimal cost connectivity for telephone, electrical, cable, internet networks
• Approximation algorithms for computational problems - traveling problem, Steiner trees
• Indirect applications
• Max bottleneck paths
• LDPC error correcting codes
• Image restoration under Renyí entropy
• Reducing data storage in sequencing amino acids
• Modeling local particle interaction in turbulence flows
• Autoconfig protocol for Ethernet bridging to avoid network cycles

13

Greedy graph approximation algorithms

14

Maximizing bipartiteness

• We saw how to verify if a graph is bipartite or not using BFS or DFS
• We could also come up with a “measure of bipartiteness”

​

• For each possible coloring , this counts how many edges are colored “correctly”
• The is the max number of edges colored correctly over all colorings
• Deciding if or can be done by BFS or DFS
• Is there an algorithm for computing in general?

15

Why is it called MaxCut?

• The function partitions the vertices in two sets (yellow and blue).
• A partition of the vertices into two sets is also called a cut.
• We say that an edge crosses the cut if and .
• counts the maximum number of edges that cross any cut.

16

A proof that MaxCut is always

• Choose uniformly randomly and independently.
• Then for any edge , let be the indicator random variable for the event that crosses the cut.

​

17

A proof that MaxCut is always

• Choose uniformly randomly and independently.
• Then for any edge , let be the indicator random variable for the event that crosses the cut.
• Since and are chosen uniformly randomly, .
• Overall, the expected number of edges crossing is:
• By linearity of expectation, .
• A random cut crosses on average edges. Therefore, there must exist some cut that crosses edges. Therefore .

18

Finding a cut with crossing edges

We know a cut exists crossing edges. Can we find it efficiently?

First idea: based on the previous slide, we could pick a uniformly random color for each vertex.

Since the average number of edges crossing is , we should have at least a reasonable probability of getting a cut that has crossings?

19

This is not true :) (Think about why!)

If you are satisfied with , for some , then you can get a constant probability of that happening. But you can’t avoid a small loss.

Finding a cut with crossing edges

We know a cut exists crossing edges. Can we find it efficiently?

Second idea:

​

​

​

20

Finding a cut with crossing edges

We know a cut exists crossing edges. Can we find it efficiently?

Second idea: let’s use a greedy algorithm!

​

​

​

21

Algorithm overview: Color the first vertex as 0 (yellow). Then, for every future vertex , if has more 0 (yellow) neighbors than 1’s (blue), assign it the color 1 (blue), otherwise assign it 0 (yellow).

Finding a cut with crossing edges

We know a cut exists crossing edges. Can we find it efficiently?

Second idea: let’s use a greedy algorithm!

​

​

​

22

Algorithm overview: Color the first vertex as 0 (yellow). Then, for every future vertex , if has more 0 (yellow) neighbors than 1’s (blue), assign it the color 1 (blue), otherwise assign it 0 (yellow).

Finding a cut with crossing edges

We know a cut exists crossing edges. Can we find it efficiently?

Second idea: let’s use a greedy algorithm!

​

​

​

23

Algorithm overview: Color the first vertex as 0 (yellow). Then, for every future vertex , if has more 0 (yellow) neighbors than 1’s (blue), assign it the color 1 (blue), otherwise assign it 0 (yellow).

Finding a cut with crossing edges

We know a cut exists crossing edges. Can we find it efficiently?

Second idea: let’s use a greedy algorithm!

​

​

​

24

Algorithm overview: Color the first vertex as 0 (yellow). Then, for every future vertex , if has more 0 (yellow) neighbors than 1’s (blue), assign it the color 1 (blue), otherwise assign it 0 (yellow).

Finding a cut with crossing edges

We know a cut exists crossing edges. Can we find it efficiently?

Second idea: let’s use a greedy algorithm!

​

​

​

25

Algorithm overview: Color the first vertex as 0 (yellow). Then, for every future vertex , if has more 0 (yellow) neighbors than 1’s (blue), assign it the color 1 (blue), otherwise assign it 0 (yellow).

Finding a cut with crossing edges

We know a cut exists crossing edges. Can we find it efficiently?

Second idea: let’s use a greedy algorithm!

​

​

​

26

Algorithm overview: Color the first vertex as 0 (yellow). Then, for every future vertex , if has more 0 (yellow) neighbors than 1’s (blue), assign it the color 1 (blue), otherwise assign it 0 (yellow).

Finding a cut with crossing edges

We know a cut exists crossing edges. Can we find it efficiently?

Second idea: let’s use a greedy algorithm!

​

​

​

27

Algorithm overview: Color the first vertex as 0 (yellow). Then, for every future vertex , if has more 0 (yellow) neighbors than 1’s (blue), assign it the color 1 (blue), otherwise assign it 0 (yellow).

Finding a cut with crossing edges

We know a cut exists crossing edges. Can we find it efficiently?

Second idea: let’s use a greedy algorithm!

​

​

​

28

Algorithm overview: Color the first vertex as 0 (yellow). Then, for every future vertex , if has more 0 (yellow) neighbors than 1’s (blue), assign it the color 1 (blue), otherwise assign it 0 (yellow).

Finding a cut with crossing edges

We know a cut exists crossing edges. Can we find it efficiently?

Second idea: let’s use a greedy algorithm!

​

​

​

29

Algorithm overview: Color the first vertex as 0 (yellow). Then, for every future vertex , if has more 0 (yellow) neighbors than 1’s (blue), assign it the color 1 (blue), otherwise assign it 0 (yellow).

Here, 10 out of 14 edges are good.

What about in general?

Proof greedy algorithm gets at least

30

Proof:

Theorem: The greedy algorithm always produces a cut with crossing edges.

Proof greedy algorithm gets at least

31

Proof: Consider the set of edges used to determine the color of vertex .

Theorem: The greedy algorithm always produces a cut with crossing edges.

Proof greedy algorithm gets at least

32

Proof: Consider the set of edges used to determine the color of vertex . By choosing the color of to be the opposite of the majority of neighbors, at least half of the edges of will cross the cut.

Theorem: The greedy algorithm always produces a cut with crossing edges.

Proof greedy algorithm gets at least

33

Proof: Consider the set of edges used to determine the color of vertex . By choosing the color of to be the opposite of the majority of neighbors, at least half of the edges of will cross the cut.

Note that every edge is in exactly one set where is the later of its two vertices to be assigned a color.

Since and at least half of the edges of each cross the cut, then at least half the edges of cross the cut.

Theorem: The greedy algorithm always produces a cut with crossing edges.

Proof greedy algorithm gets at least

34

Theorem: The greedy algorithm always produces a cut with crossing edges.

We showed that the greedy algorithm finds a cut with at least crossings.

Does it actually do even better?

Greedy algorithm can be suboptimal

The greedy algorithm can be suboptimal and fail to find the max cut. One can design examples where it fails.

Consider this graph on vertices:

35

• There is an edge connecting each vertex on the left to each vertex on the right.
• Additionally, there are vertical edges on the left: 1->2, 2->3, etc.

The greedy algorithm that explores vertices in the order that they are numbered colors as in the picture.

Greedy algorithm can be suboptimal

The greedy algorithm can be suboptimal and fail to find the max cut. One can design examples where it fails.

Consider this graph on vertices:

36

• There is an edge connecting each vertex on the left to each vertex on the right.
• Additionally, there are vertical edges on the left: 1->2, 2->3, etc.

The greedy algorithm that explores vertices in the order that they are numbered colors as in the picture.

Greedy algorithm can be suboptimal

The greedy algorithm can be suboptimal and fail to find the max cut. One can design examples where it fails.

Consider this graph on vertices:

37

• There is an edge connecting each vertex on the left to each vertex on the right.
• Additionally, there are vertical edges on the left: 1->2, 2->3, etc.

The greedy algorithm that explores vertices in the order that they are numbered colors as in the picture.

Greedy cut:

Optimal cut:

If the rule breaks ties in favor of yellow

NP-completeness

• MaxCut is an -complete problem.
• For this reason, we do not believe there is an efficient algorithm for MaxCut.
• The greedy algorithm always produces a factor approximation of the optimal cut but does not do better than this in general (due to our example).
• The best known efficient approximation algorithm achieves a factor (Goemans-Williamson ‘94)
• Believed to be NP-hard to get any better constant approximation algorithm. This belief is true assuming something known as the “Unique Games Conjecture”.
• This conjecture was proved in OpenAI’s latest math release!

​

​

​

38