pith. sign in

arxiv: 2604.23169 · v1 · submitted 2026-04-25 · 💻 cs.DS · math.CO

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

Takumi Kano , Yutaro Yamaguchi This is my paper

Pith reviewed 2026-05-08 07:31 UTC · model grok-4.3

classification 💻 cs.DS math.CO
keywords odd cyclelinear-time algorithmgroup-labeled graphundirected graphcycle through verticesparity constraintdeterministic algorithm
0
0 comments X

The pith

A deterministic linear-time algorithm finds an odd cycle through any two specified vertices in an undirected graph.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a deterministic linear-time algorithm for finding an odd cycle through two given vertices in an undirected graph. It proves this via a generalization: in any graph whose edges are labeled by elements of a group Γ where every element has order at most 2, one can decide in linear time whether two cycles through two specified vertices or edges carry distinct labels and output them when they exist. A sympathetic reader would care because the result gives an efficient way to handle parity and label-distinctness constraints on cycles, which appear in bipartiteness testing, network parity problems, and path-finding tasks. The linear-time guarantee means the method works on very large graphs without randomization or superlinear overhead.

Core claim

For any group Γ in which every element has order at most 2, given a Γ-labeled undirected graph together with two specified vertices or edges, it is possible to decide in linear time whether there exist two cycles through both that receive distinct labels and, if so, to output such cycles. The ordinary odd-cycle problem is recovered by taking Γ to be the two-element group under addition modulo 2.

What carries the argument

A Γ-labeling of the edges where every label g satisfies g² equal to the identity, which reduces the search for distinct-label cycles through two terminals to a parity-tracking search that can be solved by a single linear-time traversal.

If this is right

  • Any pair of vertices can be checked in linear time for the existence of an odd cycle containing both.
  • The same procedure decides the existence of two edge-disjoint cycles of opposite parity through two given edges.
  • The algorithm immediately yields a linear-time method for finding cycles whose labels differ by a prescribed nonzero group element.
  • Problems of detecting parity-constrained cycles through terminals become linear-time solvable under the order-2 restriction.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same linear-time technique might be lifted to dynamic graphs where edges are inserted or deleted while preserving the order-2 label condition.
  • One could test whether the result extends to finding three or more mutually label-distinct cycles through the same pair of terminals.
  • The approach suggests that many other small-order group-labeling problems on undirected graphs admit linear-time solutions once the order-2 property is present.
  • Applications to shortest-path or flow problems that track parity could be accelerated by substituting this subroutine for slower cycle searches.

Load-bearing premise

The input graph is undirected and every group element has order dividing 2.

What would settle it

An explicit undirected graph with two vertices that lie on an odd cycle, together with a run of the claimed algorithm that either reports no such cycle or exceeds linear time on that input.

Figures

Figures reproduced from arXiv: 2604.23169 by Takumi Kano, Yutaro Yamaguchi.

Figure 1
Figure 1. Figure 1: In particular, even though G − {e1, e2} contains a cycle on {x1, x2, 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 e1 and e2 has the same label 0. For precise definitions on group-labeled graphs, see Section 2.2. The proof of Theorem 1.3 in [1] is by a minimal-counterexample argument with an extremal choice of a non-zero c… view at source ↗
Figure 1
Figure 1. Figure 1: A triconnected counterexample for Theorem 1.3 when Γ = view at source ↗
Figure 2
Figure 2. Figure 2: The two possible configurations of the three linking paths view at source ↗
Figure 3
Figure 3. Figure 3: Illustration for Lemmas 4.5 and 4.6. Left: The situation of Lemma 4.5, and also view at source ↗
Figure 4
Figure 4. Figure 4: Illustration for Case 2. Left: The dashed path is view at source ↗
Figure 5
Figure 5. Figure 5: Illustration for Case 3. The dashed path is view at source ↗
Figure 6
Figure 6. Figure 6: Illustration for Case 4. The 2-fans do not share inner vertices with each other or view at source ↗
Figure 7
Figure 7. Figure 7: Illustration for Case 5. Left: Q1 is disjoint from V (C), and then Lemma 4.4 applies. Middle: Q1 contains at least two vertices on C, and there exist four distinct paths, so Lemma 4.5 applies. Right: Q1 contains exactly one vertex on C. We focus on this case below. V (C) \ {x1} with A = {vC, y1} and B = {x2, y2}, remove vC from one of the obtained paths, and use Lemma 2.1 if necessary); see view at source ↗
Figure 8
Figure 8. Figure 8: Illustration for Case 5. Left: R3 ∪ R4 splits C into two cycles at least one of which is non-zero. Middle: S1 ∪ S2 splits C into two cycles at least one of which is non-zero. Right: An x2–x1 path X together with R1, R3, R4, and P yields the conclusion. x1 z1 z2 C x2 x1 z1 z2 C x2 y2 x1 z1 z2 C view at source ↗
Figure 9
Figure 9. Figure 9: Illustration for Case 6. The dashed path view at source ↗
read the original 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$. 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript presents a deterministic linear-time algorithm for finding an odd cycle through two specified vertices in an undirected graph. This is shown via a generalization: for any group Γ in which every element has order at most 2, and a Γ-labeled graph with two specified vertices (or edges), the algorithm decides in linear time whether two cycles with distinct labels through both specified elements exist and constructs them if so.

