Being negative makes life NP-hard (for product sellers)

Sven O. Krumke, Florian D. Schwahn, Clemens Thielen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


We study a product pricing model in social networks where the value a possible buyer (vertex) assigns to a product is influenced by the previous buyers and buying proceeds in discrete, synchronous rounds. Each arc in the social network is weighted with the amount by which the value that the end node of the arc assigns to the product is changed in the following rounds when the starting node buys the product. We show that computing the price generating the maximum revenue for the product seller in this setting is possible in strongly polynomial time if all arc weights are non-negative, but the problem becomes NP-hard when negative arc weights are allowed. Moreover, we show that the optimization version of the problem exhibits the interesting property that it is solvable in pseudopolynomial time but not approximable within any constant factor unless P = NP.

Original languageEnglish
Title of host publicationFun with Algorithms - 7th International Conference, FUN 2014, Proceedings
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783319078892
StatePublished - 2014
Externally publishedYes
Event7th International Conference on Fun with Algorithms, FUN 2014 - Sicily, Italy
Duration: 1 Jul 20143 Jul 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8496 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference7th International Conference on Fun with Algorithms, FUN 2014


  • computational complexity
  • product pricing
  • social networks


Dive into the research topics of 'Being negative makes life NP-hard (for product sellers)'. Together they form a unique fingerprint.

Cite this