pith. sign in

arxiv: 2606.21103 · v1 · pith:3T75TDL6new · submitted 2026-06-19 · 💻 cs.CC

On the Reachability Problem on Monoid-Labelled Undirected Graphs

Nagashri Krishnakumar , Harshil Mittal , Jayalal Sarma This is my paper

Pith reviewed 2026-06-26 12:56 UTC · model grok-4.3

classification 💻 cs.CC
keywords labelled reachabilitymonoid-labelled graphsundirected graphsspace complexityL versus NLGreen's relationsunion-of-groups monoidscommutative monoids
0
0 comments X

The pith

Commutative monoids place monoid-labelled undirected reachability in L for every accepting set.

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

The labelled reachability problem asks whether there exists a walk from s to t in an undirected graph whose sequence of monoid labels multiplies to an element of a fixed set F. The paper fixes F rather than treating it as input and obtains tighter space bounds than prior work on groups and aperiodic monoids. It proves that the problem lies in L whenever the sole acceptor is the monoid identity, that it lies in L for every F when the monoid is commutative, and that the same holds for L(R)-commutative union-of-groups monoids. For the concrete monoids BA2 and U it establishes a clean split: every possible F yields either an L algorithm or an NL-complete problem.

Core claim

For any finite monoid M the labelled reachability problem is in L when the accepting element is the identity of M. For any commutative monoid M the problem is in L for all Fsubseteq M. For any L(R)-commutative union-of-groups monoid M the problem is in L for all F. For the monoids BA2 and U the problem is either NL-complete or in L for every F. The proofs rest on the link between Green's relations in UoG monoids and the connectivity of the product graph.

What carries the argument

The product graph whose vertices and edges encode pairs of monoid elements and whose connectivity, via Green's relations, decides the existence of a labelled walk from s to t.

If this is right

  • Logspace algorithms exist for the problem under every fixed acceptor once the monoid is commutative.
  • The algebraic properties of the monoid (commutativity, L/R-commutativity, Green's relations) directly control the space complexity.
  • Complete dichotomies become possible for small monoids such as BA2 and U, classifying every possible acceptor.
  • Deterministic logspace suffices for many monoid-labelled path problems on undirected graphs without needing nondeterminism.

Where Pith is reading between the lines

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

  • Algebraic features of the label monoid can be read off the graph to decide which algorithm to run.
  • The same product-graph technique may classify complexity for other fixed label structures such as semirings.
  • The L versus NL boundary for reachability variants is refined by fixing the acceptor rather than allowing it to vary.
  • Practical implementations could pre-compute the product graph for a given monoid and then run ordinary connectivity.

Load-bearing premise

The product graph's connectivity, mediated by Green's relations, correctly decides whether any labelled walk multiplies into the given accepting set.

What would settle it

A concrete commutative monoid together with an accepting set F for which the labelled reachability problem requires more than logarithmic space, or an F in BA2 whose complexity lies strictly between L and NL-complete.

Figures

Figures reproduced from arXiv: 2606.21103 by Harshil Mittal, Jayalal Sarma, Nagashri Krishnakumar.

Figure 1
Figure 1. Figure 1: This figure shows R-classes and H-classes of the union-of-groups monoid End(2P2) marked with dashed and solid boxes respectively. The idempotent elements are marked with ∗. The bottom box is the unit group. Note that R-classes do not coincide with H-classes and so, End(2P2) is not L-commutative. Also, observe that the two R-classes outside the unit group are right ideals. However, in this case, the two R-c… view at source ↗
Figure 2
Figure 2. Figure 2: Overview of inclusions amongst certain sub-classes of union-of-groups monoids. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Path re-visiting the V × H part Proof. It suffices to show that the in-degree of any vertex matches its out-degree in G′ [V × H]. Consider any (v, h) ∈ V × H. Note that the only edges of G due to which edges get added (in the product graph G′ ) at the vertex (v, h) ∈ V × H are the ones incident to the vertex v in G. Also, for any two such distinct edges (say, {v, w} and {v, w′}, where w and w ′ are distinc… view at source ↗
read the original abstract

The labelled reachability problem for undirected graphs with edges labelled by elements of a monoid $M$ (more generally, groupoids or magmas) captures the classes $\sf{L}$ and $\sf{NL}$. Given a graph $G(V, E)$ labelled by $\phi~\colon E \to M$, $s,t \in V$ and an accepting subset $F \subseteq M$, the problem asks to test whether there is a walk $P$ from $s$ to $t$ in $G$ where $\phi(P) \in F$. Ramaswamy et al. (2019) studied the variant where the accepting element is part of the input for aperiodic monoids and groups. Motivated by the success in designing space-bounded algorithms for the undirected graph reachability problem, we study the labelled reachability problem when the accepting set is also fixed. This reveals finer complexity bounds and dichotomies for the problem based on the monoid and the accepting set. Previous results imply that the problem is in $\sf{L}$ for any finite accepting subset when $M$ is a group or belongs to $\sf{DA}$. We prove the following (for finite monoids): 1) For any monoid $M$, the problem is in $\sf{L}$ when the accepting element is the identity of $M$. If the accepting element is an idempotent, under suitable constraints, the problem is $\sf{NL}$-hard. 2) For any commutative monoid $M$, the problem is in $\sf{L}$ for all $F \subseteq M$. 3) For any $\mathcal{L}(\mathcal{R})$-commutative union-of-groups (UoG) monoid $M$, the problem is in $\sf{L}$ for all $F\subseteq M$. We show deterministic logspace algorithms for UoG monoids that are neither $\mathcal{L}$-commutative nor $\mathcal{R}$-commutative, under certain constraints. 4) For the monoids $\sf{BA_2}$ and $\sf{U}$, we show a dichotomy: for all $F \subseteq M$, the problem is either $\sf{NL}$-complete or in $\sf{L}$. Our results exploit the connection between Green's relations in the UoG monoids and the properties of the product graph (a graph introduced by Ramaswamy et al. (2019)).

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 / 3 minor

