Tag Archives: SP11

3-Matroid Intersection

This is a problem that was really hard for me to understand and explain.  It may be less so or other people, though.

The problem: 3-Matroid Intersection.  This is problem SP11 in the appendix.

The description: Given three matroids (E,F1), (E, F2), (E,F3), and a positive integer K.  Can we find a subset E’ of E with K elements that is in the intersection of F1, F2, and F3?

A matroid (E,F) is a set of elements E, and a family F of subsets of E with the following properties:

  • Some set S in the family F implies that all subsets of S are also in F.
  • If I have two sets S and S’ in F, and |S| = |S’|+1, then there is some element e that is in S but not S’, and adding e to S’ gets us a set also in F.

A common example of matroids comes from graph theory: Given a graph G=(V,E), the matroid based on this graph is (E,F), where E is the set of edges in the graph, and F is the collection of edges that have no cycles (i.e, forests)  This follows the two rules above:

  • If S is a collection of edges that do not form a cycle, then any subset of S is also a collection of edges that do not form a cycle.
  • If I have two collections of edges S and S’, and S is larger than S’ by one element, we need to find an edge in S that connects two connected components  (trees in the forest) in S’.  Since each tree on K vertices has exactly K-1 edges, S has at least one edge that is not part of any tree in S’ (adding an edge to a tree causes a cycle).  That edge must either connect two trees together, or connect a vertex in some tree to a vertex not used in S’, or connect two vertices not used in S’.  Either way, adding this edge to S’ gives us another forest.

Example:  Since the reduction we’re going to use involves building three matroids from a basic graph, let’s do that.  Here is a graph:

3matroidintersection1

We’re going to use this graph to induce 3 matroids.  The first will be the graph matroid (using the rules defined above) on the undirected version of this graph:

3matroidintersection2

So F1 is the set of all forests in the above graph.

F2 is collections of sets of edges in the directed graph where each vertex has at most one incoming edge.  So, sets like {(s,a), (a,t)} or {(a,b), (b,c), (c,t)}.  The exception is that vertex s must have zero incoming edges in any set in the family.

F3 is built similarly, except we count outgoing edges, and t (instead of s) is the vertex restricted to have 0 outgoing edges.

If K=4, then the following set of edges is in all three families: {(s,a}, (a,b), (b,c), (c,t)}.  It’s acyclic, so it’s in F1.  No vertex in that set has indegree or outdegree of more than 1 (and s has indegree 0 and t has outdegree o), so it’s in F2 and F3.

Just to clarify, because it’s confusing to me.  The sets E that are the “elements” of the matroid are edges in the graph, and the families F are collections of edges.  We just found a collection of 4 edges that will be in all three families.

The reduction: G&J don’t give a reference to this problem, but suggest using 3DM. In my searches, I found that Wikipedia and this set of lecture notes from MIT both want to use Hamiltonian path between two vertices.   (Notice that the “corrected” reduction for HP actually specifies the two vertices to connect between, so the HP reduction also proves this variant).  Here is my explanation of the reduction in the MIT lecture notes.  The class was taught by Michael Goemans, and I got the notes from his web site.

So, we start with an instance of HP- a possibly directed graph G=(V,E), and two special vertices s and t that we want to see if there is a Hamiltonian Path between.  We build the three matroids described in the examples based on using the edge set E: One based on forests in E, one based on collections of edges that have indegree at most 1 on each vertex, and one based on collections of edges that have outdegree at most 1 on each vertex.  Set K = |V|-1.

Notice that an intersection of these three matroids has to be a collection of paths that do not encounter the same vertex twice.  If we can create a collection that has K edges in it, the path will start at s (because F2 ensures that no edges going into s will be part of the intersection), encounter each vertex once (because F1 ensures that we have no cycles, and thus hit each vertex at most once), and end at t (because F3 ensures that no edges leaving t will be part of the intersection).  Thus, we have an intersection of K edges if and only if V has a Hamiltonian cycle.

Difficulty: It’s an 8 for me.  Since this is taught in a relatively small part of one lecture of a class (yes, a class at MIT, but still just a class), presumably it may be less for other people.  But I have a lot of trouble thinking in terms of matroids, and even now, I’m not really convinced that the three families of edges we create are polynomial in size.