## Help me prove (or disprove) the following problem NP-hard

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Derek
Posts: 2180
Joined: Wed Aug 18, 2010 4:15 am UTC

### Help me prove (or disprove) the following problem NP-hard

This came up when I was thinking about something in a video game (Starcraft 2 to be exact), but I've modified the description to be simpler to understand.

Given a set of jobs that each have a fixed start and end time (a, b), and a set of workers that each have a shift during which they are available to work (x, y), find a valid assignment of jobs to workers such that all jobs are completed and a worker never has two jobs at the same time. For a worker to perform a job the job must be entirely within the worker's shift. Jobs cannot be performed at times other than what is given, they cannot be paused and resumed later, nor can they be handed off to a different worker.

Examples:

Jobs:
j1=(1, 3)
j2=(4, 6)

Workers:
w1=(0, 6)

Solution:
w1={j1, j2}

Jobs:
j1=(1, 3)
j2=(2, 4)

Workers:
w1=(0, 5)

No valid solution (only one worker but the two jobs overlap)

Jobs:
j1=(1, 3)
j2=(2, 4)

Workers:
w1=(0, 5)
w2=(2, 6)

Solution:
w1={j1}
w2={j2}

Jobs:
j1=(0, 3)
j2=(1, 4)
j3=(2, 5)
j4=(3, 6)
j5=(4, 6)
j6=(5, 7)

Workers:
w1=(0, 7)
w2=(1, 7)
w3=(2, 6)

No valid solution. This is the simplest non-trivial example of no solution I could come up with, where it can't be shown just by comparing the number of workers to the number of jobs at any single time. But j1 can only be assigned to w1, which forces j2 to be assigned to w2, forcing j3 to be assigned to w3, then j4 must be assigned to w1, j5 to w2, then finally only w3 is available, but j6 cannot be assigned because it is outside of their shift.

So far I have shown that the problem can be reduced to graph coloring: The jobs are vertices, and two jobs have an edge if they are in conflict with each other (overlapping times). Workers correspond to colors, and worker shifts can be encoded by adding an extra vertex of the worker's color with an edge going to each job outside of their shift, ensuring that those vertices cannot have that worker's color. However, this reduction goes the opposite direction of what I need. What I need is to show that some NP-hard problem can be encoded in my problem. I feel like graph coloring or some kind of set cover will have the most promise, but I haven't been able to get it yet. I also looked for other NP-hard problems that might be similar to mine, but did not find any that were obviously so.

Tub
Posts: 421
Joined: Wed Jul 27, 2011 3:13 pm UTC

### Re: Help me prove (or disprove) the following problem NP-hard

Your reduction is invalid - you cannot "add a vertex of the worker's color"; the coloring problem starts with an entirely uncolored graph. We don't know the complexity of your variant of the coloring problem - adding constraints can both increase or decrease the complexity.

Doesn't matter though, because your problem is obviously in NP: a solution can be verified in linear time. A reduction to an NP-complete problem tells us nothing new.

You can prove it to be NP-hard by reducing a NP-complete problem to yours, but your problem seems way too flimsy for that. No matter which problem I try to reduce, I end up unable to encode all the constraints I need.

Disproving a problem NP-hard implies proving P != NP, and I'm not going to help you with that. I suspect you'd be happy just finding a polytime algorithm. At first glance, there's up to w!/(w-j)! ways to assign j jobs to w workers, which is too much.

Let's do the following steps. Each step should run in polytime of (w+j), and neither step should change the solvability of the instance:

