<p>Here's a reduction from 3SAT. For each of your 3SAT variables <span class="math-container">$x_0$</span>, imagine there is one event <span class="math-container">$x_0$</span> and two rooms called "Room <span class="math-container">$x_0$</span> is true" and "Room <span class="math-container">$x_0$</span> is false". The event <span class="math-container">$x_0$</span> has to be in one of those two rooms. Whichever statement is true, that's the room we <em>don't</em> use. And it is going to take all day. So the only rooms generally available for other events are the rooms named with a true statement.</p>

<p>Now let's say you want to add a condition - <span class="math-container">$x_0$</span> OR <span class="math-container">$x_1$</span> OR NOT <span class="math-container">$x_2$</span>. Make that into an event that's just one nanosecond long, at a random time so it doesn't conflict with the other condition-events. And it has to be held in one of "Room <span class="math-container">$x_0$</span> is true", "Room <span class="math-container">$x_1$</span> is true", or "Room <span class="math-container">$x_2$</span> is false".</p>

<p>Now solving your event assignment problem lets you solve an arbitrary 3SAT problem.</p>

CC BY-SA 4.0
2020-04-19T09:37:38.190Z
Yes. That does, in fact, work, huh. I somehow didn't consider reducing directly from 3-SAT. Thanks!
Theemathas Chirananthavat
CC BY-SA 4.0
2020-04-20T22:07:06.827Z
Your answer starts by "Here's a reduction to 3SAT", but you mean a reduction *from* 3SAT, right?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2020-04-22T19:00:09.033Z
I guess so - I always get the two confused. I edited the answer. It's the direction that proves this scheduling problem is hard :P
lacker
CC BY-SA 4.0
2020-04-18T19:02:38.460Z
2020-04-22T18:59:11.400Z
2020-04-22T18:59:11.400Z
lacker
<p>The interval partitioning problem can be solved <a href="https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/04GreedyAlgorithms-2x2.pdf" rel="nofollow noreferrer">efficiently using a greedy algorithm</a>. However, adding restrictions on the interval assignment to the problem results in a problem that appears harder. Here's my problem formulation:</p>

<ul>
<li>There are <span class="math-container">$n$</span> rooms. We want to hold <span class="math-container">$m$</span> events in these rooms. These events have fixed (given as input) starting times <span class="math-container">$s_1,\dots,s_m$</span> and finishing times <span class="math-container">$f_1,\dots,f_m$</span>.</li>
<li>Each event must be held in exactly one room, and two events cannot be held in the same room at the same time.</li>
<li>Certain events can be held in only certain rooms. This is given as an input as an <span class="math-container">$n$</span> by <span class="math-container">$m$</span> matrix of booleans.</li>
<li>We want to figure out whether all events can be held in these rooms.</li>
</ul>

<p>It seems to me that a greedy algorithm can't solve this. Additionally, since bipartite matching is a special case of this problem (when all events are held at the same time), I have attempted to transform this "interval partitioning with restrictions" problem into a maximum flow problem, with no success. I have also considered trying to prove that this problem is NP-complete, but I don't know where to start.</p>

<p>Could anybody help me either find an efficient algorithm for this or prove that it is NP-complete?</p>

CC BY-SA 4.0
2020-04-18T09:52:38.237Z
@MarzioDeBiasi I don't see how the reduction from the [3-partition problem](https://en.wikipedia.org/wiki/3-partition_problem) to this problem could be possible. That problem deals with sums of integers, but my problem doesn't have any summing. Could you give me some directions?
Theemathas Chirananthavat
CC BY-SA 4.0
2020-04-18T23:04:17.300Z
sorry, I read the question too quickly and didn't notice the "fixed starting time"; there is no direct/quick reduction to 3-PARTITION ! ... I'll think if there is a quick reduction to another problem later.
Marzio De Biasi
CC BY-SA 4.0
2020-04-27T22:04:24.407Z
@NealYoung: of course, forget my quick fart-like comment (I'll delete it ;-). Lacker's reduction is elegant and correct (so I didn't spend more time on the problem)
Marzio De Biasi
<ds.algorithms><np-hardness><max-flow-min-cut><greedy-algorithms>
Interval partitioning with restrictions: NP-complete or efficiently solvable?
Theemathas Chirananthavat
# Interval partitioning with restrictions: NP-complete or efficiently solvable?

(Asked by: username_0 on 2020-04-18)

The interval partitioning problem can be solved [efficiently using a greedy algorithm](https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/04GreedyAlgorithms-2x2.pdf). However, adding restrictions on the interval assignment to the problem results in a problem that appears harder. Here's my problem formulation:

* There are $n$ rooms. We want to hold $m$ events in these rooms. These events have fixed (given as input) starting times $s\_1,\dots,s\_m$ and finishing times $f\_1,\dots,f\_m$.
* Each event must be held in exactly one room, and two events cannot be held in the same room at the same time.
* Certain events can be held in only certain rooms. This is given as an input as an $n$ by $m$ matrix of booleans.
* We want to figure out whether all events can be held in these rooms.

It seems to me that a greedy algorithm can't solve this. Additionally, since bipartite matching is a special case of this problem (when all events are held at the same time), I have attempted to transform this "interval partitioning with restrictions" problem into a maximum flow problem, with no success. I have also considered trying to prove that this problem is NP-complete, but I don't know where to start.

Could anybody help me either find an efficient algorithm for this or prove that it is NP-complete?

**Tags:** ds.algorithms, np-hardness, max-flow-min-cut, greedy-algorithms
> **Comments:**
> **username_0**: @MarzioDeBiasi I don't see how the reduction from the [3-partition problem](https://en.wikipedia.org/wiki/3-partition_problem) to this problem could be possible. That problem deals with sums of integers, but my problem doesn't have any summing. Could you give me some directions?  
> **username_1**: sorry, I read the question too quickly and didn't notice the "fixed starting time"; there is no direct/quick reduction to 3-PARTITION ! ... I'll think if there is a quick reduction to another problem later.  
> **username_1**: @NealYoung: of course, forget my quick fart-like comment (I'll delete it ;-). Lacker's reduction is elegant and correct (so I didn't spend more time on the problem)  

---

## 1 answers

### Answer by username_2 on 2020-04-18. Score: 3 | Accepted answer

Here's a reduction from 3SAT. For each of your 3SAT variables $x\_0$, imagine there is one event $x\_0$ and two rooms called "Room $x\_0$ is true" and "Room $x\_0$ is false". The event $x\_0$ has to be in one of those two rooms. Whichever statement is true, that's the room we *don't* use. And it is going to take all day. So the only rooms generally available for other events are the rooms named with a true statement.

Now let's say you want to add a condition - $x\_0$ OR $x\_1$ OR NOT $x\_2$. Make that into an event that's just one nanosecond long, at a random time so it doesn't conflict with the other condition-events. And it has to be held in one of "Room $x\_0$ is true", "Room $x\_1$ is true", or "Room $x\_2$ is false".

Now solving your event assignment problem lets you solve an arbitrary 3SAT problem.

> **Comments:**
> **username_0**: Yes. That does, in fact, work, huh. I somehow didn't consider reducing directly from 3-SAT. Thanks!  
> **username_3**: Your answer starts by "Here's a reduction to 3SAT", but you mean a reduction *from* 3SAT, right?  
> **username_2**: I guess so - I always get the two confused. I edited the answer. It's the direction that proves this scheduling problem is hard :P  

---

