The problem I have is as follows: I have a complete bipartite graph $G=(V \cup C,E)$ as input, where $|V|=1, |C|=n, |E|=n$ The interpretation is that the node of $V$ is a vehicle, the $n$ nodes of C are incidents and the $n$ edges from $V$ to $C$ are the travel times from the vehicle to the incidents. Now the incidents occur at a certain time and due to that not all incidents can be assigned to the vehicle. Every incident induces a set $D_i$ that consist of incidents that may not be assigned to the vehicle if incident $i$ is assigned to the vehicle: $D_i = \{k|\text{incidents $k$ that may not be assigned to the vehicle if incident $i$ is assigned to the vehicle}\}$ Out of the sets $D_1, \dots , D_n$ a 'Forbidden Incident' Graph $G=(C,E)$ can be constructed where an edge $(h,i)\in E$ if ($i \in D_h$ or $h \in D_i$). See the following figure as an example: Forbidden Incidents Graph

So the problem is: Give a set of incidents, is this set an independent set in the forbidden incident graph? It is known that an Independent Set problem is NP-hard. Now I aim to proof the conjecture that this problem is also NP-hard.

So I want to find a reduction from my problem to the independent set problem.

Any hints?


If you want to show that your problem is NP hard, your reduction should go in the other direction. You have to show: $\exists L \in NPH: L \le_M yourProblem$ where $NPH$ is the Set of NP-hard languages.

Your try looks like you wan't to reduce from your problem to Independent Set.


As Tomet pointed out, your reduction is in the wrong direction.

But there is a more fundamental problem (which is something to be cheerful about if your underlying goal is to solve the problem efficiently): If, as you say, the set of incidents is given, then checking if they form an independent set in the forbidden incidents set is trivial: All you need to do is check whether any pair of them corresponds to an edge in the graph. This is $O(n^2)$ time for $n$ incidents.


Your Answer

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

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