Graph theory: Job assignment

Question

I'm struggling to solve this problem.

Jack has to assign jobs to job students. There are 25 job students and 25 jobs that must be assigned. Every student is suited for a minimum of 4 jobs, but every job can be executed by a maximum of 4 job students. Can Jack give every job student a job for which he is suited?

I translated this problem to graphs:

Consider a bipartite graph $G = (V_1 \cup V_2, E)$ where $V_1$ are the job students and $V_2$ the jobs. I drawed this graph so there are 25 vertices left and 25 right. It's clear that in every vertex of $V_1$ (left), 4 edges can leave. It's also clear that in every vertex of $V_2$ (right), 4 edges can arrive.

How do I get started? Do I have to find a maximum assignment?

Thanks in advance.

EDIT: I figured out I should apply Hall's theorem to find an assignment from $V_1$ to $V_2$.

Answer 1

As stated in the comment use Hall's Theorem stating in your case:

If for every subset $W$ of students the set $N(W)$ of jobs which can be assigned to any of those students in $W$ holds $|W| \leq |N(W)|$, then there is a proper matching.

To see this just count the edges:

The edges $E$ leaving $W$ equals the edges arriving in $N(W)$. As you stated $|E| \geq 4 |W|$ since every student has at least 4 suitable jobs (hence produces at least 4 edges) and $|E|\leq 4 N(W)$ since every job is suitable for at most 4 students. As you can now easily see the wanted inequality holds for every subset of students and applying Hall's Theorem we are done.

You can now even see, that every student is suitable for exactly 4 jobs and every job is suitable for exactly 4 students, but that is just some sweet byproduct ;-)

Answer 2

Here is a translation to an integer linear program:

We have a suitability matrix $$ S = (s_{ij}) \in \{0,1\}^{25\times 25} \\ $$ which models if student $i$ is suitable for job $j$.

And we have an assignment matrix $$ A = (a_{ij}) = (a_1, \dotsc, a_{25}) \in \{0,1\}^{25\times 25} $$ which models if student $i$ is assigned to job $j$.

The constraints "suitable for at least $4$ jobs" and "assigned to not more than $4$ students" then mean $$ w(s_i^\top) \ge 4 \quad (I) \\ w(a_j) \le 4 \quad (II) $$ where $$ w(u) = \sum_i u_i $$ The suitability and assignment matrices are related like this: $$ A \le S \quad (III) $$ which is meant to hold element wise: $a_{ij} \le s_{ij}$.

A feasible solution must fulfill that every student gets at least one suitable job assigned: $$ w(a_i^\top) \ge 1 \quad (IV) $$

If we flatten $A$ into a vector of unknowns $$ x = (a_1^\top, \dotsc, a_{25}^\top)^\top \in \{0,1\}^{625} $$ we can formulate this as ILP $$ \max_x \{ 0^\top x \mid M x \le b \} \quad (\#) $$ where $M$ and $b$ are derived from the constraints $(II)$, $(III)$ and $(IV)$.

The problem is now to show that the constraints $(I)$ lead to such $M$ and $b$ that $(\#)$ has feasible solutions.