So say we have a bipartite graph G=(X,Y,E). Let\'s make a game out of it. I go f

Question

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.

Explanation / Answer

Let me spell out the solution.

We first show that Player 2 wins if there is a perfect matching ?. Player 2's strategy is very simple: if the current path ends at a vertex v, she choose ?(v). Induction shows that ?(v) is never taken, since the edges chosen by Player 1 never belong to the perfect matching. Player 2 never gets stuck, and so wins.

The more complicated case is when there is no perfect matching. Let ? be a maximal matching, and let x?X be a vertex not in ?. Since x??, the edge (x,y) chosen by Player 2 is not in ?. If he can, Player 1 now choose ?(x), and induction again shows that Player 2 never chooses edges in ?, and so Player 1 can choose an edge in ? as long as there is one adjacent to the vertex that Player 2 chose. If Player 1 gets stuck then the edges chosen by the players trace out an alternating path with Player 2 having one extra edge, showing that ? wasn't a maximal matching.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.