Reference no: EM132313104
Math Assignment - Algorithms
Need help with a couple of NP hardness proofs.
Task 1 -
You are a pirate captain. After looting a cargo ship, you need to divide up the n treasure chests among k pirates in an egalitarian manner to avoid mutiny. A reasonable way to model this is that the happiness of a pirate is the total value of his allocation, and the goal is to find an allocation such that least-happy pirate is as happy as possible.
This suggests the following decision problem called MUTINY-FREE-ALLOCATION (or MFA for short). The input to MUTINY-FREE-ALLOCATION consists of:
- a list of n non-negative integers v1, . . . , vn,
- the number of pirates k, and
- a lower bound l.
The problem is to decide if there is a partition of v1, . . . , vn into k subsets S1, . . . , Sk such that each subset Si sums to at least l.
Your task is to prove that -
(a) MUTINY-FREE-ALLOCATION is in NP,
(b) MUTINY-FREE-ALLOCATION is NP-hard using a Karp reduction. [Hint: Reduce from the Partition problem.]
Task 2 -
You are planning a road trip across Australia and need to decide which destinations you can reach from Sydney. The constraints are as follows: each road has a length and a toll cost; moreover, your car can travel K kilometers before it breaks down and you have D dollars. A destination is reachable if there exists a path from Sydney to the destination with total length at most K and total cost at most D.
This suggests the following decision problem called ROAD-TRIP-REACHABILITY (or RTR for short). The input consists of:
- an undirected graph G = (V, E) where each edge e has a non-negative integer length l(e) and a non-negative integer cost c(e),
- a source vertex s and a destination vertex t in V,
- a non-negative integer length budget K and a non-negative integer cost budget D.
The problem is to decide if there exists a simple path P from s to t in G with total length ∑e∈p l(e) ≤ K and total cost ∑e∈P c(e) ≤ D.
Your task is to prove that -
(a) ROAD-TRIP-REACHABILITY is in NP,
(b) ROAD-TRIP-REACHABILITY is NP-hard using a Karp reduction. [Hint: Reduce from the Partition problems].
Attachment:- Assignment Files.rar