14

I've struggled some time with a problem from a programming contest (Andrew Stankevich Contest 21) about a game that goes like follows:

Nick and Peter like to play the following game [...]. They draw an undirected bipartite graph G on a sheet of paper, and put a token to one of its vertices. After that they make moves in turn. Nick moves first.

A move consists of moving the token along the graph edge. After it the vertex where the token was before the move, together with all edges incident to it, are removed from the graph. The player who has no valid moves loses the game.

The graph is given and the task now is to find for a given start node, whether the starting player wins or loses if both players play optimally. To summarize

  • Bipartite graph
  • We are given the start node (say on the left side)
  • We move in turns, a move consists of following an edge, but we can't visit a node that was already visited
  • The player who cannot move loses

Since the graph is bipartite, Nick (the first player) will always remove a node from the left side and Peter will always remove a node from the right side.

The graph can have up to 1000 nodes (at most 500 at each side) and 50000 edges, so a good polynomial time algorithm is needed (the time limit here is 2 seconds to solve all starting positions, but I think we can share a lot of information between the different starting positions).

I'm pretty sure that this can be reduced to some kind of vertex covering or packing problem, because the graph is bipartite, but I can't find a strategy that correlates to any of these.

I know the solution for a special case: Let's say the sides have n1 and n2 vertices, respectively. If there is a matching of size min(n1, n2) and if the player on the smaller side begins, than there exists a winning strategy: He just has to follow the matched edges and automatically wins.

Any ideas?

