In: Computer Science
A teacher needs to take n naughty children across a river during
a trip. Certain pairs of these
children don't like each other at all and cannot be left together
on one side of the river unless the
teacher is also present, or they will harm each other. The ferry
can hold at most k passengers at a
time, including the teacher, and the kids are too small to pilot
the ferry.
Prove that it is NP-hard to decide whether the
teacher can ferry all n children across the river
unharmed by reducing from the Independent Set
problem. The input consists of the integers k and
n and an n-vertex graph G describing the pairs of children who
don't like each other. The output
is either True or False.
Start with a graph G on which you want to solve the
independent
set problem with parameter k'. Create two copies of G. Add some
edges. Choose an appropriate
k.
In graph theory, a connected graph G is said to be k-vertex-connected (or k-connected) if it has more than k vertices and remains connected whenever fewer than k vertices are removed. The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected.