Friday, November 7, 2008
3:30 pm, MC 5158

Elliot Anshelevich
Rensselaer Polytechnic Institute

Terminal Backup, 3D Matching and Covering Cubic Graphs

We define a problem called Simplex Matching, and show that it is solvable in polynomial time. While Simplex Matching is interesting in its own right as a nontrivial extension of non-bipartite min-cost matching, its main value lies in many (seemingly very different) problems that can be solved using our algorithm. For example, suppose that we are given a graph with terminal nodes, non-terminal nodes, and edge costs. Then, the Terminal Backup problem, which consists of finding the cheapest forest connecting every terminal to at least one other terminal, is reducible to Simplex Matching. Simplex Matching is also useful for various tasks that involve forming groups of at least 2 members, such as project assignment and variants of facility location.
In an instance of Simplex Matching, we are given a hypergraph H with edge costs, and edge size at most 3. We show how to find the min-cost perfect matching of H efficiently, if the edge costs obey a simple and realistic inequality that we call the Simplex Condition. The algorithm we provide is relatively simple to understand and implement, but difficult to prove correct. In the process of this proof we show some powerful new results about covering cubic graphs with simple combinatorial objects.