Consider the following "gold-digger problem" (GDP). You are given a map of a territoryconsisting of a set of towns connected by trails. Each trail (u, v) connecting towns u and vis labeled with a dollar value w(u, v), which is the value of the gold you will find along thattrail. You can traverse a trail as often as you want, but you only get the value of the trailthe first time you traverse it; subsequent traversals have no value. Each town v has a lodging
cost c(v), which you pay each time you enter the town.An expedition is a cyclic path that starts and ends at a given town. An expedition has profitk if the total value of gold found, minus the cost of the all the town visits, is k. The goal isto find an expedition of maximum profit.Either show that there exists a polynomial-time algorithm for GDP, or show that the correspondingdecision problem is NP-complete. If you want to show that the problem is hard, youmay reduce from any of: SAT, 3-CNF-SAT, CLIQUE, VERTEX-COVER, SUBSET-SUM,
PARTITION, HAM-CYCLE, TSP.