18.997 Topics in Combinatorial Optimization: Lecture 16 Notes

18.997 Topics in Combinatorial Optimization April 8, 2004 Lecture 16 This lecture is about jump systems. While they are briefly discussed in chapter 41 of Schrijver’s book, they are not covered extensively. A good reference for this material is a set of notes by Jim Geelen, available at http://www.math.uwaterloo.ca/~jfgeelen/publications/js.ps. 1 The Basics of Jump Systems We begin with some notational definitions that will simplify the rest of our discussion. Definition 1. For x, y ∈ Zn , we let the box [x, y] be the set {z ∈ Zn | min(xi , yi ) ≤ zi ≤ max(xi , yi )∀i ∈ {1, . . . , n}}. In that which follows, we shall use the L1 metric unless otherwise stated. That is, for x, y ∈ Zn , we shall have n � |xi − yi |. d(x, y) = ||x − y||1 = i=1 Definition 2. For x, y ∈ Zn , a step x
from x to y is a point x
∈ Zn such that x
∈ [x, y] and d(x, x
) = 1. We can now define our main objects of study: Definition 3. A jump system is a set J ⊆ Zn such that if x
is a step from x to y, then either 1. x
∈ J, or 2. There exists a step x

from x
to y such that x

∈ J. We now consider some examples of jump systems. Example 1. Let M be a matroid over a set S, |S| = n. We let each coordinate of Zn correspond to an element of S, and let J ⊆ {0, 1}n be the set of characteristic functions for bases of M , J = {χB |B a basis of M }. Claim 1. The set J is a jump system. Proof. Let x and y be the respective characteristic vectors of two bases b1 and b2 of M . A step x
from x to y corresponds to either: 1. Adding to b1 an element of b2 \ b1 , or 2. Removing from b1 some element of b1 \ b2 . / J. Since all bases have the same size, the set corresponding to x
will never be a basis, so x
∈ We thus require there to be some step x

from x
to y such that x

∈ J, i.e., such that the set corresponding to x

is a basis. In both cases, this is guaranteed by Basis Exchange (see lecture 11). 16-1 Example 2. Let G = (V, E) be an undirected graph, and let n = |V |. For every subgraph H = (V, F ) of G, we can construct its degree sequence dH ∈ Zn by setting the ith coordinate of dH equal to the degree in H of the ith vertex of G. Now let J = {dH |H is a subgraph of G} be the set of all degree sequences of subgraphs of G. Claim 2. J is a jump system. We could check this directly, but it would be rather tedious. Instead, we shall describe several operations that one can perform on jump systems that give rise to other jump systems. We will then show how to construct J using these operations, from which Claim 2 will follow. 2 Operations on Jump Systems In this section, we describe several operations on jump systems. Throughout the sequel, let J ⊆ Zn be a jump system. Translation If J is a jump system, J + a is a jump system for any vector a ∈ Zn . Reflection For some i ∈ {1, . . . , n} reflect the entire jump system through the xi = 0 plane, replacing each point (x1 , . . . , xn ) ∈ J with (x1 , . . . , −xi , . . . , xn ). This clearly produces another jump system. Projection Project onto some axis-parallel subspace of Zn . That is, let S ⊆ {1, . . . , n} be some subset of the coordinates, and create a new set JS = {x|S , x ∈ J}. To see that JS is a jump system, note that the projection of a step either gives a step or no motion at all. Sum If J1 and J2 are jump systems, define a new set J1 + J2 := {x + y|x ∈ J1 , y ∈ J2 }. Claim 3. J1 + J2 is a jump system. Proof. Let x1 , y1 ∈ J1 , x2 , y2 ∈ J2 , x = x1 + x2 , y = y1 + y2 , and suppose that x
is a step from x to y. We shall show that either x
∈ J1 + J2 or that there exists a step x

