Chicago Journal of Theoretical Computer Science

Volume 2013

Article 13

Published by the Department of Computer Science, The University of Chicago.

Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs

Parinya Chalermsook
Max Planck-Institut für Informatik
Saarbrücken, Germany
painya AT cs DOT uchicago DOT edu

Shiva Kintali
Department of Computer Science
Princeton University
Princeton, NJ-08540
kintali AT cs DOT princeton DOT edu

Richard J. Lipton
College of Computing
Georgia Institute of Technology
Atlanta GA-30332
rjl AT gatech DOT edu


Danupon Nanongkai
School of Physical and Mathematical Sciences
Nanyang Technological University
danupon AT gmail DOT com

November 9, 2013


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 products. Consumers are represented by weighted edges. Given the prices of products, each consumer will buy both products she wants, at the given price, if she can afford to. Our objective is to help the seller price the products to maximize her profit.

This problem is called graph vertex pricing (GVP) problem and has resisted several recent attempts despite its current simple solution. This motivates the study of this problem on special classes of graphs. In this paper, we study this problem on a large class of graphs such as graphs with bounded treewidth, bounded genus and $k$-partite graphs.

We show that there exists an FPTAS for GVP on graphs with bounded treewidth. This result is also extended to an FPTAS for the more general single-minded pricing problem. On bounded genus graphs we present a PTAS and show that GVP is NP-hard even on planar graphs.

We study the Sherali-Adams hierarchy applied to a natural Integer Program formulation that $(1+\epsilon)$-approximates the optimal solution of GVP. Sherali-Adams hierarchy has gained much interest recently as a possible approach to develop new approximation algorithms. We show that, when the input graph has bounded treewidth or bounded genus, applying a constant number of rounds of Sherali-Adams hierarchy makes the integrality gap of this natural LP arbitrarily small, thus giving a $(1+\epsilon)$-approximate solution to the original GVP instance.

On $k$-partite graphs, we present a constant-factor approximation algorithm. We further improve the approximation factors for paths, cycles and graphs with degree at most three.

Submitted July 3, 2012, revised September 9, 2013 and November 7, 2013; published November 9, 2013.

DOI: 10.4086/cjtcs.2013.013

[] Article 12 [] Article 14
[back] Volume 2013 [back] Published articles
[CJCTS home]