COMP2870 Graph Algorithms

Walk

Alternating sequence of k vertices and k+1 edges.

Trail

Walk where edges are distinct

Path

Walk where vertices are distinct.

Cycle

A closed trail with no repeating vertices except the start and end.

Subgraph

Graph formed from the subsets of another graph’s vertices and edges.

Spanning

Contains all vertices from original

Induced

Contains all edges (and therefore vertices) from original

Connected Component

Inclusion-maximal connected subgraph

Tree

Connected, acyclic subgraph.

Each pair of vertices have 1 path between them.

Prim’s Algorithm

Greedy vertices smallest-to-biggest

Steps:

• Pick a vertex

• Add the next smallest edge connected to vertices

• Keep going until all vertices added

Greedy Algorithms

Algorithms which make the locally optimal choice at each stage in the hopes of finding the globally optimum choice.

Kruskal’s Algorithm

Make list of edges with weights, move from smallest to largest and add edge if it doesn’t form a cycle.
Steps:

• Sort edges in non-increasing order, i.e. for i, j in 1-|E|, e_i > e_j if w(e_i) > w(e_j)

• Add the next smallest edge if it doesn’t form a cycle

Steiner Tree

The minimum-weight spanning tree (MST) for a given subset of vertices in a graph, which may be forced to include other vertices to minimise the total edge weight.

Dijkstra’s Algorithm

Algorithm that finds the shortest path from a source vertex to all other vertices in a weighted graph. Can be changed so it finds the shortest path to 1 vertex.

Steps:

• Set distances from s to v to be edge weights if adjacent, infinity otherwise, and set dist(s, s) = 0

• For every unadded vertex

  • Find the next-smallest weight vertex and add it

  • Update weights for remaining vertices

Dynamic Programming

Solving complex problems by breaking them down into smaller subproblems to avoid recalculations.

Floyd-Warshall Algorithm

Algorithm to compute all pairs’ shortest paths in directed graphs.

Steps:

• Set all pairs of vertices to w(u, v), which is either the edge or infinity.

• For k = 1 → n:

  • dist_k(u, v) = min(dist_k-1(u, v), dist_k-1(u, k) + dist_k-1(k, v))

Network

Directed graph with a capacity function, c: E → N, and a source and sink vertex.

Flow

Non-negative integer function f: E → N for amount of material moving from source to sink of a network.

f⁺(v)

Total flow of edges exiting vertex v.

f^-(v)

Total flow of edges entering vertex v.

f⁺(S)

Total flow of edges exiting set S.

f^-(S)

Total flow of edges entering set S.

Feasible Flow

A flow that satisfies capacity constraints and conservation constraints for all vertices.

Capacity Constraint

For all e ∈ E, 0 <= f(e) <= c(e). i.e. each edge is within its capacity

Conservation Constraint

For every v ∈ V \ {s, t}, f^-(v) = f⁺(v). i.e. each vertex is lossless.

Value of a flow, val(f)

Net amount of flow passing from source to sink, i.e. f^-(t) - f⁺(t).

f-augmenting path

A path in a flow network where every forward edge has excess capacity (f(e) < c(e)) and every backward edge has non-zero flow (f(e) > 0), allowing for an increase in flow value.

Leeway

Minimum of all excess capacities on forward edges and non-zero flows on backward edges in a flow network.

Source/Sink Cut

A partition of the vertices in a flow network that separates vertices into a source and sink cut, S and T. The name of the edges from S to T is the cut itself.

Lemma 4.2

If U is a set of nodes in a network, and f is a flow, then f⁺(U) - f^-(U) = Σv∈U(f⁺(v) - f^-(v)). (i.e. net flow out of U is equal to the sum of the net flows of the vertices in U).

In particular, if [S, T] is a source-sink cut and f is a feasible flow, then f⁺(S) - f^-(S) = val(f) = f^-(T) - f⁺(T). (i.e. net flow out of S and net flow into T are both equal to the value of the flow).

Proof:

Let α = f+(U) − f−(U) and β = Σv∈U ( f+(v) − f−(v)).

Consider how the flow of an edge xy, f(xy), contributes to both α and β.

Cases:

• x, y ∈ U: f(xy) contributes nothing to α, since it’s contained. f(xy) contributes positively to β on one side and negatively on the other, and since it’s looking at the same edge from 2 ends, they cancel out. So both contribute 0.

• x, y ∈ U: No contribution, as they’re not part of the set.

• x ∈ U, y ∈ U: f(xy) contributes positively from the x side in both, since x is outgoing via xy, and receives 0 from y since y isn’t in U.

• x ∈ U, y ∈ U: f(xy) contributes negatively because it counts the incoming flow from y and the incoming flow for U, but not the outgoing (since x is not in U).

Summing contributions over all edges, we get α = β.

Linking to [S, T]:

If [S, T] is a source-sink cut and f is a feasible flow, we get that:

f+(T) - f-(T) = Σv∈T ( f+(v) − f−(v)), which is equal to -val(f), since for every v =/= t, f+(v) − f−(v) = 0.

Since f+(S) = f-(T), and f-(S) = f+(T),