Significance. If the central algorithmic claim and its proof hold, the result is significant. It delivers a deterministic linear-time solution to a non-trivial cycle-detection problem with parity constraints, using a reduction to finding two u-v paths with distinct Γ-labels (enabled by the exponent-2 property) followed by cycle reconstruction via parent pointers from a linear-time traversal. The generalization to arbitrary exponent-2 groups and the explicit handling of both vertex and edge specifications strengthen the contribution and provide a clean, parameter-free algorithmic result.

minor comments (1)
  1. The abstract states the result for both vertices and edges but does not indicate whether the edge case requires any additional handling in the traversal or label-cancellation steps; a brief clarifying sentence in the introduction would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review, detailed summary of our contribution, and recommendation to accept the manuscript. We are pleased that the significance of the deterministic linear-time algorithm and its generalization to exponent-2 groups was recognized.

Circularity Check

0 steps flagged

No significant circularity in algorithmic derivation

full rationale

The paper presents a new deterministic linear-time algorithm for detecting and constructing odd cycles through two vertices (generalized to Γ-labeled graphs with exponent dividing 2). The derivation chain consists of standard graph-search primitives (BFS/DFS traversals with parent pointers) combined with label-cancellation arguments that follow directly from the stated group property; these steps are self-contained, use only the input graph and the explicit structural assumption on Γ, and do not reduce to fitted parameters, self-definitional equations, or load-bearing self-citations. The result is an existence-plus-construction claim whose correctness is independently checkable from the described procedure.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard assumptions of undirected graph theory and the algebraic property that the labeling group is an elementary abelian 2-group; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption The input is an undirected graph (possibly with edge labels from a group Γ where g² = 1 for all g in Γ).
    Stated in the abstract as the setting for the algorithm.

pith-pipeline@v0.9.0 · 5371 in / 1246 out tokens · 54127 ms · 2026-05-08T07:31:09.033001+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Cycles through two edges in signed graphs.arXiv preprint arXiv:2306.05574, 2023

    Matt DeVos and Kathryn Nurse. Cycles through two edges in signed graphs.arXiv preprint arXiv:2306.05574, 2023

    work page arXiv 2023

  2. [2]

    Incremental planarity testing

    Giuseppe Di Battista and Roberto Tamassia. Incremental planarity testing. In30th Annual Symposium on Foundations of Computer Science, pages 436–441. IEEE, 1989

    work page 1989

  3. [3]

    Detecting cycles through three fixed vertices in a graph.Information Processing Letters, 42(1):29–33, 1992

    Herbert Fleischner and Gerhard J Woeginger. Detecting cycles through three fixed vertices in a graph.Information Processing Letters, 42(1):29–33, 1992

    work page 1992

  4. [4]

    Maximal flow through a network.Canadian Journal of Mathematics, 8:399–404, 1956

    Lester R Ford Jr and Delbert R Fulkerson. Maximal flow through a network.Canadian Journal of Mathematics, 8:399–404, 1956

    work page 1956

  5. [5]

    PhD thesis, Dortmund University of Technology, 2010

    Carsten Gutwenger.Application of SPQR-Trees in the Planarization Approach for Drawing Graphs. PhD thesis, Dortmund University of Technology, 2010

    work page 2010

  6. [6]

    A linear time implementation of SPQR-trees

    Carsten Gutwenger and Petra Mutzel. A linear time implementation of SPQR-trees. In International Symposium on Graph Drawing, pages 77–90. Springer, 2000

    work page 2000

  7. [7]

    Algorithm 447: efficient algorithms for graph manipu- lation.Communications of the ACM, 16(6):372–378, 1973

    John Hopcroft and Robert Tarjan. Algorithm 447: efficient algorithms for graph manipu- lation.Communications of the ACM, 16(6):372–378, 1973

    work page 1973

  8. [8]

    Dividing a graph into triconnected components.SIAM Journal on Computing, 2(3):135–158, 1973

    John Hopcroft and Robert Tarjan. Dividing a graph into triconnected components.SIAM Journal on Computing, 2(3):135–158, 1973

    work page 1973

  9. [9]

    PhD thesis, University of Waterloo, 2009

    Tony Chi Thong Huynh.The Linkage Problem for Group-Labelled Graphs. PhD thesis, University of Waterloo, 2009

    work page 2009

  10. [10]

    Finding a shortest non-zero path in group-labeled graphs.Combinatorica, 42(Suppl 2):1253–1282, 2022

    Yoichi Iwata and Yutaro Yamaguchi. Finding a shortest non-zero path in group-labeled graphs.Combinatorica, 42(Suppl 2):1253–1282, 2022

    work page 2022

  11. [11]

    The graph minor algorithm with parity conditions

    Ken-ichi Kawarabayashi, Bruce Reed, and Paul Wollan. The graph minor algorithm with parity conditions. In2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 27–36. IEEE, 2011

    work page 2011

  12. [12]

    Finding a path with two labels forbidden in group-labeled graphs.Journal of Combinatorial Theory, Series B, 143:65–122, 2020

    Yasushi Kawase, Yusuke Kobayashi, and Yutaro Yamaguchi. Finding a path with two labels forbidden in group-labeled graphs.Journal of Combinatorial Theory, Series B, 143:65–122, 2020

    work page 2020

  13. [13]

    Zur allgemeinen kurventheorie.Fundamenta Mathematicae, 10(1):96–115, 1927

    Karl Menger. Zur allgemeinen kurventheorie.Fundamenta Mathematicae, 10(1):96–115, 1927

    work page 1927

  14. [14]

    Graph minors

    Neil Robertson and Paul D Seymour. Graph minors. XIII. the disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995

    work page 1995

  15. [15]

    Springer, 2003

    Alexander Schrijver.Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. 15

    work page 2003