Given a Set K of n tasks, a set T of t possible time-intervalls to schedule any task, and a number k:

Is there a schedule for the tasks, such that there are at most k conflicts (time - overlaps) of the tasks?

I'm having trouble showing that this is np-complete. I don't know how to reduce it to another np-complete problem. My intuition suggests something graph-related, but I can't get anywhere.

Edit: What I thought so far: Let the undirected Graph

G = (V;E) with V= {T} $\cup$ {K} and E = { {u,v} | u $\in$ K, v $\in$ T: u can be performed in intervall v}

So basically connect all tasks to timeslots they can be performed in. Is there a Hamilton cycle with at most k nodes used more than once? You will get a path along the lines of: t1-1-t2-2-t3-1-t1, which shows 1 conflict (obviously, with 3 tasks and 2 timeslots). Every intevall-node that is visited more than once is a conflict node. Is this correct thinking? How can I show this is np -complete?

  • $\begingroup$ I haven't done the full reduction, but my guess is you want to look at Graph Coloring. $\endgroup$ – jmite Dec 7 '14 at 17:06
  • $\begingroup$ I thought of something using hamilton cycle. See above. Is that correct? $\endgroup$ – RunOrVeith Dec 9 '14 at 14:30
  • $\begingroup$ @RunOrVeith You can use any NP-complete problem as reduction partner, so yes. $\endgroup$ – Raphael Dec 9 '14 at 15:19

Your Answer

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

Browse other questions tagged or ask your own question.