emoji's blog

Finding if there is an odd length path between any 2 vertices in a graph
By emoji, history, 8 years ago, In English

I have found a really interesting problem http://codeforces.net/problemset/problem/97/E but i am not able to solve it in the required time complexity.

The problem is that given a graph with vertices n and edges m where n,m<=1e5 and

you are also given q queries where q<=1e5 and in each query 2 vertices are given u and v.

we have to find that whether there exists a simple path with odd length between u and v in each query.

Can someone please help me in solving the problem.

  • Vote: I like it
  • +27
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by emoji (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

UPD: wrong solution

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That proof with bipartite argument is so beautiful that it makes my comment seem stupid! Nice :D

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Actually I'm wrong. I accidentally read that path is any. My solution didn't works for case:

      Graph with 7 vertex:
1 2
2 3
3 4
4 5
3 6
6 7
7 3
And for query 1 5 answer is no.
      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

UPD: wrong as well, as pointed out by P_Nyagolov (thank you).

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

if the path asked was not simple we could have done shortest path algorithm with states. Am i right or wrong?? It would take O(n) time though per query.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    If the path did not have to be simple you can solve in O(N) precomputation and O(1) query. Read Temirulan's first version comment to see solution to this alternative problem.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If I remember correctly there is a fact that in a 2-connected-graph with odd cycle, each vertex will appear in at least one odd cycle too.

If I'm not wrong about this then partitioning the graph into 2-connected-components will solve the problem.

NOTE: I'm not sure about edge-connected or vertex-connected :)...but I think it should be vertex-connected.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This is true for vertex-connected graphs, but can you elaborate a bit on how it helps us?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 4   Vote: I like it +10 Vote: I do not like it

      If that's true then we can divide the graph into sereval bi-connected components and we can construct a tree by consider each connected component and their articulation Point as vertices. Consider the components passed by any simple path (u,v), if any of the component(vertex in new graph) on the induced path on the new graph contains a odd cycle, there is always a odd path from u to v.

      Proof: consider a simple path (u', v') passing vertex u and v in original graph and they are in same bi-connected component. Destroy the path from u to v. Consider some vertex w that lies on same odd cycle as u. There are at least two paths from u and w and they differ in parity. We want to pick some w so that the cycle does not contain v, or let w=v if u and v lies on some same odd cycle. Then we pick up any simple path that does not affect the connectivity from u and w (it must exist, due to the bi-connectivity of the component and the fact that v does not lie on the odd cycle) and we can now control the parity of the (u', v') path by alternating the path from u to w.

      Otherwise, the parity of any simple path from u to v does not change (because the component is bipartite) and can be computed easily. We can precompute stuff (contains odd cycle, path parity from vertex to vertex) in O(N lg N) and answer query in O(1) time.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If you pick graph G7 in this picture, the triangle is obviously biconnected, but there is no simple odd length path between the two leaf vertices.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          The simple path does not pass through the triangle (aka component). It passes through one of the AP of the triangle however.

          → Reply