Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The Largest Connected Subgraph Game

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

This paper introduces the largest connected subgraph game played on an undirected graph G. In each round, Alice first colours an uncoloured vertex of G red, and then, Bob colours an uncoloured vertex of G blue, with all vertices initially uncoloured. Once all the vertices are coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph whose order is greater than the order of any blue (red, resp.) connected subgraph. We first prove that, if Alice plays optimally, then Bob can never win, and define a large class of graphs (called reflection graphs) in which the game is a draw. We then show that determining the outcome of the game is PSPACE-complete, even in bipartite graphs of small diameter, and that recognising reflection graphs is GI-hard. We also prove that the game is a draw in paths if and only if the path is of even order or has at least 11 vertices, and that Alice wins in cycles if and only if the cycle is of odd length. Lastly, we give an algorithm to determine the outcome of the game in cographs in linear time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. Generalised Hex is a generalisation of Hex played on graphs, where the two players alternate picking vertices, with the first player aiming to join two fixed vertices s and t by a path formed by their vertices, while the second player aims at preventing this from happening.

References

  1. Andres, S.D., Huggan, M., Mc Inerney, F., Nowakowski, R.J.: The orthogonal colouring game. Theor. Comput. Sci. 795, 312–325 (2019)

    Article  MathSciNet  Google Scholar 

  2. Bensmail, J., Fioravantes, F., Mc Inerney, F., Nisse, N.: The largest connected subgraph game. In: Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021), Lecture Notes in Computer Science, vol. 12911, pp. 296–307. Springer (2021)

  3. Bonnet, E., Jamain, F., Saffidine, A.: On the complexity of connection games. Theor. Comput. Sci. 644, 2–28 (2016)

    Article  MathSciNet  Google Scholar 

  4. Browne, C.: Connection Games: Variations on a Theme. AK Peters, Natick (2005)

    MATH  Google Scholar 

  5. Bruno, J., Weinberg, L.: A constructive graph-theoretic solution of the Shannon switching game. IEEE Trans. Circuit Theory 17(1), 74–81 (1970)

    Article  MathSciNet  Google Scholar 

  6. Changat, M., Lekha, D.S., Peterin, I., Subhamathi, A.R., Spacapan, S.: The median game. Discrete Optim. 17, 80–88 (2015)

    Article  MathSciNet  Google Scholar 

  7. Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14(4), 926–934 (1985)

    Article  MathSciNet  Google Scholar 

  8. Duchêne, E., Gonzalez, S., Parreau, A., Rémila, E., Solal, P.: INFLUENCE: a Partizan scoring game on graphs. Theor. Comput. Sci. 878–879, 26–46 (2021)

    Article  MathSciNet  Google Scholar 

  9. Even, S., Tarjan, R.E.: A combinatorial problem which is complete in polynomial space. J. ACM JACM 23(4), 710–719 (1976)

    Article  MathSciNet  Google Scholar 

  10. Gardner, M.: The Scientific American Book of Mathematical Puzzles & Diversions. Simon and Schuster, New York (1959)

    Google Scholar 

  11. Gardner, M.: The Second Scientific American Book of Mathematical Puzzles and Diversions. Simon and Schuster, New York (1961)

    Google Scholar 

  12. Larsson, U., Nowakowski, R.J., Neto, J.P., Santos, C.P.: Guaranteed scoring games. Electron. J. Combin. 23(3), P3.27 (2016)

    Article  MathSciNet  Google Scholar 

  13. Larsson, U., Nowakowski, R.J., Santos, C.P.: Game comparison through play. Theor. Comput. Sci. 725, 52–63 (2018)

    Article  MathSciNet  Google Scholar 

  14. Larsson, U., Nowakowski, R.J., Santos, C.P.: Games with guaranteed scores and waiting moves. Int. J. Game Theory 47(2), 653–671 (2018)

    Article  MathSciNet  Google Scholar 

  15. Micek, P., Walczak, B.: A graph-grabbing game. Combin. Probab. Comput. 20(4), 623–629 (2011)

    Article  MathSciNet  Google Scholar 

  16. Reisch, S.: Hex ist PSPACE-vollständig. Acta Inf. 15(2), 167–191 (1981)

    Article  MathSciNet  Google Scholar 

  17. Schaefer, T.J.: On the complexity of some two-person perfect-information games. J. Comput. Syst. Sci. 16(2), 185–225 (1978)

    Article  MathSciNet  Google Scholar 

  18. Shapovalov, A.: Occupation games on graphs in which the second player takes almost all vertices. Discrete Appl. Math. 159(15), 1526–1527 (2011)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Université Côte d’Azur, Inria, CNRS, I3S, Valbonne, France

    Julien Bensmail, Foivos Fioravantes & Nicolas Nisse

  2. CISPA Helmholtz Center for Information Security, Saarbrücken, Germany

    Fionn Mc Inerney

Authors
  1. Julien Bensmail
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Foivos Fioravantes
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Fionn Mc Inerney
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Nicolas Nisse
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fionn Mc Inerney.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work has been supported by the European Research Council (ERC) consolidator Grant No. 725978 SYSTEMATICGRAPH, the STIC-AmSud project GALOP, the PHC Xu Guangqi project DESPROGES, and the UCA\(^\textit{JEDI}\) Investments in the Future project managed by the National Research Agency (ANR-15-IDEX-01). An extended abstract of parts of this paper has been presented in [2]

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bensmail, J., Fioravantes, F., Mc Inerney, F. et al. The Largest Connected Subgraph Game. Algorithmica 84, 2533–2555 (2022). https://doi.org/10.1007/s00453-022-00973-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-022-00973-5

Keywords

Search

Navigation