Assigning drivers to buses and routes We have a set of N chauffeurs, N buses and N routes, and there are some restrictions about which buses can drive each chauffeur, and which buses can be used in each route given in the form of a graph. For example, in the graph below the chauffeur $C_1$ can only drive bus $A_1$, and bus $A_1$ can be used in any of the three routes $R_i$. ![enter image description here]( The problem is to design an algorithm that identifies if a given graph is solvable or not. For example, the graph above is not solvable since $A_1$ cannot go to both $R_1$ and $R_2$ at the same time, and there is no other bus that goes to either route. Additionally, is the problem NP-complete? It looks like that to me, but right now I cannot think how to reduce 3SAT to this.

Since there is no direct restriction on which drivers can be on which routes, we can just solve two independent problems:

1. Which drivers are assigned to which buses.
2. Which buses are assigned to which routes.



Each problem is a separate instance of finding a perfect matching in a bipartite graph, which we know can be checked efficiently#In_unweighted_bipartite_graphs).

A more general problem, finding a 3-dimensional matching, _is_ NP-complete. But here, our restrictions are that we have a set of allowed triples of driver, bus, and route. For example, we could have a triple $(C_1,B_1,R_1)$ and $(C_2,B_1,R_2)$, saying that driver $C_1$ can drive bus $B_1$ on route $R_1$, or another driver $C_2$ can drive the same bus $B_1$ on route $R_2$. This is strictly more general, because we can allow these two triples without allowing the triple $(C_1, B_1, R_2)$: whether or not bus $B_1$ can drive on route $R_2$ in this version of the problem can depend on who is driving it.