|Discrete Mathematics and Optimization Seminar
University of Tuebingen
Monday March 13th at 4.30pm
Title. The complexity of the bigamist matching problem.
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.