Complexity of Subtraction Games on Graphs

In games involving graphs, two players take turns removing vertices. The game ends when no moves can be made. One classic game of this type is where players remove two connected vertices in each turn. This game was created in 1978, and its complexity is still unknown. Recently, a variant called subtraction games has been introduced, where players cannot disconnect the graph during their moves.

This article explores the complexity of these games. We show that some types of subtraction games are quite difficult to solve, even when played on structured graphs like bipartite or split graphs. However, we also find that certain forms of these games can be solved more easily on specific graph types, such as unicyclic and Clique Trees.

#Game Basics

In a game based on graph vertices, the players take turns removing two adjacent vertices along with their edges from the graph. The game continues until no more moves can be made, with the player unable to play losing. This structure makes the game competitive and strategic, as players must decide which vertices to remove to maximize their chances of winning.

Impartial games, where both players have the same options, are the focus here. Depending on the position of the game, one player may have a winning strategy while the other does not. Each possible position has options leading to other positions, and a position where all options lead to a win for one player is considered a winning position.

The complexity of these games hinges on understanding the options and possible moves, which can be quite complex depending on the structure of the graph.

#Subtraction Games

Subtraction games differ slightly. Players remove vertices but must ensure the graph remains connected. This added restriction complicates the strategy as players cannot simply remove any vertex. The goal of this paper is to study the computational complexity of these non-disconnecting subtraction games.

#Complexity Classes

To analyze the complexity of these games, we categorize them into complexity classes. The PSPACE class includes problems that can be solved using polynomial space. A problem is PSPACE-complete if it is as hard as the hardest problems in PSPACE. If we can show that a specific game belongs to this class, it gives us confidence in its complexity.

We demonstrate that many subtraction games are PSPACE-complete. In particular, when players must follow specific rules or play on structured groups like bipartite graphs, the game remains challenging to solve.

However, we found that certain types of graphs, which have unique structures, allow for more straightforward solutions. For instance, Unicyclic Graphs, which contain one cycle, enable players to develop winning strategies more easily.

#Winning Strategies

In games played on different graph structures, players develop varied strategies based on the configuration of the graph. For structured graphs like unicyclic or tree-like graphs, players can analyze which moves lead to winning positions more clearly.

In a unicyclic graph, players can make moves that change the game's state without disconnecting the graph. They can even force their opponent into positions where they cannot move effectively. Similarly, in clique trees, players can remove leaf vertices or articulation points, maintaining overall structure and control of the game.

The winning conditions for these games often rely on these strategies. If a player can move to a position where their opponent has no beneficial moves, they can secure a win.

#Specific Graph Classes

1. Unicyclic Graphs
   Unicyclic graphs are those that contain exactly one cycle. In these graphs, players can make moves that reduce the overall game without leaving the graph disconnected.

2. Clique Trees
   A clique tree is a graph where each biconnected section is a clique. The ability to remove vertices without disconnecting the graph makes it easier for players to develop winning strategies.

3. Threshold Graphs
   Threshold graphs can be constructed from adding isolated or universal vertices. These graphs have characteristics that make them easier to analyze, enabling players to predict outcomes with simpler strategies.

#Complexity Results

Through our analysis, we found that many games remain hard even with these structured graphs. While some forms, like those played on trees or unicyclic graphs, allow for polynomial-time solutions, others are still challenging.

#Non-Disconnecting Condition

The non-disconnecting rule complicates the game significantly. Players must be aware of how their moves will affect the connectivity of the graph. This leads to more strategic thinking and careful planning of moves. The interplay between these rules and graph structures is key to understanding the complexity of the games.

#Hardness Results

Our findings confirm that many subtraction games are PSPACE-complete. Even when played on structured graphs, the complexity remains high. For instance, games played on bipartite graphs exhibit this complexity, as does the game on split graphs.

#Polynomial Time Algorithms

Despite the complexity of many forms of these games, we also uncovered polynomial-time algorithms for specific classes. For example, calculating outcomes on unicyclic graphs or clique trees can be done efficiently.

#Conclusion and Future Directions

This study adds to the understanding of the complexity surrounding subtraction games and vertex deletion games in general. Some games can be categorized as difficult or even unsolvable within certain limits, while others lend themselves to efficient strategies depending on their graph structure.

Future research can focus on other tree-like graphs, exploring additional structures and their effects on game complexity. There are still open questions about the relationships between various graph types and the behaviors of these games.

In conclusion, while the computational complexity of these games is high, the exploration of specific graph structures provides pathways for simpler solutions. The balance between game rules, graph types, and player strategies continues to offer rich opportunities for research in this field.