Topological Network-Control Games: Computer-Assisted Proofs

Welcome to the repository for our project on Topological Network-Control Games. This project provides computer-assisted proofs for theoretical models in this field, with our findings published in the COCOON2023 and COCOON2024 conferences.

Background

We introduce topological network-control games, a new class of combinatorial games played on graphs. These games model the influence of two competing parties aiming to control a network. In each game, given the network, players move alternately, selecting an unclaimed vertex and its unclaimed neighbors within a distance of t. The players must ensure that all claimed vertices stay connected. The goal is to decide which player can claim the majority of the vertices by the end of the game.

Objectives

• Validate Theoretical Models: Use computer-assisted methods to validate the accuracy and applicability of existing models.
• Identify Key Factors: Determine critical factors influencing network-control outcomes.
• Provide Practical Insights: Offer recommendations for implementing network-control strategies.

Methodology

Our approach involves the analysis of various strategies and graph structures:

• Strategy Analysis: Study greedy, symmetric, and optimal strategies in topological network-control games.
• Class-Specific Solutions: Solve these games on various classes of graphs.
• Complexity Proofs: Prove that finding an optimal winning strategy is a PSPACE-complete problem.

Achievements

Our research has been published in:

• COCOON2023: Liang, Z., Khoussainov, B., & Yang, H. (2023, December). Topological Network-Control Games. In International Computing and Combinatorics Conference (pp. 144-156). Cham: Springer Nature Switzerland.
• COCOON2024: Topological network-control games played on graphs

Contributions

• Understanding Combinatorial Games: Our findings enhance the understanding of combinatorial games played on graphs, specifically topological network-control games.
• Complexity Insights: Provided insights into the computational complexity of finding optimal strategies, proving it to be PSPACE-complete.

Future Work

We plan to explore more complex network structures and incorporate advanced computational techniques to enhance our models. Collaborations with industry partners are also in the pipeline to apply our findings in real-world scenarios.