-----Original Message----- From: math-fun-bounces+andy.latto=pobox.com@mailman.xmission.com [mailto:math-fun-bounces+andy.latto=pobox.com@mailman.xmission.com]On Behalf Of Thomas Colthurst Sent: Thursday, January 27, 2005 1:24 PM To: michael.kleber@gmail.com; math-fun@mailman.xmission.com Cc: thomasc@bbn.com Subject: [math-fun] Re: Marriage theorem generalization
Well, here's a reduction to what is hopefully a well-studied graph theory problem.
Add two special sets: S, which contains only the interval [0,0], and E, which contains only [n+1,n+1]. Now make a graph G with a vertex for every interval and an edge between two intervals iff (1) the union of the two intervals is itself an interval and (2) the two intervals come from different sets. Thus, if there were k sets of intervals in the beginning, G is (k+2)-partite graph. The problem now becomes: find a path in G from [0,0] in S to [n+1,n+1] in E that visits each part of G at most once.
As I said, I hope this is a well-studied problem, because all I know are bad solutions to it.
Well, it's a more difficult problem than finding Hamiltonian circuits in a graph, so it's NP-complete. Given a graph G with N vertices, you can construct a new graph G', with vertices in G X {1, 2,...,n} If G has an edge from x to y, then G' has an edge from {x, i} to {y, i+1} for all i. G' is n-partite, with projection to G giving the parts. Now G has a hamiltonian path starting at x and ending at y just if G' (an n-partite graph) has a path from {x, 1} to {y, n} that visits each part of G' at most once. So you've reduced what might be a hard problem, but might be an easy one, to a problem that's definitely hard. Andy Latto andy.latto@pobox.com