MathCastle
Graph TheoryHardBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Hard problem

A network splits into two separate pieces. In the first piece, workers p1,p2,p3p_1,p_2,p_3 can each be assigned only to task xx or task yy. In the second piece, stations q1,r1,q2,r2q_1,r_1,q_2,r_2 are wired in a 44-cycle q1-r1-q2-r2-q1q_1\text{-}r_1\text{-}q_2\text{-}r_2\text{-}q_1, and a "cover" there means a set of stations touching every wire. What is the minimum total number of tasks, workers, and/or stations needed so that every worker-task pairing in the first piece AND every wire in the second piece is touched by the chosen set?