Graph TheoryHardBipartite Graphs and Matchings
Bipartite Graphs and Matchings · Hard problem
A compatibility graph has workers and machines : workers are each compatible only with machine ; workers are each compatible with machine or machine ; worker is compatible with machine , , or . What is the minimum number of workers-or-machines needed to touch every listed compatibility in this -vertex network?