Monday, April 6, 2009

Puzzle: Cycle Containing Two Nodes

The following simple puzzle was circulating among Romanian olympiad participants around 1998. It was supposed to be a quick way to tell apart algorithmists from mere programmers.

Given an undirected graph G, and two vertices u and v, find a cycle containing both u and v, or report than none exists. Running time O(m).
Update: Simple ideas based on a DFS (like: find one path, find another) do not work. Think of the following graph:
If you first find the path s → a → b → t, you will not find a second. 

The one-line answer is: try to route two units on flow from s to t in the unit-capacity graph (with unit node capacities if you want simple cycles). This is not the same as two DFS searches, because the second DFS is in the residual graph (it can go back on the edges of the first DFS).


About the previous puzzle: As many people noticed, Alice can guarantee a win or a draw. She computes the sum of the elements on odd positions and the sum on the even positions. Depending on which is higher, she only plays odd positions or only even positions. (Bob has no choice, since the subarrays he's left with always have the ends of the same parity.)

But how do you compute the optimal value for Alice? If the sum of even and odd is equal, how can Alice determine whether she can win, or only draw? A simple dynamic program running in O(n2) time works. Can you solve it faster?

16 comments:

Anonymous said...

single DFS from u. there is a cycle iff there is a whitepath to u from a node in the subtree of v.

Anonymous said...

yeah just backtrack through parents in DFS tree if v hit; if v not hit, no cycle. DFS times O(m), backtrack time O(m).

Anonymous said...

It seems to be straightforward flow with value 2. Am I right?

Anonymous said...

i was anon 2, who MISREAD.

corrected solution--DFS from u, backtrack after hitting v (through parents in tree) to find a u--v path. cut this path's edges from the graph, and DFS to find another path. works since undirected graph has cycle iff has pair of paths.

the 2-flow idea works too, in fact it'll do what i wrote (find a path, mark it as used, find another).

Anonymous said...

Do you want edge-disjoint/node-disjoint cycles?

Mihai said...

Do you want edge-disjoint/node-disjoint cycles?

Doesn't matter, both have an O(m) solution.

Anonymous said...

An interesting variant would be find such a cycle in a directed graph.

Mihai said...

An interesting variant would be find such a cycle in a directed graph.

But that is simply DFS, no?

Anonymous said...

Mihai, how do you define the residual graph for a flow problem with node capacities in an *undirected* graph?

Just trying to see if you are an mathematician, or a mere algorithmist. :)

rgrig said...
This comment has been removed by the author.
Mihai said...

What's wrong with the residual network for an undirected node-capacitated graph? It seems like a perfectly healthy creature to me. It's of course a directed graph.

Anonymous said...

Just define it. Let's say I have G=(V_G,E_G) undirected, with capacities u_G, and a flow x on it. What exactly is R=(V_R, E_R), and what are the capacities u_R?

Mihai said...

Dude, you shouldn't run flow on the undirected graph if you want to add node capacities. Every node v is split into v1 and v2; all edge have a version coming into v1 and one going out of v2. There is a single edge between v1 and v2 with the capacity of the node. The residual network is just what the residual network is.

Anonymous said...

Ok, so let's look at your directed network (assume no node capacities for the moment).

Say you find a flow given by two paths v, v_1, v_2, ..., v_k, u

and v, w_1, w_2, ..., v_7, v_6, ..., v_3, v_2, ..., v_10, v_9, ..., w_l, u.

What next?

Mihai said...

Ok, I think I understand your problem: you may get a flow plus a circulation, instead of just a flow.

0) Recap your lectures on flow :) These things have fairly standard fixes.

1) You can avoid the extra circulation by implementing your flow carefully. More precisely, the back edges in the residual graph should have priority in your 2nd run of DFS (this way, if there is a path going back on some edges, you will go back in a contiguous way, not hop on and off the back path).

2) Otherwise, you can easily get rid of the extra circulation. In the node-capacitated case, just keep the edges with nonzero flow that are in the same connected component with the source and sink.

Without node capacities, do two DFS from the source to the sink, staying only on edges with nonzero flow. The 2nd scan cannot get stuck, by flow conservation (what comes in must go out).

Mihai said...

PS: You should really implement this (I did it in 98 or so). You will understand these technical details much better when you need to think of them carefully.