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 ouralgorithm. 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 two members, such as project assignment and variants of facility location.

Authors

• Elliot Anshelevich
• Adriana Karagiozova

Keywords

• terminal backup
• simplex matching
• polynomial time