A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices

Takumi Kano, Yutaro Yamaguchi · 2026

Read A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices by Takumi Kano, Yutaro Yamaguchi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-23169.txt.

Introduction

Kano and Yamaguchi give a deterministic linear-time method to find an odd or even cycle through two chosen vertices of an undirected graph. They prove a wider claim for any group where every element has order at most two. For any graph labelled by that group, one can test in linear time whether two cycles with distinct labels pass through both chosen vertices or edges. When such cycles exist, the method finds them. The result turns a parity-flavoured cycle question into a fast, exact graph procedure.

Catalog record

CREATORTakumi Kano, Yutaro Yamaguchi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50406
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.23169

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices Takumi Kano, Yutaro Yamaguchi Abstract We present a deterministic linear-time algorithm for finding an odd cycle through two specified vertices in an undirected graph. This is shown in a generalized form as follows: Let Γ \Gamma be any group in which every element is of order at most 2 2 . For a given Γ \Gamma -labeled graph with two specified vertices (or edges), we can determine in linear time whether there exist two cycles with distinct labels that are through both of the two specified vertices (or edges), and find such cycles if yes. Keywords: Cycle through three vertices, Group-labeled graphs, Non-zero cycle, SPQR-tree 1 Introduction In this paper, we show the following: Theorem 1.1 . There exists a deterministic algorithm to find an odd cycle through two specified vertices in a given undirected graph that runs in \mathrm{O}(n+m) time, where n and m denote the numbers of vertices and of edges in the input graph, respectively. This extends a linear-time algorithm for finding a cycle through three specified vertices in a given undirected graph [ 3 ] . To see this, let G be an undirected graph, and x,y,z be three distinct vertices in G . We construct from G an auxiliary graph \tilde{G} as follows: subdivide each edge in G with exactly one extra vertex in the middle, split the vertex z into two copies z_{1} and z_{2} with the same neighbor as the original z , and add an extra edge between z_{1} and z_{2} . Then, a cycle in \tilde{G} is odd if and only if it is through the extra edge \{z_{1},z_{2}\} . Thus, an odd cycle through both x and y in \tilde{G} corresponds to a cycle through all of x , y , and z in G . In order to prove Theorem 1.1 , we actually solve a more general problem in group-labeled graphs, which is formally defined in Section 2.2 . Our main theorem is stated as follows: Theorem 1.2 . Let \Gamma be a group in which every element is of order at most 2 (i.e., self-inverse). There exists a deterministic algorithm to determine whether the label of a cycle through two specified vertices (or two specified disjoint edges) in a given biconnected \Gamma -labeled graph is unique or not in \mathrm{O}(n+m) time. Moreover, if it is not unique, the algorithm outputs two such cycles with distinct labels. The assumption that every element of \Gamma is of order at most 2 is essential. For signed graphs, that is, for \Gamma=\mathbb{Z}_{2}=\mathbb{Z}/2\mathbb{Z} , DeVos and Nurse [ 1 ] recently gave a structural characterization of when there exist two cycles passing through two specified edges whose signs are different. This characterization (in a rephrased form) plays a key role in our algorithm, for which we give a constructive proof with an efficient algorithm (see Section 4 ). Theorem 1.3 (DeVos and Nurse [ 1 ] (rephrased)) . Let G be a triconnected \mathbb{Z}_{2} -labeled graph, and e_{1},e_{2}\in E(G) be disjoint edges that have no parallel edges. Then, G contains two cycles passing through both e_{1} and e_{2} with distinct labels if and only if G-\{e_{1},e_{2}\} contains a non-zero cycle of length at least three. Indeed, this characterization fails already for triconnected \mathbb{Z}_{3} -labeled graphs, as shown in Figure 1 . In particular, even though G-\{e_{1},e_{2}\} contains a cycle on \{x_{1},x_{2},w,v,u\} with label 2-1+0+0+0=1 , which is non-zero, it may still happen that every cycle through the distinguished edges e_{1} and e_{2} has the same label 0 . For precise definitions on group-labeled graphs, see Section 2.2 . Figure 1: A triconnected counterexample for Theorem 1.3 when \Gamma=\mathbb{Z}_{3} . The solid edges are directed and labeled by elements of \mathbb{Z}_{3} ; the label of a walk is the signed sum of the traversed edge labels, taking sign +1 when the walk follows the chosen direction and sign -1 otherwise (see Section 2.2 for more details). The proof of Theorem 1.3 in [ 1 ] is by a minimal-counterexample argument with an extremal choice of a non-zero cycle. Thus, it does not provide a fast algorithm to find explicit witness cycles even for \mathbb{Z}_{2} -labeled graphs. Our main contribution is showing Theorem 1.2 , which gives a linear-time algorithm to find target cycles for a more general class of group-labeled graphs. We should remark that a polynomial-time algorithm for our problem (when |\Gamma| is constant) can be derived from [ 9 , 11 ] . In [ 11 ] , Kawarabayashi, Reed, and Wollan gave an \mathrm{O}(mn\cdot\alpha(m,n)) -time algorithm for finding k vertex-disjoint paths in a given undirected graph between k specified pairs of vertices with a specified parity of each path for any fixed k . It is not difficult to see that, by taking k=2 and checking all of 2^{2}=4 patterns of parities for each element of a fixed generating set of \Gamma , we can solve our problem via this setting. In [ 9 ] , Huynh also provided a polynomial-time algorithm for finding k vertex-disjoint paths in a given \Gamma -labeled graph between k specified pairs of vertices with a specified label for any fixed k and a constant-size group \Gamma . A similar reduction works for this setting. Nevertheless, their algorithms are on the top of the sophisticated graph minor theory initiated by Robertson and Seymour (in particular, [ 14 ] ) and do not achieve linear-time computation. The advantage of our algorithm is that it is rather elementary and runs in linear time. 2 Preliminaries In this section, we provide necessary definitions, related concepts, and basic facts used in this paper. Throughout the paper, graphs may have parallel edges, but have no self-loops. 2.1 Graphs Let G=(V,E) be an undirected graph. An alternating sequence W=(v_{0},e_{1},v_{1},\dots,e_{\ell},v_{\ell}) of vertices and edges in G is called a walk in G if e_{i}=\{v_{i-1},v_{i}\}\in E for every i=1,2,\dots,\ell . We call \ell the length of W , and we say that W is odd and even if \ell is odd and even, respectively. We say that W is a path if all its vertices v_{0},v_{1},\dots,v_{\ell} are distinct, and a cycle if \ell\geq 2 , almost all its vertices v_{1},\dots,v_{\ell} are distinct, v_{0}=v_{\ell} , and e_{1}\neq e_{\ell} . In particular, a walk of length zero is regarded as a path, which is called trivial , and a walk consisting of two distinct parallel edges is regarded as a cycle. A path is referred to as a v_{0} – v_{\ell} path (or an X – Y path when v_{0}\in X and v_{\ell}\in Y ) if the end vertices are emphasized. We denote by P[v_{i},v_{j}] the subpath of a path P from v_{i} to v_{j} , where the direction is flipped accordingly. We say that G is connected if every pair of vertices, say s,t\in V , there exists an s – t path in G . For each integer k\geq 1 , a k -cut is a vertex set X\subseteq V with |X|\leq k such that its removal results in a disconnected graph G-X . For k\geq 2 , we say that G is k -connected if |V|>k and it has no

Read the complete text