∈ J from x
to y. Take z1 ∈ J1 , z2 ∈ J2 such that d(x
, z1 + z2 ) = 1 and so that d(z1 , y1 ) + d(z2 , y2 ) is minimized. This is always possible, since d(x
, x1 + x2 ) = 1. We now have two possibilities: Case 1: z1 + z2 ∈ [x
, y]. In this case, we are already done, since z1 + z2 ∈ J, and z1 + z2 is a step from x
to y. Case 2: x
∈ [z1 + z2 , y]. Let x
= z1 +z2 +s, so that z1 +z2 +s ∈ [z1 +z2 , y1 +y2 ]. This implies that either z1 +s ∈ [z1 , y1 ] or z2 +s ∈ [z2 , y2 ]. By symmetry, we may assume without loss of generailty that z1 +s ∈ [z1 , y1 ]. We now have two possibilities: 1. z1 + s ∈ J1 , or / J1 . 2. z1 + s ∈ 16-2 In the first case, we are done, since x
= (z1 + s) + z2 ∈ J1 + J2 , as required. In the second case, the fact that J1 is a jump system implies that there exists a step z1
∈ J1 from z1 + s to y. It thus follows easily that d(z1
+ y1 ) + d(z2 , y2 ) < d(z1 , y1 ) + d(z2 , y2 ). However, since d(z1
+ z2 , x
) = 1, and since z1 + z2 was chosen from points satisfying this condition so as to minimize d(z1 , y1 ) + d(z2 , y2 ), we must have d(z1
, y1 ) + d(z2 , y2 ) ≥ d(z1 , y1 ) + d(z2 , y2 ), thereby resulting in a contradiction. We can now prove Claim 2 and show that the set described in Example 2 is in fact a jump system. Proof of Claim 2. If G is a single edge connecting two vertices i and j, the degree sequences are just {0, ei + ej }, which is obviously a jump system. If G is a more complicated graph, its set of degree sequences is just the sum of the jump systems for each of its edges, which is a jump sequence by Claim 3. 3 Optimizing Over a Jump System Suppose we have some vector (wi ), i = 1, . . . , n. In this section, we shall show how to maximize wT x for x ∈ J. By reflecting and reordering the coordinates if necessary, we may assume w1 ≥ w2 ≥ · · · ≥ wn ≥ 0. We shall find the optimum with the following greedy algorithm: J0 = J For i=1 to n Ji ← arg maxx∈Ji−1 xi Return Jn , where the argmax returns the set of all values achieving the maximum. Claim 4. This algorithm returns the desired maximum. Proof. Suppose to the contrary. By induction on i, we can assume that the maximum taken over J is not equal to that taken over J1 . Call the vector that achieves the former quantity x, and call the vector that achieves the latter y. Our assumption implies that x1 < y1 . We have also assumed that wT x > wT y. Now, either 1. x + e1 ∈ J, or 2. x + e1 ± ek ∈ J. Take x out of the optimal solutions to be the one that minimizes y1 − x1 . In the first case, we have wT (x + e1 ) = wT x + w1 ≥ wT x, which yields a contradiction. In the second case, we have wT (x + e1 ± ek ) = wT x + w1 ± wk ≥ wT x, which again yields a contradiction. This completes the proof. Observe that since we first computed the absolute values of the wi ’s, the greedy algorithm described here does not correspond to the classical greedy algorithm to compute a maximum weight basis of a matroid. 16-3 4 Membership in Jump Systems The material in this section is almost exclusively due to Lovász. A paper covering this and much more is available at http://research.microsoft.com/users/lovasz/jump.ps. Suppose we are given a jump system J in some sort of implicit form. In this section, we take up the question of when we can determine whether some point x is in J. This specializes to many standard problems that we have already considered in this class. Example 3. Let G be a graph, and let JG be its set of degree sequences. Asking whether the vector (1, . . . , 1) ∈ JG is equivalent to asking whether there is some subgraph of G in which every vertex of G has degree exactly one. This is exactly the question of whether G admits a perfect matching. This can be generalized to the “factor problem”: Given a graph G = (V, E) and a function f : V → Z≥0 , does there exist a subgraph F ⊆ E such that df (v) = f (v) for all v? (It turns out that, using classical methods, one can reduce this problem to solving perfect matching, so this doesn’t really gain us too much generality.) Example 4. Let M1 and M2 be matroids, and let J1 and J2 be their respective jump systems of bases, as described in Example 1. Now let J = J1 − J2 . The question of whether 0 belongs to J is equivalent to asking whether M1 and M2 have a common basis. So it would be great if we could get a good general solution to the membership problem for jump systems. Unfortunately, this is going to turn out to be too much to ask for. As the next example will show, the membership problem includes matroid matching, which we established in an earlier lecture to be NP-hard. Example 5. Let M = (S, I) be a matroid, let E be a set of pairs of elements of S, let JM be the jump system of bases of M (as in Example 1), and let JG be the jump system of degree sequences of G = (S, E) (as in Example 2). Now, let J = JM − JG . Every vector in JM is a {0, 1}-vector of weight equal to the rank of M . Such a vector, when interpreted as an element of JG , corresponds to a matching of weight rk(M ). It thus follows that 0 ∈ J if and only if there is a matching in G of weight rk(M ) that is independent in M . Checking if 0 ∈ J is thus precisely equivalent to matroid matching, which, alas, is NP-hard. We therefore can’t hope to solve the membership problem in general. However, Lovász described a broad class of cases where we can solve it, which we will discuss here and in the next lecture. 4.1 The Beginnings of a Min-Max Relation It will be useful to generalize a little bit and consider the question of finding the closest element of a jump system to some box. Let J be a jump system, and let B = [a, b], a, b ∈ Zn , be a box. Now consider the quantity � |xi − yi |. d(J, B) = min d(x, y) = min x∈J,y∈B x∈J,y∈B i n If w ∈ {0, +1, −1} , then clearly d(J, B) ≥ min wT (x − y) = min wT x − max wT y. x∈J,y∈B x∈J y∈B (1) In some classes of systems, we will have equality in Equation (1), which will facilitate a solution to the membership problem. To state when this occurs, we will need some terminology. First, given a box B, let JB = {x ∈ J|d(x, B) = d(J, B)}. Theorem 1 (Lovász). JB is a jump system. 16-4 Now, we will define two sets, VB+ and VB− : VB+ = {i ∈ {1, . . . , n} | ∃x ∈ JB s.t. xi > bi }, VB− = {i ∈ {1, . . . , n} | ∃x ∈ JB s.t. xi < ai }. The main theorem, which we shall show in the next lecture, is: Theorem 2. If VB+ ∩ VB− = ∅, then we have equality in Equation (1). 16-5