Summary. The paper studies the labelled reachability problem on undirected graphs with edges labelled by a finite monoid M (with fixed accepting set F ⊆ M). It claims that the problem lies in L for every finite monoid when the accepting element is the identity; lies in L for every F when M is commutative; lies in L for every F when M is an L(R)-commutative union-of-groups monoid; and, for the concrete monoids BA₂ and U, exhibits a dichotomy in which every F yields either NL-completeness or membership in L. All results are obtained by relating Green's relations on UoG monoids to connectivity properties of the product graph introduced by Ramaswamy et al. (2019).

Significance. If the stated theorems hold, the work supplies a finer classification of a natural labelled generalisation of undirected s-t connectivity, extending the known L-membership results for groups and DA monoids to commutative monoids, L(R)-commutative UoG monoids, and two explicit non-commutative examples. The explicit deterministic logspace algorithms for several families and the clean dichotomy for BA₂ and U constitute concrete, falsifiable contributions to the study of space-bounded computation on labelled graphs.

minor comments (3)
  1. The abstract states that the identity case holds for any finite monoid while the idempotent case is NL-hard 'under suitable constraints'; the precise constraints and the section in which they are proved should be stated explicitly already in the abstract.
  2. The product-graph construction is invoked throughout; a self-contained definition (or a precise pointer to the 2019 reference) in §2 would improve readability for readers who have not internalised the earlier paper.
  3. Notation for Green's relations (ℒ, ℛ, 𝒟, etc.) and for the monoids BA₂ and U is used without a preliminary table or diagram; adding one would help readers track the case distinctions in §4 and §5.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our work and for recommending minor revision. No major comments were raised in the report, so we have no point-by-point responses to provide at this time. We will incorporate any minor suggestions during the revision process.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's results on labelled reachability for monoids (L for identity acceptor in any finite M; L for all F in commutative M; L for all F in L(R)-commutative UoG M; dichotomy for BA2 and U) are derived via new reductions and algorithms that connect Green's relations to the product graph construction introduced in external prior work (Ramaswamy et al. 2019). No equation or step reduces a claimed prediction or theorem to a fitted input, self-definition, or load-bearing self-citation chain; the central claims retain independent content from the cited external construction and the paper's own case analysis for the listed monoid classes. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on the standard definition of monoids, the definition of Green's relations, and the correctness of the product-graph construction from prior work; no new free parameters or invented entities are introduced.

axioms (2)
  • standard math A monoid is a set equipped with an associative binary operation and an identity element.
    Invoked throughout the problem definition and all stated theorems.
  • domain assumption Green's relations capture the structural properties of elements in finite monoids that determine reachability in the product graph.
    Explicitly cited as the bridge between algebra and graph connectivity in the final paragraph.

pith-pipeline@v0.9.1-grok · 5995 in / 1421 out tokens · 23159 ms · 2026-06-26T12:56:59.836187+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