Niklas B.
  • 92,950
  • 18
  • 194
  • 224
  • Wouldn't this be somehow related to a Hamiltonian path? – Vincent van der Weele Mar 24 '14 at 19:37
  • @RikayanBandyopadhyay The token is moved in an alternating manner between the player (first Nick moves, then Peter moves, then Nick again) and they share the same token – Niklas B. Mar 24 '14 at 19:38
  • @Heuster The might well be... But Hamiltonian path is NP-complete for bipartite graphs. Also I don't see a strategy that maximizes the number of visited nodes or similar – Niklas B. Mar 24 '14 at 19:40
  • I think that http://en.wikipedia.org/wiki/Minimax can be used. However it is not really efficient in depth. The value of decision would be how much you or your opponent has possibilities to go forward. You want to find solution where you have the most and enemy as less as possible. Minimax is used for example in chess decision making with same logic (each turn have some "score" and you want to find turn, where you get the most score and the enemy the less - and few turns in future of course) – libik Mar 24 '14 at 19:42
  • Hmmm... many two-player games end up being PSPACE-complete, but those time bounds suggest there's a much faster solution. Interesting problem! – templatetypedef Mar 24 '14 at 19:42
  • @templatetypedef - Maybe - like chess - there is no perfects solution, but there are approximate solutions, which are good enough. – libik Mar 24 '14 at 19:43
  • @libik An optimal solution is needed here. The game value has to be computed precisely (1 or 0, depending on which player wins) – Niklas B. Mar 24 '14 at 19:44
  • @libik I think an approximate solution for a decision problem is not what Niklas is looking for. – G. Bach Mar 24 '14 at 19:44
  • @templatetypedef The contests are full of interesting problems like these... I think this is not even among the difficult ones (but then again it's a Russian contest ;) – Niklas B. Mar 24 '14 at 19:46
  • @NiklasB. - Ah, I thought that two humans created their own alghoritms and then they let them played against each other and who had better alghoritm, won... – libik Mar 24 '14 at 19:46
  • I'm thinking backtracking dynamic programming for each vertex is the key. – Nuclearman Mar 24 '14 at 19:51
  • @Nuclearman What would be the DP state? I don't see it – Niklas B. Mar 24 '14 at 19:56
  • @libik In chess there are perfect solutions. This is possible to be proven mathematically; being non random and full knowledge stuff. It is a problem for modern computers (not algorithms!) to find them ;). I cant bet this game is about [this problem](http://cs.stackexchange.com/questions/11281/how-to-find-the-minimum-number-of-vertices-whose-removal-make-the-graph-disjoint) and the biparity is allowing some kind of "exploit" to make it fast. – luk32 Mar 24 '14 at 20:10
  • @luk32 - if we are solving concrete example with concrete alghorithm, it implicitly means, that we are talking about "solvable in reasonable time", in this case, it is 2secs. – libik Mar 24 '14 at 20:13
  • @libik I think it is safe to assume that there is a polynomial time algorithm that solves this particular game – Niklas B. Mar 24 '14 at 20:19
  • I had to think about it for a bit to try to avoid logical flaws, but I keep coming back to the all pairs all shortest paths. An vertex cannot be traversed twice so it works out. However, 50 million seems a bit high for 2 seconds. – Nuclearman Mar 24 '14 at 20:22
  • @Nuclearman 5e7 is okay, but I don't see the algorithm to be honest. But it's impossible to debunk it without knowing what you have in mind :P – Niklas B. Mar 24 '14 at 20:25
  • 1
    This should be related to matchings; if both partitions have the same size, then a perfect matching means that the first player to move can force a win. No idea how to generalize that, though. – G. Bach Mar 24 '14 at 20:29
  • Give me a minute I've got an implementation of the algorithm handy itself which I'll provide as a partial answer. – Nuclearman Mar 24 '14 at 20:30
  • @G.Bach Yes, if every node on your side is matched, you can always follow matched edges and win. But it could be that this is not the case for either of the sides – Niklas B. Mar 24 '14 at 20:31
  • @Nuclearman I don't need code here, it's more about the idea... I can code most stuff myself :) – Niklas B. Mar 24 '14 at 20:33
  • @libik You never know. It is possible! =D. Btw Niklas. To be clear. 2s time is to find all solutions from the starting node, or any given one? You say we are given starting position, but then, that we need to solve all within the time limit. – luk32 Mar 24 '14 at 20:33
  • @luk32 It is for all starting positions together, but I would be happy with the idea for a single starting node. I think it has to do with matchings, so we can reuse the residual network of the flow algorithm between solutions – Niklas B. Mar 24 '14 at 20:35
  • @G.Bach There is nowhere said the sides are matched in sizes. I imagine a bipartite clique made of 1 to N-1 vertices a valid input. Am I wrong? – luk32 Mar 24 '14 at 20:36
  • @luk32 - if game exists for two players which plays turn by turn and they both play optimally and no random events occure, then it always has one "perfect" solution. – libik Mar 24 '14 at 20:37
  • @luk32 no, you're right. He said that he doesn't know how to generalize it, and that is basically my problem as well – Niklas B. Mar 24 '14 at 20:37
  • @libik luk32 Can you guys please break up your discussion about game theory? It somewhat clutters the comment section here – Niklas B. Mar 24 '14 at 20:38
  • It seems my approach wasn't helpful. However, it got me researching into properties of bipartite graphs. I don't suppose you noticed that in bipartite graphs, [matching and vertex cover are equivalent](http://en.wikipedia.org/wiki/Bipartite_graph#K.C3.B6nig.27s_theorem_and_perfect_graphs). – Nuclearman Mar 24 '14 at 22:10
  • @Nuclearman That's a pretty common theorem of which I am well aware. I know how to solve maximum independent set, dominating set, vertex cover etc., but I don't know how to apply it to the problem – Niklas B. Mar 24 '14 at 22:23
  • http://cs.stackexchange.com/ – Blazemonger Apr 09 '14 at 18:52
  • @Blazemonger I like SO more for this question. We have lots of algorithm questions here as well (and they're not off-topic) – Niklas B. Apr 09 '14 at 18:54
  • That's because cs.stackexchange.com wasn't around when most of them were asked. I accept that questions asking for general algorithms are considered acceptable on SO for legacy reasons, but I'm of the opinion/understanding that this site is best-suited for *specific* programming issues. Clearly this question has more to do with CS and graph theory in general than programming in specific. (But hey, I'm just zis guy, you know?) – Blazemonger Apr 09 '14 at 18:57
  • @Blazemonger If you ask me, SO would be a pretty boring place without language-agnostic questions. I answered lots of algorithm questions in the last month, only very few of my answers involved actual code. The help center says that questions about "software algorithms" are on-topic. So I guess it's a matter of preference which site to choose, and I prefer SO because I know some people here from which I expect excellent answers :) Agreed though that CS might actually be the more fitting choice (but let's face it, it gets a lot less attention) – Niklas B. Apr 09 '14 at 19:23
  • Codechef personell seems to be pretty lazy, they used this problem almost verbatim, just with general graphs: http://www.codechef.com/JULY15/problems/HAMILG – Niklas B. Jul 14 '15 at 00:18

2 Answers2

11

Proposition. Nick (the first player) wins starting from vertex v iff this vertex belongs to every possible maximum matching of the given graph. We will prove it in two steps.

  1. If there is a maximum matching without v, Nick loses.
    Indeed, since the matching is maximum, there is no augmenting path from v. That means every simple odd-length path from v can be prolonged by an edge of the matching. In terms of our problem, it means the game can be continued by Peter after every Nick's move.

  2. If there is no maximum matching without v, Nick wins.
    Consider any possible maximum matching. Move along the edge of this matching from v to, say, u. Now, the initial matching minus the edge u-v is a maximum matching of the remaining graph which does not include u. As we know from step 1, the player to move now (which is Peter) is at a loss.

