The shortest connection game. (English) Zbl 1369.05147
Summary: We introduce shortest connection game, a two-player game played on a directed graph with edge costs. Given two designated vertices in which the players start, the players take turns in choosing edges emanating from the vertex they are currently located at. This way, each of the players forms a path that origins from its respective starting vertex. The game ends as soon as the two paths meet, i.e., a connection between the players is established. Each player has to carry the cost of its chosen edges and thus aims at minimizing its own total cost.
In this work we analyse the computational complexity of shortest connection game. On the negative side, shortest connection game turns out to be computationally hard even on restricted graph classes such as bipartite, acyclic and cactus graphs. On the positive side, we can give a polynomial time algorithm for cactus graphs when the game is restricted to simple paths.
In this work we analyse the computational complexity of shortest connection game. On the negative side, shortest connection game turns out to be computationally hard even on restricted graph classes such as bipartite, acyclic and cactus graphs. On the positive side, we can give a polynomial time algorithm for cactus graphs when the game is restricted to simple paths.
MSC:
| 05C57 | Games on graphs (graph-theoretic aspects) |
| 05C12 | Distance in graphs |
| 05C35 | Extremal problems in graph theory |
| 05C20 | Directed graphs (digraphs), tournaments |
| 91A43 | Games involving graphs |
| 91A05 | 2-person games |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Alfieri, A.; Nicosia, G.; Pacifici, A., Exact algorithms for a discrete metric labeling problem, Discrete Optim., 3, 181-194 (2006) · Zbl 1130.05025 |
| [2] | Bodlaender, H., Complexity of path-forming games, Theoret. Comput. Sci., 110, 1, 215-245 (1993) · Zbl 0776.90100 |
| [3] | Darmann, A.; Nicosia, G.; Pferschy, U.; Schauer, J., The subset sum game, European J. Oper. Res., 233, 539-549 (2014) · Zbl 1339.91069 |
| [4] | Darmann, A.; Pferschy, U.; Schauer, J., The shortest path game: Complexity and algorithms, (Proceedings of Theoretical Computer Science. Proceedings of Theoretical Computer Science, (TCS 2014). Proceedings of Theoretical Computer Science. Proceedings of Theoretical Computer Science, (TCS 2014), Lecture Notes in Computer Science, vol. 8705 (2014), Springer), 39-53 · Zbl 1417.68065 |
| [5] | Darmann, A.; Pferschy, U.; Schauer, J., The shortest connection game. Technical report (2015), University of Graz, Department of Statistics and Operations Research, available as: arXiv:1511.07847 |
| [6] | Darmann, A.; Pferschy, U.; Schauer, J., On the shortest path game, Discrete Appl. Math., 217, 1, 3-18 (2017) · Zbl 1351.05152 |
| [7] | Feldmann, A. E.; Foschini, L., Balanced partitions of trees and applications, Algorithmica, 71, 2, 354-376 (2015) · Zbl 1315.68201 |
| [8] | Flögel, A.; Karpinski, M.; Kleine-Büning, H., Subclasses of quantified boolean formulas, (Computer Science Logic. Computer Science Logic, Lecture Notes in Computer Science, vol. 533 (1991), Springer), 145-155 |
| [9] | Fraenkel, A. S.; Scheinerman, E. R.; Ullman, D., Undirected edge geography, Theoret. Comput. Sci., 112, 2, 371-381 (1993) · Zbl 0801.90147 |
| [10] | Fraenkel, A. S.; Simonson, S., Geography, Theoret. Comput. Sci., 110, 1, 197-214 (1993) · Zbl 0799.90145 |
| [11] | Hatzl, J., Median problems on wheels and cactus graphs, Computing, 80, 377-393 (2007) · Zbl 1170.90467 |
| [12] | Lichtenstein, D.; Sipser, M., GO is polynomial-space hard, J. ACM, 27, 2, 393-401 (1980) · Zbl 0434.68028 |
| [13] | (Nisan, N.; Roughgarden, T.; Tardos, E.; Vazirani, V. V., Algorithmic Game Theory (2007), Cambridge University Press) · Zbl 1130.91005 |
| [14] | Osborne, M. J., An Introduction to Game Theory (2004), Oxford University Press: Oxford University Press USA · Zbl 1140.91365 |
| [15] | Palbom, A., Complexity of the directed spanning cactus problem, Discrete Appl. Math., 146, 81-91 (2005) · Zbl 1087.90081 |
| [16] | Schaar, G., Remarks on Hamiltonian properties of powers of digraphs, Discrete Appl. Math., 51, 181-186 (1994) · Zbl 0801.05029 |
| [17] | Schaefer, T. J., On the complexity of some two-person perfect-information games, J. Comput. System Sci., 16, 2, 185-225 (1978) · Zbl 0383.90112 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