57 extracted references · 10 canonical work pages

  1. [1]

    I , author=

    On the theory of epigroups. I , author=. Russian Academy of Sciences. Sbornik Mathematics , volume=

  2. [2]

    Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007, Proceedings , series =

    Eric Allender , title =. Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007, Proceedings , series =

    2007

  3. [3]

    Proceedings of the National Academy of Sciences , volume=

    The word problem , author=. Proceedings of the National Academy of Sciences , volume=

  4. [4]

    American Mathematical Society Translations, Series 2 , volume =

    Novikov, Petr Sergeevich , year=. American Mathematical Society Translations, Series 2 , volume =

  5. [5]

    2001 , publisher=

    Nagy, Attila , volume=. 2001 , publisher=

    2001

  6. [6]

    Semigroup Forum , volume=

    Mary, Xavier , booktitle=. Semigroup Forum , volume=. 2014 , organization=

    2014

  7. [7]

    Amplifying lower bounds by means of self-reducibility , journal =

    Eric Allender and Michal Kouck. Amplifying lower bounds by means of self-reducibility , journal =

  8. [8]

    Noga Alon and Oded Schwartz and Asaf Shapira , title =. Comb. Probab. Comput. , volume =

  9. [9]

    Electron

    Omer Reingold , title =. Electron. Colloquium Comput. Complex. , volume =

  10. [10]

    Karp and Richard J

    Romas Aleliunas and Richard M. Karp and Richard J. Lipton and L. Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems , booktitle =. 1979 , url =. doi:10.1109/SFCS.1979.34 , timestamp =

    work page doi:10.1109/sfcs.1979.34 1979

  11. [11]

    Bridgland , title =

    Michael F. Bridgland , title =. Journal of Algorithms , volume =. 1987 , url =. doi:10.1016/0196-6774(87)90019-8 , timestamp =

    work page doi:10.1016/0196-6774(87)90019-8 1987

  12. [12]

    Log-space constructible universal traversal sequences for cycles of length O(n^

    Michal Kouck. Log-space constructible universal traversal sequences for cycles of length O(n^. Theoretical Computer Science , volume =

  13. [13]

    Polynomial Universal Traversing Sequences for Cycles Are Constructible (Extended Abstract) , booktitle =

    Sorin Istrail , editor =. Polynomial Universal Traversing Sequences for Cycles Are Constructible (Extended Abstract) , booktitle =

  14. [14]

    Karloff and Ramamohan Paturi and Janos Simon , title =

    Howard J. Karloff and Ramamohan Paturi and Janos Simon , title =. Information Processing Letters , volume =

  15. [15]

    Ruzzo and Martin Tompa , title =

    Allan Borodin and Walter L. Ruzzo and Martin Tompa , title =. Journal of Computer and System Sciences , volume =

  16. [16]

    Ruzzo and Martin Tompa , title =

    Paul Beame and Allan Borodin and Prabhakar Raghavan and Walter L. Ruzzo and Martin Tompa , title =. Information and Computation , volume =

  17. [17]

    Universal traversal sequences with backtracking , journal =

    Michal Kouck. Universal traversal sequences with backtracking , journal =. 2002 , url =. doi:10.1016/S0022-0000(02)00023-5 , timestamp =

    work page doi:10.1016/s0022-0000(02)00023-5 2002

  18. [18]

    Universal Traversal Sequences for Arbitrarily Labeled Graphs , author=

  19. [19]

    2003 , note=

    On traversal and exploration sequences , author=. 2003 , note=

    2003

  20. [20]

    On Traversal Sequences, Exploration Sequences, and Completeness and Kolmogorov Random Strings

    Michal Kouck. On Traversal Sequences, Exploration Sequences, and Completeness and Kolmogorov Random Strings. 2003

    2003

  21. [21]

    2000 , url =

    Klaus Reinhardt and Eric Allender , title =. 2000 , url =. doi:10.1137/S0097539798339041 , timestamp =

    work page doi:10.1137/s0097539798339041 2000

  22. [22]

    Kallampally and Raghunath Tewari , editor =

    Vivek Anand T. Kallampally and Raghunath Tewari , editor =. Trading Determinism for Time in Space Bounded Computations , booktitle =. 2016 , url =. doi:10.4230/LIPIcs.MFCS.2016.10 , timestamp =

    work page doi:10.4230/lipics.mfcs.2016.10 2016

  23. [23]

    Vidhya Ramaswamy and Jayalal Sarma and K. S. Sunil , title =. Journal of Computer and System Sciences , volume =

  24. [24]

    Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2006) , pages =

    Reingold, Omer and Trevisan, Luca and Vadhan, Salil , title =. Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2006) , pages =. 2006 , isbn =

    2006

  25. [25]

    Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs , journal =

    L. Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs , journal =

  26. [26]

    Combinatorica , volume =

    Noam Nisan , title =. Combinatorica , volume =

  27. [27]

    Information Processing Letters , volume =

    Shlomo Hoory and Avi Wigderson , title =. Information Processing Letters , volume =

  28. [28]

    1988 , publisher=

    Barrington, David A Mix and Therien, Denis , journal=. 1988 , publisher=

    1988

  29. [29]

    Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC 1983) , pages=

    Unbounded fan-in circuits and associative functions , author=. Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC 1983) , pages=

    1983

  30. [30]

    Barrington, David A , booktitle=

  31. [31]

    Lewis and Christos H

    Harry R. Lewis and Christos H. Papadimitriou , title =. Theor. Comput. Sci. , volume =

  32. [32]

    Bounds on Universal Sequences , journal =

    Amotz Bar. Bounds on Universal Sequences , journal =

  33. [33]

    Chris Bourke and Raghunath Tewari and N. V. Vinodchandran , title =. 2009 , url =. doi:10.1145/1490270.1490274 , timestamp =

    work page doi:10.1145/1490270.1490274 2009

  34. [34]

    1997 , isbn =

    Michael Sipser , title =. 1997 , isbn =

    1997

  35. [35]

    Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness , booktitle =

    Venkatesan Guruswami and Xin Lyu and Xiuhan Wang , editor =. Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness , booktitle =. 2022 , url =. doi:10.4230/LIPIcs.APPROX/RANDOM.2022.20 , timestamp =

    work page doi:10.4230/lipics.approx/random.2022.20 2022

  36. [36]

    Oliver Korten , title =. 62nd. 2021 , url =. doi:10.1109/FOCS52979.2021.00051 , timestamp =

    work page doi:10.1109/focs52979.2021.00051 2021

  37. [37]

    Aduri Pavan and Raghunath Tewari and N. V. Vinodchandran , title =. Comput. Complex. , volume =. 2012 , url =. doi:10.1007/s00037-012-0047-3 , timestamp =

    work page doi:10.1007/s00037-012-0047-3 2012

  38. [38]

    UL problem

    Algebraic weighting schemes and the NL vs. UL problem. 2017

    2017

  39. [39]

    and Merz, Sarah , year =

    Langley, Larry and Lundgren, J. and Merz, Sarah , year =

  40. [40]

    2012 , issn =

    The competition number of a graph and the dimension of its hole space , journal =. 2012 , issn =. doi:https://doi.org/10.1016/j.aml.2011.10.003 , author =

    work page doi:10.1016/j.aml.2011.10.003 2012

  41. [41]

    2024 , archivePrefix=

    Deciding Reachability in a Directed Graph given its Path Decomposition , author=. 2024 , archivePrefix=

    2024

  42. [42]

    Reachability Problems and Space Bounds. 2017

    2017

  43. [43]

    Komarath, Balagopal and Sarma, Jayalal and Sunil, K. S. Descriptional Complexity of Formal Systems (DCFS 2014). 2014

    2014

  44. [44]

    Lyapin, E. S. , title =. 1963 , address =

    1963

  45. [45]

    Advances in Mathematics , volume=

    A group-theoretical interpretation of the word problem for free idempotent generated semigroups , author=. Advances in Mathematics , volume=. 2019 , publisher=

    2019

  46. [46]

    J. A. Green , journal =. On the Structure of Semigroups , urldate =

  47. [47]

    1961 , publisher=

    The Algebraic Theory of Semigroups, Volume I , author=. 1961 , publisher=

    1961

  48. [48]

    D. D. Miller and A. H. Clifford , journal =. Regular D-Classes in Semigroups , urldate =

  49. [49]

    Pacific Journal of Mathematics , volume =

    Yamada, Miyuki , title =. Pacific Journal of Mathematics , volume =

  50. [50]

    Theory of Computing Systems , volume=

    Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups , author=. Theory of Computing Systems , volume=

  51. [51]

    Pin, Jean-Eric , year=

  52. [52]

    1995 , publisher=

    Fundamentals of Semigroup Theory , author=. 1995 , publisher=

    1995

  53. [53]

    Some results on

    Gigo. Some results on. Semigroup Forum , year =

  54. [54]

    Pascal Tesson , title =

  55. [55]

    Language and Automata Theory and Applications (LATA 2011) , series =

    Thomas Colcombet , title =. Language and Automata Theory and Applications (LATA 2011) , series =

    2011

  56. [56]

    Margolis and Jean-Eric Pin , title =

    Stuart W. Margolis and Jean-Eric Pin , title =. Pacific Journal of Mathematics , volume =

  57. [57]

    2016 , publisher=

    Pipattanajinda, Nirutt and Knauer, Ulrich and Gyurov, Boyko and Panma, Sayan , journal=. 2016 , publisher=

    2016