CODEWITHSUNDEEP
algorithmgraph
ALTN
ALTN

Reputation: 699

Check if 3 given vertices from undirected graph belong to a cycle in most efficient way

Is it possible to perform some sort of pre-processing that would allow to answer the question efficiently (fast)?

The graph is connected, undirected, has no self loops neither parallel edges (a cycle is formed by at least 3 nodes).

Note that this a yes/no query, meaning that I just need to know whether such a cycle exits, which one doesn't matter.

Edit: My progress so far (based on Nursultan hint) and where I'm blocking:

I'm separating the graph into sub-components through articulation points, and then doubling articulation points in each sub-component they originally separated. This came from the following observation: 3 given vertices may belong to a cycle iff they all belong to a component with no articulation points. I have not proved this but I couldn't think of a counter example.

Assuming the observation above is correct (which seems very likely), the problem now is the 3 given vertices in the query may all be articulation points, in which case all of them would belong to several components, which in the worst case could lead to a slow O(n) query time complexity.

Another observation that seem helpful to address the described worst case is: there's at most 1 sub-graph to which 2 given articulation points may both belong to at the same time (I can prove this if needed), the observation easily leads to a worst case pre-processing space and time of O(n^2) (n is number of vertices), versus constant time queries, however O(n^2) preprocessing time is too slow (O(n^2) space is also too greedy). Can preprocessing be improved? a trade off of say log(n) query time expense would be fine.

Upvotes: 2

Views: 816

Answers (2)

Alexandru Barbarosie
Alexandru Barbarosie

Reputation: 3002

Having A as the adjacency matrix of the graph. A^l_{i,j} gives you the number of paths from i to j of length l. So A^l_{i,i} are the number of cycles for node i.

Precompute all A^l for l>=3. Let n_1, n_2, n_3 be the nodes. Assuming they are part of the same cycle then there exists a cycle from each of them of the same length. Hence check in the same A^l if A^l_{n_i, n_i} have at least one cycle. They can be in different cycles though. So for each l the before criteria satisfied, see if you can find such d_i, 1 <= i <= 3 between n_1 -> n_2 -> n_3 -> n_1 such that sum(d_i) = l. Since you already computed the set {A^l} doing that is rather easy.

Upvotes: 1

Nursultan Zarlyk
Nursultan Zarlyk

Reputation: 412

Let's partition your graph into several subgraphs, which has this property:

Every vertice in each subgraph belongs to some cycle and using this cycle you can travel to any vertice from this subgraph.

So you can check if three vertices belong to a cycle by checking if they belong to some subgraph. It can be done in O(log V)

So how can we partition such graph?

  1. Partition your graph into subgraphs (http://www.geeksforgeeks.org/bridge-in-a-graph/)
  2. Remove all edges considered as bridges
  3. Now you have several components. Every vertice that belongs to the same component, insert into the same set.

NOTE: As @ALTN mentioned this is not a correct solution. So maybe you must also partition each subgraph in articulation points. http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

Upvotes: 2

Related Questions