Graph sharing games: complexity and connectivity

Details Graph sharing games: complexity and connectivity Graph sharing games: complexity and connectivity

2012-02-04

arxiv.org/abs/1202.0847v2

Computer Science

Discrete Mathematics

22 pages, 11 figures; updated references, minor stylistical changes

Scientific paper

We study the following combinatorial game played by two players, Alice and Bob, which generalizes the Pizza game considered by Brown, Winkler and others. Given a connected graph G with nonnegative weights assigned to its vertices, the players alternately take one vertex of G in each turn. The first turn is Alice's. The vertices are to be taken according to one (or both) of the following two rules: (T) the subgraph of G induced by the taken vertices is connected during the whole game, (R) the subgraph of G induced by the remaining vertices is connected during the whole game. We show that if rules (T) and/or (R) are required then for every epsilon > 0 and for every positive integer k there is a k-connected graph G for which Bob has a strategy to obtain (1-epsilon) of the total weight of the vertices. This contrasts with the original Pizza game played on a cycle, where Alice is known to have a strategy to obtain 4/9 of the total weight. We show that the problem of deciding whether Alice has a winning strategy (i.e., a strategy to obtain more than half of the total weight) is PSPACE-complete if condition (R) or both conditions (T) and (R) are required. We also consider a game played on connected graphs (without weights) where the first player who violates condition (T) or (R) loses the game. We show that deciding who has the winning strategy is PSPACE-complete.

Affiliated with

Also associated with

No associations

Rating

Graph sharing games: complexity and connectivity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph sharing games: complexity and connectivity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph sharing games: complexity and connectivity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-329662