-2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ This is b-matching with even/odd constraints. It is solvable in polynomial time. $\endgroup$
    – Chao Xu
    Jun 23 at 6:58
  • $\begingroup$ AFAICT b-matching includes fixed constraints on the vertices, which is not true for the vertices corresponding to timeslots. It is not obvious that the looser constraint makes the problem easier and so it is not obvious that this is in P. $\endgroup$ Jun 23 at 17:48
  • $\begingroup$ What's your question? I don't see a question here. We are a question-and-answer site, so we require you to articulate a specific question. $\endgroup$
    – D.W.
    Jun 23 at 19:45
  • $\begingroup$ Depends on the definition, b-matching can be on vertex v, at most b(v) edges incident to it. Just set b(v) on time slot= Number of people. $\endgroup$
    – Chao Xu
    Jun 24 at 16:57
  • $\begingroup$ @D.W. The question is in the title. The description is elaboration on that question. $\endgroup$ Jun 24 at 18:51
0
$\begingroup$

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$

$\endgroup$
2
  • $\begingroup$ And both general ILP and binary-only ILP is also NP-complete. Convincing enough for me, thanks. $\endgroup$ Jun 24 at 19:10
  • $\begingroup$ This does not answer the question that was asked -- it does not provide any information about whether the problem is NP-hard. $\endgroup$
    – D.W.
    Jun 24 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.