Graph TheoryHardBipartite Graphs and Matchings
Bipartite Graphs and Matchings · Hard problem
A network splits into two separate pieces. In the first piece, workers can each be assigned only to task or task . In the second piece, stations are wired in a -cycle , 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?