Step 1) deobfuscate the time axis
- relabel all timestamps as integers 0..i without changing any order; let's call our time unit "ticks".
- remove any intervals where no jobs are active
- for each worker, increase their shift's start to the start of the first job they could do; decrease their shift's end to the end of the last job they could do. If they can't do any jobs, remove them.
- Shorten any intervals where nothing changes to 1 tick.
Step 2) check for trivial rejections
- if the sum of all job lengths is larger then the sum of all shift lengths, halt.
- If at any time there are more jobs than workers, halt.
Step 3) do any obvious job assignments
- If any job perfectly matches a worker's shift, assign them.
- If a job can only be done by one worker (or all possible workers are equal), assign them.
- if a worker can accept a job without impeding its ability to accept any other (non-equal) job, assign them.
(Note: "assigning" means removing both the job and the worker; possibly creating up to two new workers for the remaining parts of the shift before and after the job)
Step 4) loop
- If any job was assigned and removed during Step 3, go back to Step 1. (Since this cannot happen more than j times, we're still in polytime)

This algorithm will either solve or reject a lot of instances, including all your examples.
Step 1 guarantees that at every tick, at least one job must either start or end, so your timestamps now range from 0 to at most 2*j. (Basically, an instance has at most 2*j interesting time intervals, and we've relabeled all timestamps to make it explicit).

During every tick, at least one job and at least two workers must be active. Every worker must match at least two non-equal jobs (all overlapping), and every job must be matched by at least two non-equal workers.

I've been trying to come up with examples where something remains that is not solvable, but I wasn't able to. The remaining instances have so many degrees of freedom, I'm almost tempted to proclaim that Step 4 is to print "solvable" and halt. But I'm putting the ball back in your corner: try to find a better counterexample, or find proof that the remaining instances are all solvable.

Derek
Posts: 2180
Joined: Wed Aug 18, 2010 4:15 am UTC

### Re: Help me prove (or disprove) the following problem NP-hard

Tub wrote:Your reduction is invalid - you cannot "add a vertex of the worker's color"; the coloring problem starts with an entirely uncolored graph. We don't know the complexity of your variant of the coloring problem - adding constraints can both increase or decrease the complexity.

Graph coloring with a partially completed graph is still NP-hard, the reduction is very easy to show: To find a k-coloring for a partially complete graph, introduce a new k-clique of vertices, these must each be colored with a unique color. Now add an edge from each of these vertices to every pre-colored vertex of a different color. Now you can remove all colors from the graph. The resulting uncolored graph will permit the exact same colorings (up to permutation of colors) as the original partially colored graph. If the original graph had v vertices and e edges, the new graph will have v+k vertices and O(e + kv) edges, so the reduction is polynomial time.

In general, most constraint problems like this remain NP-hard when given partial solutions. In fact, if they didn't they could be solved in polynomial time by creating a partial solution, checking it, then either keeping it or trying a different partial solution.

Doesn't matter though, because your problem is obviously in NP: a solution can be verified in linear time. A reduction to an NP-complete problem tells us nothing new.

Yes I know, like I said my reduction is the wrong direction of what I need. I only mentioned it because the connection to graph coloring may be useful in the correct reduction.

Disproving a problem NP-hard implies proving P != NP, and I'm not going to help you with that. I suspect you'd be happy just finding a polytime algorithm. At first glance, there's up to w!/(w-j)! ways to assign j jobs to w workers, which is too much.

Fair enough, but yes I mean find a polynomial time algorithm. (As an aside, like most computer scientists I'm fairly confident that P != NP.)

The remaining instances have so many degrees of freedom, I'm almost tempted to proclaim that Step 4 is to print "solvable" and halt.

Even if this is true, my requirement is to find a solution, not simply show that one exists.

The problem with your algorithm (nothing you did was wrong, just insufficient) is that there will be many cases without any trivial assignment, at which point some assignment must be guessed and tried. This can result in an unsolvable subproblem even when the original problem is solvable, which therefore requires backtracking, and the possibility of exponential time. For example:

Jobs:
j1=(0, 3)
j2=(1, 4)
j3=(2, 5)
j4=(3, 6)
j5=(4, 6)
j6=(5, 7)

Workers:
w1=(0, 6)
w2=(0, 7)
w3=(1, 7)

This can be solved with:
w1={j1, j4}
w2={j2, j5}
w3={j3, j6}

But there is no trivial assignment at the start. If the assignment w2={j1} is tried, then no solution is possible. I'm pretty sure examples like this could be constructed with no solution at all, though I haven't constructed one yet (it may require more workers).

If you're right that all problems without trivial contradictions (contradictions provable by your four steps) are solvable, then a polynomial algorithm exists: After all trivial steps are applied, make a random assignment and apply all trivial steps again. If no contradiction is reached, then this assignment is part of a valid solution, so save this assignment make another one. If a contradiction is reached, then remove the assignment and try a different random assignment. If applying trivial assignments take P(j,w) time, then this takes O(j*w*P(j,w)) time. But as I said, I'm skeptical that the trivial steps always reveal contradictions. I will continue looking for examples. I might write a Python script to try to solve random examples.

Tub
Posts: 421
Joined: Wed Jul 27, 2011 3:13 pm UTC

### Re: Help me prove (or disprove) the following problem NP-hard

But there is no trivial assignment at the start. If the assignment w2={j1} is tried, then no solution is possible.

w1={j2, j5}
w2={j1, j4}
w3={j3, j6}

I'm a bit short on time right now, so that's all I'm going to add. Implementing the algorithm might find us a better counter-example.

This just screams "use a sweepline algorithm", if we could prove that keeping at most O(n^k) solutions in the state is sufficient.

Derek
Posts: 2180
Joined: Wed Aug 18, 2010 4:15 am UTC

### Re: Help me prove (or disprove) the following problem NP-hard

I made a mistake in the description (too much copy-pasting), it should have been:

Jobs:
j1=(0, 3)
j2=(1, 4)
j3=(2, 5)
j4=(3, 6)
j5=(4, 7)
j6=(5, 7)

Workers:
w1=(0, 6)
w2=(0, 7)
w3=(1, 7)

Every job has at least two possible workers that can be assigned to it, no job perfectly matches a shift, and every job assignment will impede some other possible job assignment. Therefor there are multiple choices for the first assignment, but some choices lead to unsolvable solutions.

Derek
Posts: 2180
Joined: Wed Aug 18, 2010 4:15 am UTC

### Re: Help me prove (or disprove) the following problem NP-hard

If you're right that all problems without trivial contradictions (contradictions provable by your four steps) are solvable, then a polynomial algorithm exists: After all trivial steps are applied, make a random assignment and apply all trivial steps again. If no contradiction is reached, then this assignment is part of a valid solution, so save this assignment make another one. If a contradiction is reached, then remove the assignment and try a different random assignment. If applying trivial assignments take P(j,w) time, then this takes O(j*w*P(j,w)) time. But as I said, I'm skeptical that the trivial steps always reveal contradictions. I will continue looking for examples. I might write a Python script to try to solve random examples.

I implemented a program to apply this algorithm to solve the problem, I even applied some more logic to remove workers that cannot be assigned any jobs to improve the job count versus worker count checks. I ran this against randomly generated problems (after testing it on all the examples in this thread already, on which it worked), and it found the following problem which passes all the basic tests but has no solution:

Jobs:
j1=(5, 8)
j2=(3, 5)
j3=(4, 7)
j4=(6, 8)
j5=(3, 5)

Workers:
w1=(4, 9)
w2=(2, 7)
w3=(2, 8)

All basic checks pass:
-There is more worker time available than job time.
-At all times the number of available workers is greater than the number of available jobs.
-There are no trivial assignments available:
--Every job can be done by at least two workers
--Every worker has multiple overlapping jobs to choose from.
--No worker has a job that matches it's shift, even after contraction of time (the way I actually implemented this was to look for any jobs that were supersets of all other available jobs for that worker).

Despite this, if you play around with this example you'll see pretty quickly that it has no solution. I think this demonstrates that any solution will probably have to include some kind of backtracking.

Qaanol
The Cheshirest Catamount
Posts: 3064
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: Help me prove (or disprove) the following problem NP-hard

I believe this is a linear programming problem—very nearly a textbook example of one—and as such can be solved in polynomial time.
wee free kings

DavidSh
Posts: 179
Joined: Thu Feb 25, 2016 6:09 pm UTC

### Re: Help me prove (or disprove) the following problem NP-hard

The only formulations I can think along the lines of linear programs also require integrality of the variables, making them integer linear programs. Many NP-hard problems can be formulated as integer linear programs.

-- much later --

I think this is NP-hard. I can see an on-line abstract for a paper by M. R. Garey, D. S. Johnson, G. L. Miller, and C. H. Papadimitriou, which claims to be NP-complete the problem of determining, given a set of circular arcs, and a number K, whether you can color the arcs using no more than K colors such that no two overlapping arcs have the same color. If you had a polynomial-time algorithm for your scheduling assignment problem, I think you could solve the arc-coloring problem in polynomial time, roughly as follows:

Given a set of arcs and a number K, pick an arbitrary point P on the circle. Count how many arcs cross P. Call this number N. If N is more than K, the arc coloring is impossible. Otherwise, declare P to be midnight, and the circle to correspond to 24 hours. For each of the N crossing arcs, create a worker that becomes available at the clockwise end of the arc, and becomes no longer available at the counterclockwise end of the arc. If K is more than N, create additional K-N workers that are available from midnight to midnight -- that is, all the time. For each of the remaining arcs that don't cross P, create a job to be scheduled.
Now, run your polyomial-time scheduling assignment problem. Each worker then can map back to a different one of the K colors, so the assignment of jobs to workers corresponds to a coloring of the arcs.