MathCastle
Graph TheoryHardBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Hard problem

A compatibility graph has workers 1,2,3,4,5,61,2,3,4,5,6 and machines a,b,c,d,e,fa,b,c,d,e,f: workers 1,2,31,2,3 are each compatible only with machine aa; workers 4,54,5 are each compatible with machine bb or machine cc; worker 66 is compatible with machine dd, ee, or ff. What is the minimum number of workers-or-machines needed to touch every listed compatibility in this 1212-vertex network?