Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs

Parinya Chalermsook, Shiva Kintali, Richard Lipton +1

Consider the following problem. A seller has infinite copies of $n$ products represented by nodes in a graph. There are $m$ consumers, each has a budget and wants to buy two produc…