Discrete Optimization 2023/2024
Homework 2
Graded exercises: 2 − 1, 2 − 2, and 2 − 3
Deadline for submission: Monday, September 25, 2023, 13:15
Exercise 2 − 1 (Matroids, 4 points)
(a) A shortest (s, t)-path in a directed graph G = (V, E) with edge lengths c : E → R≥0 can be seen as a
certain subset of the edges of the graph. Define an independence system on E via
I = {I ⊆ E | I is subset of some (s, t)-path} .
Is it a matroid? Give a proof or a counterexample.
(b) Consider two arbitrary matroids on the same ground set E, say M1 = (E, I1 ) and M2 = (E, I2 ).
Define M3 = (E, I3 ) as the intersection of M1 and M2 , that is, I ∈ I3 if and only if I ∈ I1 and I ∈ I2 .
Is M3 = (E, I3 ) a matroid? Give a proof or a counterexample. [Hint: Consider question 1 − 4]
Exercise 2 − 2 (Matroids, 3 points) Let M = (E, I) be a matroid, and w : E → R≥0 a weight function
on its elements. The following is a known fact about matroids (read “−” and “+” for operations on sets).
Strong basis exchange property. Given two bases B, B ′ ⊆ E for M , then for each e ∈ B \ B ′
there exists e′ ∈ B ′ \ B so that both B − e + e′ and B ′ − e′ + e are bases1 .
With this at hand show the following: For any two maximum weight bases B and B ′ , show that any e ∈ B\B ′
can be replaced by some e′ ∈ B ′ \ B so that B − e + e′ is again a basis and w(e) = w(e′ ).
Exercise 2 − 3 (Shortest paths, 3 points) Given is a directed graph G = (V, E) with edge lengths
c : E → R≥0 , and s ∈ V , and so that there are no positive length cycles in G. We adapt Dijkstra’s algorithm
as follows, in order to compute longest instead of shortest (s, v)-paths:
• Initialize d(s) = 0, d(v) = −∞ for all v ∈ V \ {s}.
• In each iteration, choose a vertex u with maximum label d(u) among all vertices V ∗ .
• redefine procedure relax to be: If d(v) < d(u) + c(uv) Then d(v) := d(u) + c(uv).
Is this correct? Give a proof, or give a counterexample.
Exercise 2 − 4 (Shortest paths) Suppose we are given an acyclic directed graph G = (V, E) with edge
lengths c : E → R, and assume that the vertices v ∈ V are numbered so that for all edges (vi , vj ) ∈ E, we
have that i < j.2
Suggest an algorithm to compute the shortest / longest (s, v)-path lengths for all v ∈ V , in linear time, that
is O( n + m ) where n = |V | and m = |E|. (Assuming that s = v1 ). Also argue why the algorithm is correct.
[Hint: Use the topological ordering of V , and an inductive proof to argue correctness.]
1 Note that the first statement, existence of e′ ∈ B ′ \ B so that B − e + e′ is again a basis, follows directly from the
augmentation property, by considering the two independent sets B − e and B ′ . The second part of the statement, however, is
new and in fact non-trivial to prove, but this is not the exercise.
2 Such an order of the vertices is called a topological order of the vertices of G. If the vertices are drawn on a line in order
v1 , . . . , vn , all directed edges go from left to right. A topological order exists and can be easily computed for any acyclic graph.
