Abstract
The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem introduced at WADS’07. The game is played on a graph, whose edges are colored either red or blue, and where the red edges have a given fixed cost. The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. We study this problem in the cases of planar and bounded-treewidth graphs. We show that the problem is NP-hard on planar graphs but can be solved in polynomial time on graphs of bounded treewidth.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abrahamson, K.R., Fellows, M.R.: Finite automata, bounded treewidth, and well-quasiordering. In: Robertson, N., Seymour, P. (eds.) Graph Structure Theory, pp. 539–564 (1993)
Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153–180 (1994)
Bilò, D., Gualà, L., Proietti, G., Widmayer, P.: Computational aspects of a 2-player Stackelberg shortest paths tree game. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 251–262. Springer, Heidelberg (2008)
Briest, P., Hoefer, M., Krysta, P.: Stackelberg network pricing games. In: Proc. 25th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 133–142 (2008)
Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305–1317 (1996)
Cardinal, J., Demaine, E.D., Fiorini, S., Joret, G., Langerman, S., Newman, I., Weimann, O.: The Stackelberg minimum spanning tree game. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 64–76. Springer, Heidelberg (2007) (to appear in Algorithmica)
Courcelle, B.: Graph structure and monadic second-order logic: Language theoretical aspects. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 1–13. Springer, Heidelberg (2008)
Demaine, E.D., Hajiaghayi, M., Kawarabayashi, K.: Approximation algorithms via structural results for apex-minor-free graphs. In: Proc. 36th International Colloquium on Automata, Languages and Programming, ICALP (2009)
Demaine, E.D., Hajiaghayi, M., Mohar, B.: Approximation algorithms via contraction decomposition. In: Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 278–287 (2007)
Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)
Grigoriev, A., van Loon, J., Sitters, R., Uetz, M.: Optimal pricing of capacitated networks. Networks 53(1), 79–87 (2009)
Klein, P.N.: A subset spanner for planar graphs, with application to subset TSP. In: Proc. 38th ACM Symposium on Theory of Computing (STOC), pp. 749–756 (2006)
Labbé, M., Marcotte, P., Savard, G.: A bilevel model of taxation and its application to optimal highway pricing. Management Science 44(12), 1608–1622 (1998)
Roch, S., Savard, G., Marcotte, P.: An approximation algorithm for Stackelberg network pricing. Networks 46(1), 57–67 (2005)
Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. SIAM J. Comput. 11(2), 298–313 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cardinal, J., Demaine, E.D., Fiorini, S., Joret, G., Newman, I., Weimann, O. (2009). The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs. In: Leonardi, S. (eds) Internet and Network Economics. WINE 2009. Lecture Notes in Computer Science, vol 5929. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10841-9_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-10841-9_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10840-2
Online ISBN: 978-3-642-10841-9
eBook Packages: Computer ScienceComputer Science (R0)