<p>This can be easily implemented in ILP.</p>
<p>For each person <span class="math-container">$p$</span> and slot <span class="math-container">$s$</span> define binary variable <span class="math-container">$a^p_s$</span> indicating whether the person is assigned to the slot or not. Obviously, for unavailable slots we have <span class="math-container">$a^p_s=0$</span>. To make sure person is assigned to one slot only we have <span class="math-container">$a^p_1 + a^p_2 + \ldots + a^p_s = 1$</span>.</p>
<p>To make sure even number of people is assigned to a slot, we introduce variable <span class="math-container">$e_s$</span> for which we set <span class="math-container">$2 \cdot e_s = a^1_s + a^2_s + \ldots + a^p_s$</span></p>

CC BY-SA 4.0
2021-06-24T19:10:46.747Z
And both general ILP and binary-only ILP is also NP-complete. Convincing enough for me, thanks.
ScratchyCzyn
CC BY-SA 4.0
2021-06-24T19:46:12.140Z
This does not answer the question that was asked -- it does not provide any information about whether the problem is NP-hard.
D.W.
CC BY-SA 4.0
2021-06-23T18:04:05.660Z
2021-06-23T18:04:05.660Z
user1543037
<p>I have the following problem, which I intuitively expect to be NP-hard but cannot see how to write a reduction for:</p>
<p>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.</p>
<p>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.</p>
<p>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. <code>((person_1_10-11 ∧ person_2_10-11) ∨ (person_1_10-11 ∧ person_3_10-11) ∨ (person_2_10-11 ∧ person_3_10-11) ∨ ...)</code>. A reduction to a different problem or form, much more concisely, seems probably possible, but I cannot find it.</p>
<p>This looks similar to <a href="https://cstheory.stackexchange.com/questions/12497/is-meeting-room-planning-np-complete">a prior question about meeting room scheduling</a>, 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.</p>

CC BY-SA 4.0
2021-06-23T06:58:59.943Z
This is b-matching with even/odd constraints. It is solvable in polynomial time.
Chao Xu
CC BY-SA 4.0
2021-06-23T17:48:49.023Z
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.
ScratchyCzyn
CC BY-SA 4.0
2021-06-23T19:45:54.970Z
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.
D.W.
CC BY-SA 4.0
2021-06-24T16:57:59.540Z
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.
Chao Xu
CC BY-SA 4.0
2021-06-24T18:51:16.083Z
@D.W. The question is in the title. The description is elaboration on that question.
ScratchyCzyn
CC BY-SA 4.0
2021-06-24T19:45:55.973Z
Please make sure that the body of your post contains the title you want answered.
D.W.
<cc.complexity-theory><np-hardness><scheduling>
Is time-slot matchmaking NP-hard?
ScratchyCzyn
# Is time-slot matchmaking NP-hard?

(Asked by: username_0 on 2021-06-23)

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](https://cstheory.stackexchange.com/questions/12497/is-meeting-room-planning-np-complete), 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.

**Tags:** cc.complexity-theory, np-hardness, scheduling
> **Comments:**
> **username_1**: This is b-matching with even/odd constraints. It is solvable in polynomial time.  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_1**: 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.  
> **username_0**: @D.W. The question is in the title. The description is elaboration on that question.  
> **username_2**: Please make sure that the body of your post contains the title you want answered.  

---

## 1 answers

### Answer by username_3 on 2021-06-23. Score: 0 | Accepted answer

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$

> **Comments:**
> **username_0**: And both general ILP and binary-only ILP is also NP-complete. Convincing enough for me, thanks.  
> **username_2**: This does not answer the question that was asked -- it does not provide any information about whether the problem is NP-hard.  

---

