Ferrying the Deceased
Betal has picked up a part-time job that involves ferrying $n$ deceased people across a river for a smooth transition into the next phase. Certain pairs of these people are sworn enemies, who cannot be taken together on the ferry because when on water, they can in fact get into a deadly fight, and this will be a distraction to Betal who will be navigating rough waters. It is safe to leave them on the shore because corpses don't fight on land.
The ferry has unlimited capacity, but Betal has limited time.
Input: Integers $k$ and $n$, and an $n$-vertex graph $G$ describing the pairs of enemies (an edge $(u,v)$ means $u$ and $v$ are enemies).
Output: TRUE if Betal can ferry all $n$ people across the river safely in at most $k$ rounds, FALSE otherwise.
Part A
Consider 5 people: $A, B, C, D, E$ with the following enemy pairs:
(This forms a 5-cycle.)
What is the minimum number of ferry trips needed to transport everyone safely?
The enemy graph is a 5-cycle $C_5$, which has chromatic number 3.
We cannot do it in 2 trips because $C_5$ is an odd cycle and not bipartite.
We can do it in 3 trips:
- Trip 1: $\{A, C\}$ (not enemies)
- Trip 2: $\{B, D\}$ (not enemies)
- Trip 3: $\{E\}$
Part B
Is this decision problem NP-hard in general?
Each ferry trip must carry an independent set of $G$ (no two enemies together). Ferrying all $n$ people in $\leq k$ rounds means partitioning $V(G)$ into $\leq k$ independent sets — exactly the definition of $k$-colorability. Since Graph $k$-Coloring is NP-complete for $k \geq 3$, this problem is NP-hard.
Hints
Think about which people can safely travel together (no edge between them).