MathCastle
Graph TheoryHardBipartite Graphs and Matchings

Bipartite Graphs and Matchings · Hard problem

Six tasks 1,…,61,\dots,6 need machines from {a,b,c,d,e,f}\{a,b,c,d,e,f\}: 11 and 22 can each use aa or bb; 33 and 44 can each use aa, bb, or cc; 55 can use dd or ee; 66 can use ee or ff. What is the maximum number of tasks that can run at the same time, one machine per task?