# How to determine if two vertices (or two edges) fall on a cycle of a specific length?

A walk is a finite or infinite sequence of edges which joins a sequence of vertices. A trail is a walk in which all edges are distinct. A cycle in a graph is a non-empty trail in which only the first and last vertices are equal.

We know that determining whether two vertices (or two edges) fall on a triangle is relatively easy. However, I am not sure if there are any algorithms for general k-cycles. That is to say, I would like to determine whether two given vertices (or two edges) fall on a cycle of a specific length.

I am not aware of the existence or complexity of such an algorithm. However, I think if the length of the cycle is equal to the order of a graph, it must be NP-hard, because determining whether a graph is Hamiltonian is NP-hard.

If $$k$$ is an input, and the cycle is not allowed to repeat vertices, then as you say, the problem is NP-hard, as it is at least as hard as the Hamiltonian cycle problem (simply set $$k$$ equal to the number of vertices in the graph).
If $$k$$ is fixed and small and the cycle is not allowed to repeat vertices, I believe the problem can be solved in polynomial time (but exponential in $$k$$) by adapting the methods in https://cstheory.stackexchange.com/q/19508/5038.
If the cycle is allowed to repeat vertices and edges, then the problem is easy to solve. Let $$A$$ denote the adjacency matrix, so that $$A_{ij}=1$$ if there is an edge $$(i,j)$$ in the graph and 0 otherwise. Note that $$A^n$$ can be computed efficiently using matrix multiplication, and $$(A^n)_{ij}$$ counts the number of (non-simple) walks from $$i$$ to $$j$$ of length $$n$$ (where vertices and/or edges can be repeated). It follows that vertices $$i,j$$ are on the same cycle iff there exists $$\ell$$ such that $$(A^\ell)_{ij}>0$$ and $$(A^{k-\ell})_{ji}>0$$. This gives an efficient algorithm for your problem in this case.