Is time-slot matchmaking NP-hard?

Question

I have the following problem, which I intuitively expect to be NP-hard but cannot see how to write a reduction for:

Givens: There is a fixed set of time slots, e.g. {9-10, 10-11, 11-12, 12-1, etc.}. There are N people, for each of whom is given a list of which of those time slots is available for them.

Problem: Find an assignment of people to slots such that each person is assigned to a time slot they have marked as available (and only to one), and each time slot has an even number of people assigned to it.

This can be formulated as a Boolean satisfiability problem, but naively writing in in that way requires the Boolean expression's length to be exponential in N, e.g. ((person_1_10-11 ∧ person_2_10-11) ∨ (person_1_10-11 ∧ person_3_10-11) ∨ (person_2_10-11 ∧ person_3_10-11) ∨ ...). A reduction to a different problem or form, much more concisely, seems probably possible, but I cannot find it.

This looks similar to a prior question about meeting room scheduling, but has both constraints not present there (one 'meeting' per person) and looser versions of constraints present there ('meetings' do not have maximum capacity), so its answers are inapplicable.

Answer 1

This can be easily implemented in ILP.

For each person $p$ and slot $s$ define binary variable $a^p_s$ indicating whether the person is assigned to the slot or not. Obviously, for unavailable slots we have $a^p_s=0$. To make sure person is assigned to one slot only we have $a^p_1 + a^p_2 + \ldots + a^p_s = 1$.

To make sure even number of people is assigned to a slot, we introduce variable $e_s$ for which we set $2 \cdot e_s = a^1_s + a^2_s + \ldots + a^p_s$