Representing Shift Eligibility
Suppose a set of workers must each be assigned one shift, and each shift can be assigned to at most one worker. A worker may be eligible for some shifts but not others. The key is to model eligibility separately from the assignment: an edge records that a pairing is allowed, while a matching selects pairings that do not conflict. This turns the question “Can everyone be assigned?” into a precise graph problem.
The graph is simple: an eligibility pair either is or is not allowed, so repeated edges are unnecessary. A matching enforces both assignment constraints at once. No worker appears twice because matching edges cannot share a worker endpoint, and no shift is assigned twice because they cannot share a shift endpoint.
“Maximum” and “maximal” have different meanings. A maximal matching cannot be enlarged just by adding a single edge; a maximum matching has the greatest possible size. A maximal matching need not be maximum, so merely finding an assignment to which no new worker–shift pair can be added does not settle whether more workers could be assigned by rearranging existing pairs.
If there are fewer shifts than workers, a complete assignment is impossible: each matching edge assigns at most one worker and uses a different shift, so a matching has size at most \(|S|\). When there are at least as many shifts as workers, a complete assignment still may fail because the eligibility edges can be concentrated on too few shifts. The matching, rather than the number of shifts alone, captures both availability and eligibility.
Improving an Assignment
Given a current matching \(M\), an alternating path is a path whose edges alternate between edges outside \(M\) and edges in \(M\). If its endpoints are unmatched by \(M\), it is an augmenting path. Starting at an unmatched worker, such a path alternates between an eligible shift not currently assigned to that worker and the worker currently assigned to that shift. Its final endpoint is a shift that is not currently assigned.
Proof. First suppose \(M\) has an augmenting path. The path has one more edge outside \(M\) than in \(M\), because it begins and ends with an edge outside \(M\). Remove the path’s edges that belong to \(M\), and add its other edges. Each internal vertex loses its one path-edge from \(M\) and gains one path-edge; each endpoint gains one edge and was previously unmatched. Edges of \(M\) away from the path are unchanged. The resulting set is therefore a matching, and its size is \(|M|+1\). Thus \(M\) was not maximum.
Conversely, suppose \(M\) is not maximum, and let \(N\) be a matching with \(|N|>|M|\). Consider the graph formed by the edges belonging to exactly one of \(M\) and \(N\). At each vertex there is at most one incident edge from each matching, so every vertex in this graph has degree at most two. Its components are paths, cycles, or isolated vertices; on every nontrivial component the edges alternate between \(M\) and \(N\). An alternating cycle has the same number of edges from each matching. An alternating path has either equal numbers or one more edge from one matching than the other. Since \(N\) has more edges overall, at least one path component has more \(N\)-edges than \(M\)-edges. That path starts and ends with \(N\)-edges. Its endpoints are unmatched by \(M\): an additional \(M\)-edge at an endpoint would either be in the component, contradicting that the path ends there, or belong to both matchings, contradicting that the endpoint is incident with an \(N\)-edge. The path is therefore an augmenting path for \(M\). This proves both directions. \(\square\)
This criterion justifies a practical search. From an unmatched worker, explore eligible edges not in the current matching; from a shift reached this way, follow its matching edge back to its assigned worker, if it has one. Continue until an unmatched shift is reached or no new vertices can be reached. In the first case, flip which edges on the resulting alternating path belong to the matching. Each successful search increases the matching size by one. If a search from all unmatched workers finds no augmenting path, the theorem says the current matching is maximum.
Worked Example: Reassigning Workers to Complete an Assignment
Let the workers be \(W=\{A,B,C\}\), the shifts be \(S=\{1,2,3\}\), and the eligibility edges be \(E=\{A1,A2,B1,C2,C3\}\). Begin by processing workers \(A\), \(B\), and \(C\) in that order. The search below uses a queue: from a worker it examines eligible shifts, and from a matched shift it returns to its assigned worker.
| Search | Queue and exploration | Augmenting path and new matching |
|---|---|---|
| Start with \(A\) | Queue \([A]\); \(A\) is eligible for shift \(1\), which is free. | Path \(A-1\); \(M=\{A1\}\). |
| Then \(B\) | Queue \([B]\); \(B\) reaches shift \(1\), matched to \(A\). Queue becomes \([A]\). From \(A\), shift \(2\) is free. | Path \(B-1-A-2\); flip its edges to obtain \(M=\{B1,A2\}\). |
| Then \(C\) | Queue \([C]\); \(C\) reaches shift \(2\), matched to \(A\), so the queue becomes \([A]\). Shift \(3\) is free. | Path \(C-3\); \(M=\{B1,A2,C3\}\). |
The second search makes the important change: instead of declaring failure because shift \(1\) is already assigned, it moves \(A\) to shift \(2\) and assigns shift \(1\) to \(B\). At the end, \(A\) has shift \(2\), \(B\) has shift \(1\), and \(C\) has shift \(3\). Each pair is an edge of \(E\), and the three chosen edges have distinct endpoints, so this is a complete assignment.
Check: the matching has three edges, one for each of the three workers. Since no matching can have more edges than there are workers, its size is maximum. Directly checking the eligibility list confirms \(A2,B1,C3\in E\).
Certifying That an Assignment Is Largest
Finding a matching of size \(k\) proves that at least \(k\) workers can be assigned. To prove that no larger assignment exists, it helps to identify a vertex cover: a set of vertices containing at least one endpoint of every edge. Any matching has at most as many edges as any vertex cover. Indeed, every matching edge must meet the cover, and distinct matching edges cannot use the same covering vertex. A cover of size \(k\) therefore certifies that every matching has size at most \(k\). If a matching and a cover have the same size, that matching is maximum.
Worked Example: A Bottleneck Prevents a Complete Assignment
Let \(W=\{A,B,C\}\), \(S=\{1,2,3\}\), and \(E=\{A1,A2,B1,B2,C1\}\). Although there are three shifts for three workers, the eligibility edges show that no worker is eligible for shift \(3\), and all three workers have eligibility confined to shifts \(1\) and \(2\).
The set \(M=\{A2,B1\}\) is a matching, so two workers can be assigned. The set \(U=\{1,2\}\) is a vertex cover: every edge in \(E\) has shift endpoint \(1\) or \(2\). Thus every matching has at most \(|U|=2\) edges. Since \(|M|=2\), \(M\) is maximum, and no complete assignment exists.
Check: the upper bound comes from the two cover vertices, not from the total number of shifts. The two matching edges \(A2\) and \(B1\) meet the cover at different shifts, confirming that the bound of two is attained. Worker \(C\) remains unassigned in this maximum matching.
Proof. Let \(M\) be a matching and \(U\) a vertex cover. Each edge of \(M\) contains a vertex of \(U\), since \(U\) meets every edge. Two different edges of \(M\) cannot be accounted for by the same vertex of \(U\), since matching edges have no shared endpoints. Hence \(|M|\leq |U|\). If equality holds, no matching can be larger than \(M\), so \(M\) is maximum. If the common size is less than \(|W|\), a matching cannot assign every worker, because a complete assignment requires one distinct matching edge for each worker. \(\square\)
Checking a Proposed Roster
Worked Example: Verifying an Assignment Against Eligibility
Let \(W=\{\text{Liam},\text{Mia},\text{Noah}\}\), \(S=\{\text{Early},\text{Late},\text{Overnight}\}\), and let \(E=\{\text{Liam-Early},\text{Liam-Late},\text{Mia-Early},\text{Mia-Overnight},\text{Noah-Late},\text{Noah-Overnight}\}\). A proposed roster is Liam–Early, Mia–Overnight, Noah–Late.
Check eligibility pair by pair: Liam–Early is in \(E\), Mia–Overnight is in \(E\), and Noah–Late is in \(E\). The workers are distinct, so no worker is assigned twice. The shifts Early, Overnight, and Late are also distinct, so no shift is assigned to two workers. The three proposed edges therefore form a matching that is complete for \(W\).
Check: the matching has size three, equal to \(|W|=3\), so it assigns every worker. In fact, all three shifts are used exactly once; the roster satisfies both eligibility and the one-worker-per-shift rule.
Common Pitfall: Greedy Choices Can Block a Better Roster
Consider \(W=\{A,B\}\), \(S=\{1,2\}\), and \(E=\{A1,A2,B1\}\). A greedy choice that first assigns \(A\) to shift \(1\) leaves \(B\) without an available shift. The matching \(\{A1\}\) is maximal: no edge can simply be added to it, because \(B1\) shares shift \(1\) and \(A2\) shares worker \(A\). But it is not maximum. Reassigning \(A\) to shift \(2\) gives \(\{A2,B1\}\), a matching of size two and a complete assignment.
The error is to treat “no eligible edge can be added without changing anything” as proof that an assignment is as large as possible. An augmenting path accounts for the possibility of changing earlier choices. For a successful assignment, check that every selected pair is eligible and that no endpoints are repeated. For an impossibility claim, either show that the maximum matching is smaller than the number of workers or give an upper-bound certificate such as a vertex cover.
Check Your Understanding
Use the bipartite-graph model and the results in this tutorial to answer the following.
- For \(W=\{A,B\}\), \(S=\{1,2\}\), and \(E=\{A1,A2,B1\}\), give an augmenting path from the matching \(\{A1\}\).
- Give a vertex cover of size two for the graph with \(W=\{A,B,C\}\), \(S=\{1,2,3\}\), and \(E=\{A1,A2,B1,B2,C1\}\). What does it imply about complete assignments?
- Explain why a matching of size \(|W|\) is a complete assignment for the workers.
- Give an example in which a maximal matching is not maximum, and identify the larger matching.
- Why does an augmenting path increase the size of a matching by exactly one?