How to Sell a Graph: Guidelines for Graph Retailers

We consider a profit maximization problem when pricing a set of m items which can be represented as the edges of an undirected multi graph G. There is a set of n customers, each of which is interested in purchasing a bundle of edges of G, and we assume that these edges form a simple path in G. Each customer has a known budget for her respective bundle. Customers are single minded, so they are only interested in that particular bundle. The objective is to find a pricing and a feasible assignment of items to customers in order to maximize the total profit. We discuss the complexity of the problem when the underlying graph is a path, and derive a fully polynomial time approximation scheme, complementing a recent NP-hardness result. If the underlying graph is a tree, and all items are unique, we show that the problem is polynomially solvable, contrasting its APX-hardness for the case of unlimited availability of items. However, if the underlying graph is a grid, and items are unique, we show that it is even NP-complete to approximate the problem to within a factor n1-2.