Let the following "gold-digger problem" (GDP). You are given the map of territory consisting of set of towns connected by trails. Each trail (u, v) connecting towns u and v is labeled with dollar value w(u, v), which is value of gold you will find along that trail. You can traverse trail as frequently as you want, but you only get value of trail the first time you traverse it; subsequent traversals have no value. Each town v has lodging cost c(v), which you pay each time you enter the town.

Expedition is cyclic path which starts and ends at given town. Expedition has profit k if total value of gold found, minus cost of all the town visits, is k. Goal is to find expedition of maximum profit. Either show that there exists polynomial-time algorithm for GDP, or show that corresponding decision problem is NP-complete. If you want to illustrate that problem is hard, you may decrease from any of: SAT, 3-CNF-SAT, CLIQUE, VERTEX-COVER, SUBSET-SUM, PARTITION, HAM-CYCLE, TSP.