3
$\begingroup$

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 three 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.

Preprocessing should be efficient as well (ideally less than $O(m^2)$ both time and space) where $m$ is the number of edges.

Edit: The cycle is simple (no vertex in the cycle is repeated)

Edit2: My progress so far 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 for a trade off of maybe log(n) query time expense?

$\endgroup$
  • 2
    $\begingroup$ The trivial answer would be "Pre-process by computing the answer for all $\binom{n}{3}$ triples and then solve the queries by table lookup", so I guess you're looking for some sort of trade-off between cost of preprocessing and cost of querying. (Sorry for making points one at a time -- that wasn't my intention!) $\endgroup$ – David Richerby Jun 18 '17 at 13:15
  • 1
    $\begingroup$ If instead of 3 nodes you had 2 nodes, the answer would be to calculate biconnected components. Perhaps here you need to calculate the triconnected components. $\endgroup$ – Yuval Filmus Jun 18 '17 at 13:40
  • 1
    $\begingroup$ en.wikipedia.org/wiki/SPQR_tree $\endgroup$ – Evil Jun 18 '17 at 13:48
  • 1
    $\begingroup$ Do you require a simple cycle (i.e., no vertex in the cycle is repeated), or are you OK with repeated vertices? If the latter, what's wrong with computing connected components? Can you edit the question to clarify so people don't need to read the comments to understand the question? $\endgroup$ – D.W. Jun 18 '17 at 15:02
  • 1
    $\begingroup$ @Evil if my understanding is correct SPQR trees are used to determine whether a component is triconnected, which is not a necessary condition for the query I described in the question (see my comment above). $\endgroup$ – ALTN Jun 18 '17 at 15:21

Your Answer

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

Browse other questions tagged or ask your own question.