1
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I am not sure if it is necessary to first find all k-cycles, and then test one by one whether two vertices or two edges are on a specific k-cycle. $\endgroup$
    – licheng
    Apr 13, 2023 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.