4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I've been told that there are two cases to look at. One when a perfect matching is possible, and one where a perfect matching is not possible. $\endgroup$ – User Nov 12 '13 at 23:54
2
$\begingroup$

Let me spell out the solution.

We first show that Player 2 wins if there is a perfect matching $\pi$. Player 2's strategy is very simple: if the current path ends at a vertex $v$, she choose $\pi(v)$. Induction shows that $\pi(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 $\pi$ be a maximal matching, and let $x \in X$ be a vertex not in $\pi$. Since $x \notin \pi$, the edge $(x,y)$ chosen by Player 2 is not in $\pi$. If he can, Player 1 now choose $\pi(x)$, and induction again shows that Player 2 never chooses edges in $\pi$, and so Player 1 can choose an edge in $\pi$ 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 $\pi$ wasn't a maximal matching.

$\endgroup$
  • $\begingroup$ A question for the curious: what happens in the non-bipartite case? $\endgroup$ – Yuval Filmus Nov 13 '13 at 8:28
  • $\begingroup$ Check out the link I posted from Dartmouth. I think this can work for any simple, connected graph (not necessarily bipartite). $\endgroup$ – User Nov 17 '13 at 8:36
1
$\begingroup$

I've found the solution here: solution courtesy of Dartmouth

Essentially, the second player wins if and only if there's a perfect matching.

$\endgroup$
  • 2
    $\begingroup$ Perhaps you could spell it out? $\endgroup$ – Yuval Filmus Nov 13 '13 at 4:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.