Proving Problems NPC

Efficient Recruiting

Organize a summer sports camp. Need at least one coach to cover $n$ sports. We have $m$ potential coaches. Here is the kicker - for each of the $n$ sports, there is some subset of $m$ applicants. Here is the decision problem: For a give number $k < m$, is it possible to hire at most $k$ coaches and still cover $n$ sports?

Prove efficient recruiting is NPC.

Prove Efficient Recruiting in NP

Certificate: a subset $V'$ of coaches that cover all $n$ sports

Certifier: for each coach in $V'$, mark the sport that he/she qualifies, check if all $n$ sports are cleared in the end.

The checker takes polynomial time. Thus, efficient recruiting is in NP.

Reduction from Vertex Cover

We want to show VC $\leq_p$ ER

Step 1 Construct a poly-time algorithm that converts VC inputs to ER inputs

Given a graph $G = (V, E)$ and an integer $k$, we'd like to define a sport $S_e$ for each edge $e$ and a coach $C_v$ for each vertex $v$. $C_v$ is qualified for sport $S_e$ iff $v$ is an endpoint of edge $e$.

Step 2 Claim: an ER instance is true iff the corresponding VC instance is true

$\Rightarrow$ If there are $k$ coaches that cover all $n$ sports, then the $k$ vertices in the graph will cover all the edges in $G$.

$\Leftarrow$ If there is a vertex cover of size $k$, then this set of coaches will cover all sports.

Reduction from Set Cover

We want to show SC $\leq_p$ ER

Step 1 Convert SC inputs to ER inputs

Let the universe set $U$ be the set of sports, and let each coach's skills be a subset, so the collection of subsets will a collection of coaches. We have $k$ subsets union to $U$.

Step 2 Claim: an ER instance is true iff the corresponding SC instance is true

$\Rightarrow$ If there are $k$ coaches that cover all $n$ sports, then the $k$ subsets will cover all the elements in the university and union to $U$.

$\Leftarrow$ If there are $k$ subsets that union to $U$, then these $k$ coaches will cover all sports.

References

Algorithm Design Ch8.2, 8.3

Connie Fan Blog Solutions