Monday March 13th at 4.30pm

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.