Discrete Mathematics and Optimization Seminar

Klaus Reinhardt
University of Tuebingen
Monday March 13th at 4.30pm
Burnside 1205

Title. The complexity of the bigamist matching problem.

Abstract. We describe a polynomial time algorithm to construct a maximal bigamist matching for a given bipartite graph, that is the maximal set of
vertex disjoint triples consisting of one bigamist vertex and two monogamist vertices. This solves an open problem of Sharan et al. As a method we
use a "double reachability" algorithm to find a simple path in a switch graph, which is equivalent to finding an augmenting path for the
bigamist matchings. Furthermore, we show that some other problems of this kind are NP-complete.