# Reduction from an assignment problem to an independent set problem: NP-hard

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?

## 2 Answers

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.