Problem Detail: So say we have a bipartite graph G=(X,Y,E). Let’s make a game out of it. I go first. I pick a node in X. You go next. You pick a node in Y that is connected by an edge to the node I picked. Next it’s my turn. I pick another node in X (must be a new one that hasn’t been used before) that is also connected to the node in Y you just picked. We continue playing in this manner, until someone cannot pick a node (i.e. all edges out of the current node have already been used). When that happens, the person who cannot pick a next node loses. I’m supposed to find a polynomial time algorithm to decide which of the two players (you or me) can force a “win” for a given bipartite graph. I’m stumped. I’ve approached this in many different ways, including the following two: 1) 1) each node in the xy “path” played will use two edges, except for the first and last nodes which will only use one edge. Idea: add one new node on each side of the bipartite graph, and connect to all opposite nodes. Then check for a perfect (or maximal) matching twice, removing the edges used in the first perfect (maximal) matching when finding the second one. I don’t think this really helps us with the problem, though, as there are many different nodes you could visit next given a current node. 2) A second idea was to work with alternating/augmenting paths (as we “zig-zag” between the two sides). I again got stuck since at any given node there are many possible nodes to visit next. Does anyone have any suggestions for this problem? I’m thinking it has to do with matching, but I could be wrong. Thanks in advance!
Asked By : User
Answered By : User
I’ve found the solution here: solution courtesy of Dartmouth Essentially, the second player wins if and only if there’s a perfect matching.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/17974
