The paper for this one is one of the older ones I have- it was published in 1972, but they say it was first submitted in 1970, which would be before Cook’s paper came out.
The problem: Feasible Basis Extension. This is problem MP4 in the appendix.
The description: Given an mxn matrix A of integers (m < n), and a column vector of size m, and a subset S of <m columns of A, can we find a non-singular (i.e., invertible) mxm submatrix B of A, such that:
- B contains all of the columns of S, and
- All of the elements of the vector , where = B-1 * are 0?
Example: I’ll try to keep the matrix calculations simple. Suppose A was:
and S was just the second column. Then B has to be a 2×2 submatrix of A that includes the second column, for example:
The inverse of this is:
Which, if we multiply by , gives us:
The paper by Murty is from 1972, so doesn’t really follow the same reduction structure we’re used to. The basic idea is to start with an instance of TSP, and realize that we can write a tour as an nxn matrix X where xij = 1 if the tour goes from city i to city j, and 0 otherwise. (This is basically a way of taking a permutation of the n cities, and stretching it out to an nxn 0-1 matrix). We can then write the TSP problem as a set of constraints: Each row in the solution sums to exactly 1, each column in the solution sums to exactly 1, and all entries are 0. We are trying to minimize the cost of all of the 1 entries in the solution. We can get the decision problem by adding a new constraint: That the costs of all of the entries is the K from the TSP instance.
He then shows that if this system has a feasible basis, it must be a tour that satisfies the TSP instance. The proof involves lemmas that talk about the “convex polytope” of the constraints, which I think needs some pretty sophisticated linear programming familiarity to follow.
Difficulty: 8. Maybe less if you are teaching a mathematical programming class- I don’t think the ideas are hard, but I do think they’re not likely to come up in an algorithms class.