f+(S) − f−(S) = f−(T) − f+(T) = val(f).

Ford-Fulkerson Algorithm

Algorithm which finds the maximum flow in a flow network or the minimum cut that separates the source and sink.

Steps:

• Start with R (reachable) = {s}, and S = empty.

• For each vertex, v, in R \ S:

  • Add all neighbouring vertices of v that are either backward edges of non-zero flow or forward edges with excess capacity.

  • Add v to S (seen)

  • If t is in R (if we reached the sink), trace back the path of inclusions leading to t to return the f-augmenting path.

  • If R == S we’ve reached a wall, so return to get the cut [S, V \ S].

Weak Duality (Corollary 4.3)

If f is a feasible flow and [S, T] is a source-sink cut, then val(f) <= cap(S, T)

Proof:

val(f) = f+(S) - f-(S).

val(f) <= f+(S) since f-(S) >= 0

f+(S) <= Σf(uv) where u∉S, v∈S, <= Σc(uv) = cap(S, T)

Therefore val(f) <= cap(S, T)

Strong Duality (Theorem 4.4)

In every network, the maximum value of a feasible flow is equal to the minimum capacity of a source-sink cut

Proof:

Let G=(V, E) is a network, with source, sink and capacity function.

A zero-flow f is a feasible flow. Given a feasible flow, we apply the labelling algorithm (Ford-Fulkerson) to add vertices to R until we either ‘break through’ and reach the sink, or create a cut when S=R.

If we break through, we increase the value of the flow by the leeway. We know the value is limited by the capacity of the source-sink cut (Corollary 4.3, weak duality) so this will happen a finite number of times. Eventually we reach S=R.

Once we reach this, we can form [S, T] where T = V \ S, where cap(S, T) = val(f). By the Ford-Fulkerson algorithm, once S=R, this meant there were no more valid edges to attempt, so all forward edges have flow = capacity, and all backward edges now have zero flow. Formally,

u ∈ S, v ∈ T ⇒ f (uv) = c(uv)
u ∈ T , v ∈ S ⇒ f (uv) = 0

Therefore:

• f^-(S) (backward edges into S from T) = 0

• f⁺(S) (forward edges from S to T) = cap(S, T)

By Lemma 4.2, (net flow out of S and net flow into T are both equal to the value of the flow), f⁺(S) - f^-(S) = val(f).

Therefore val(f) = cap(S, T).

f is a maximum flow and [S, T ] is a minimum cut, and hence the
maximum value of a feasible flow equals the minimum capacity of a source/sink cut.

Matching

A subset of the edge set of an undirected graph such that no two edges are adjacent (share a vertex).

Perfect matching

All vertices are covered by M, i.e. every vertex of an undirected graph is saturated by a matching.

Maximum matching

Biggest matching possible in the graph.

Bipartite Graph Matching Flow Algorithm

Algorithm for finding maximum matching in a bipartite graph, using flow networks.

Steps:

• Add a source and sink, then direct all edges going Source → V1 → V2 → Sink

• Add capacity of 1 to all edges

Theorem 5.1 - If f is a maximum flow in G’, and M is a matching where matched edges have flow, f(uv) = 1, then M is a maximum matching in G.

Proof:
First, to prove that M is a matching:

Suppose M is not a matching. This would mean there is exists 2 edges in M sharing a common end node, say uv and uw.

2 cases:

• The shared node is in V₁, so u ∈ V1, v, w ∈ V2. So f⁺(u) >= 2. su would be the only edge entering u, so f^-(u) <= 1. But now f^-(u) < f⁺(u), which contradicts capacity constraints.

• The shared node is in V₂, so v, w ∈ V1, u ∈ V2. So f^-(u) >= 2. ut would be the only edge exiting u, so f⁺(u) <= 1. But now f⁺(u) < f^-(u), contradicting capacity constraints.

Therefore M has to be a matching in G.

Now, to show M is a maximum matching:

Arguing by contradiction - assume M is not a maximum matching. That means there exists a matching M’ where |M’| > |M|. We construct f’ similar to M, where all involved edges, f(su), f(uv), f(vt) = 1, and for every remaining edge, f(e) = 0.

Cases:

• f’(su) = 0, so by construction of f’, f’(uv) = 0 for every v adjacent to u. So f^′−(u) = f^′+(u) = 0.

• f’(su) = 1, so by construction of f’, f’(uv) = 1 for exactly 1 edge between u and v, so there’s 1 edge in M’, and all other edges aren’t incident with the same vertex v. So f^′−(u) = f^′+(u) = 1.

• f’(vt) = 0, so by construction of f’, f’(uv) = 0 for every edge uv, f’(uv) = 0, So f^′−(v) = f^′+(v) = 0

• f’(vt) = 1, so by construction of f’, f’(uv) = 1 for exactly 1 edge between u and v, so there’s 1 edge in M’, and all other edges aren’t incident with the same vertex v. So f^′−(v) = f^′+(v) = 1.

So conservation constraint holds for all vertices in the graph.

Therefore f’ is a feasible flow.

val(f’) = |M’| > |M| = val(f), contradicting the assumption that f was a maximum flow.