Tag Archives: Hamiltonian Path

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.

Protected: Kth Shortest Path

This content is password protected. To view it please enter your password below:

Protected: Isomorphic Spanning Tree

This content is password protected. To view it please enter your password below:

Protected: Maximum Leaf Spanning Tree, Connected Dominating Set

This content is password protected. To view it please enter your password below:

Protected: Degree Constrained Spanning Tree

This content is password protected. To view it please enter your password below:

Protected: Hamiltonian Completion

This content is password protected. To view it please enter your password below:

Protected: Hamiltonian Path on Bipartite Graphs

This content is password protected. To view it please enter your password below:

Protected: Degree-Bounded Connected Subgraph

This content is password protected. To view it please enter your password below:

Protected: Longest Path

This content is password protected. To view it please enter your password below:

Hamiltonian Path

Before I start doing my own problems where G&J don’t give proofs, here’s a really simple extension of Hamiltonian Circuit that will be useful.

The problem: Hamiltonian Path

The description: Given a graph G=(V,E), where |V| = N.  Can I create an ordering <v1, v2…vn>of the vertices where an edge exists between each (vi, vi+1) in the sequence?

(This is the Hamiltonian Circuit problem without the restriction that I return to the start)

EDIT 4/24/15.  My original reduction doesn’t work.  I’ve left it below.  Thanks to Fernando Berzal for pointing it out to me.  I’ve added his answer, which looks correct.

In all honesty, the best part about being wrong is that it means people actually read these things!

The new Reduction: From HC.  Given a graph G =(V,E), an instance of HC, pick any vertex v.

We’re going to build a graph G’ =(V’, E’)

V’ = All of the vertices in V, plus a new vertex v’ (which is a “copy” of v)

E’ = All of the edges in E, plus an edge (v’, w) if there was an edge (v,w) in E.

So, G’ is G, with one vertex (v) “duplicated” as v’.  v’ has edges to all of the places v has.

We want to see if there’s an HP from v to v’.

If G’ has an HP from v to v’, then the last edge in the path goes from some vertex u to v’.  If we replace that edge with the edge (u,v) we get a HC in G.

If G has an HC, then we can follow that cycle starting from v.  Instead of the last edge coming back to v, follow it to v’.  This will give us a HP in G’

My reduction that doesn’t work: From HC.  Given a graph GHC, an instance of HC, we build GHP to be the exact same graph with 2 vertices added- vstart and vend. We add two edges, one from vstart to some vertex in GHC, and one from vend to the same vertex in GHC.  The idea is that a Hamiltonian path in this graph would start at vstart, travel through the HC in the given graph (if it exists), and end at vend.

This doesn’t work because if the two new vertices both connect to the same vertex then we hit it twice in our HP, which breaks the rules.

Difficulty: 2.  This is a good “simple reduction” for students to work on.  I don’t use it because it’s just a variant on the same problem, and I like to drive home how reductions tie very different-looking problems together.  But I do like how it’s simple, but does make you make some changes to the original problem.

(I think that I’m going to upgrade this difficulty to 4 now, since I can see a lot of students making the same mistake I did)