• (34 pts) Extreme points. For a graph G = (V; E) and a weight function w : E ! R+ consider the following linear program:
s.t.
Pe2E
w
e
x
e
min
Pe2xe
0
for all e
2
E;
(u) xe
1
for all u
2
V
where (u) stands for the set of edges in E incident on u. Prove that every extreme point solution is supported on a disjoint union of odd length cycles and stars.
Hint: first show that no extreme point solution can contain an even length cycle in its support; then consider an odd length cycle with a path attached to it, and then two odd length cycles connected by a path.
• (33 pts) Partitioning into disjoint bases. Give an algorithm that, taking as input a matrix A 2 Rn kn for integers n; k 1, outputs YES if the columns of A can be partitioned into k sets such that every set forms a basis of Rn, and outputs NO otherwise.
Hint: use matroid intersection.
• (33 pts) Implementation. The objective of this problem is to successfully solve the problem Minimum spanning tree dual program on our online judge. You will find detailed instructions on how to do this on Moodle.
Hint: you may find Section 5 of these notes useful: https: // theory. epfl. ch/ courses/ topicstcs/ Lecture52015. pdf .
Page 1 (of 1)
