-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.

Improve this question
$\endgroup$
6
  • $\begingroup$ This is b-matching with even/odd constraints. It is solvable in polynomial time. $\endgroup$
    – Chao Xu
    Jun 23, 2021 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$
    – ScratchyCzyn
    Jun 23, 2021 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, 2021 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, 2021 at 16:57
  • $\begingroup$ @D.W. The question is in the title. The description is elaboration on that question. $\endgroup$
    – ScratchyCzyn
    Jun 24, 2021 at 18:51

1 Answer 1

Reset to default
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$

Improve this answer
$\endgroup$
2
  • $\begingroup$ And both general ILP and binary-only ILP is also NP-complete. Convincing enough for me, thanks. $\endgroup$
    – ScratchyCzyn
    Jun 24, 2021 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, 2021 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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