As for the implementation, we can first construct a maximum matching in O(VE) utilizing the straightforward algorithm (see here for an example implementation) — turns out the common name is Kuhn's augmenting paths algorithm.

After that, you maintain a maximum matching and look at every vertex. If the vertex, say v, is not currently in the matching, Nick loses. If it is, remove the corresponding edge, say v-u, from the matching, forbid the vertex v temporarily and run a search for an augmenting path from u in O(E). If you don't find such path, Nick wins, and you have to restore the edge you removed. Otherwise, Nick loses again, and the new maximum matching can be left untouched. The total running time is O(VE) again.

Gassa
  • 8,546
  • 3
  • 29
  • 49
  • I know it as Kuhn's algorithm, no idea whether that is the correct name. Thanks Gassa, that looks really good – Niklas B. Mar 24 '14 at 23:05
  • @Niklas B.: I also faintly remembered that's Kuhn's algorithm, but the first page of Google results on the name didn't agree with that for some reason. – Gassa Mar 24 '14 at 23:07
  • There are better performing algorithms for bipartite graphs, like the [Hopcroft–Karp](http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm). – Nuclearman Mar 24 '14 at 23:09
  • @Nuclearman In competitive, shorter is always better if it's fast enough ;) Usually I would use Dinic instead of Hopcroft-Karp if I need speed, because it has the same asymptotics for matching graphs but is also a good general max-flow algorithm – Niklas B. Mar 24 '14 at 23:10
  • @Nuclearman: yeah, but this one, for a bipartite graph, is only a few lines of code (like, ten). And that is valuable in a programming contest environment. Besides, the second part of my answer is still the same O(VE) - can you do better there, too? – Gassa Mar 24 '14 at 23:11
  • True, the question is whether O(VE) will be enough with the time-limit. As for the O(VE), it might be possible if that matching and vertex cover approach I mentioned in David Eisenstat's answer works out (reducing that part to O(V)). However, a fair point that I can't say for certain it will and as you said if the algorithm is fast enough for the timeline, then it's fast enough. At least unless your trying to get the best time... – Nuclearman Mar 24 '14 at 23:11
  • @Nuclearman: Yeah, it's enough. Actually, I checked that on the genuine problem's test data before replying. You can try it [here](http://codeforces.com/gym/100337) (Problem A). – Gassa Mar 24 '14 at 23:13
  • I think the same argument should work for general graphs as well, which is pretty cool. Is that correct or am I missing something? – Niklas B. Apr 05 '14 at 18:19
  • @NiklasB.: Perhaps that's true for non-bipartite graphs. It seems to follow (and maybe a bit clearer, too) from David's answer as well. – Gassa Apr 05 '14 at 19:54
4

Cute problem. I believe that the intended solution is to compute a maximum matching and then determine which left vertices belong to every maximum matching. These are the wins for player one.

The winning strategy is to choose edges that belong to a maximum matching. If the start vertex v belongs to every maximum matching, then the other endpoint w of the edge e chosen by player one does not belong to every maximum matching of the graph minus v (since v belongs to every maximum matching, the cardinality of the maximum matching decreases by one after deletion, so since e belongs to some maximum matching M, we have that M - e is maximum in the new graph and leaves the other endpoint of e unmatched). Conversely, if there exists a maximum matching to which v does not belong, then all of its neighbors w belong to all maximum matchings of the graph minus v (otherwise, find a maximum matching without w and add the edge from v to w, contradicting the assumption that the maximum cardinality of a matching did not decrease when we deleted v).

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • 2
    (To determine whether a vertex v belongs to every maximum matching: delete it and try to augment what's left of the matching.) – David Eisenstat Mar 24 '14 at 22:55
  • Nice, this was exactly the algorithm I had in mind, but I had no idea how to prove its correctness. Thanks David! – Niklas B. Mar 24 '14 at 23:00
  • On the most basic simple example (the base case) Nick wins if his turn begins on a covered vertex. Thus Nick tries to move towards uncovered vertices, while Peter tries to move towards covered vertices. Seems like this ends up being the same strategy looking at the Konig's Theorem Wikipedia page, but I haven't been able to test it other than by hand due to not having bipartite vertex cover algorithm handy. Although it might be more accurate to say the covered/uncovered edge with the lowest degree. Although, given the equivalence, it's probably simpler to just use this approach. – Nuclearman Mar 24 '14 at 23:02
  • I choose the other answer because I find the proof using augmenting paths slightly more intuitive. Thank you both! – Niklas B. Mar 25 '14 at 00:24