On the Reachability Problem on Monoid-Labelled Undirected Graphs

arXiv:2606.21103 · cs.CC · Submitted 2026-06-19 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "On the Reachability Problem on Monoid-Labelled Undirected Graphs".

Jane: Here's the gist of the paper. The labelled reachability problem for undirected graphs where edges are labelled with elements from a monoid M is known to capture space-bounded complexity classes L and NL Given a labelled graph G(V, E) (labelled with ϕ: E → M), s, t ∈ V and an accepting subset F ⊆ M, the problem asks to test whether there is a walk P from s to t in G where ϕ(P) ∈ F When the accepting element is also part of the input, the problem has been studied by Ramaswamy et al (2019)

RSS19: Motivated by the success in designing space-bounded algorithms for the graph reachability problem in the undirected case, we study the labelled reachability problem when the accepting set is also fixed In fact, when the monoid M is a group or belongs to the monoid pseudovariety DA, the previous results imply a deterministic logspace algorithm for the undirected labelled reachability problem over the monoid M for any finite accepting subset as well Problem Formulation and Key Results The paper defines the monoid reachability problem REACHM,F as testing whether there is a walk P from s to t in an undirected graph G where the edge labels ϕ(P) ∈ F The authors establish several deterministic logspace algorithms based on the structure of the monoid M and the accepting set F)&For any finite monoid M, there is a deterministic logspace algorithm for solving the above problem when the accepting element is the identity of M In contrast, if the accepting element is an idempotent element, under suitable constraints, the problem is NL-hard)&Considering the more general case of the problem when the accepting set is an arbitrary subset of M, we show a deterministic logspace algorithm for a commutative monoid M for all accepting sets F ⊆ M)&Further, we prove that for any finite L-commutative or R-commutative union-of-groups monoid M, there is a deterministic logspace algorithm for all accepting sets F ⊆ M Reachability with Specific Accepting Elements The paper investigates reachability when the accepting set is restricted to specific elements of the monoid M)&For any fixed finite monoid M, let G˜ denote the unit group of M.

Tom: Then, REACHM,F can be solved using a deterministic logspace algorithm for all accepting sets F ⊆ G˜ (and so, in particular, when F = id, where id denotes the identity of M))&Consider any fixed finite union-of-groups monoid M.

Jane: Let G˜ denote the unit group (i.e., the H-class containing the monoid identity id) of M.

Tom: Then, REACHM,F can be solved using a deterministic logspace algorithm for all accepting sets F ⊆ G˜)&Consider any fixed finite aperiodic monoid M with monoid identity id.

Title and authors: Tom: Let's talk about the title and who wrote this, "On the Reachability Problem on Monoid-Labelled Undirected Graphs." It sounds like it’s focusing specifically on how adding monoid labels messes with graph reachability.

Jane: And Nagashri Krishnakumar, Harshil Mittal, and Jayalal Sarma are the authors. They seem to be digging into the structure of these monoids to figure out the complexity bounds.

Lu: The paper immediately sets up a framework where they analyze how different types of monoids—like groups or pseudovarieties—affect whether you can get a deterministic logspace algorithm for this reachability problem when the accepting set F is fixed.

Meng: So, if the monoid structure is simple enough, like when it’s a group or in that pseudovariety DA, they claim there's an L-time deterministic solution for any finite accepting set F. That’s a big claim for practical deployment because we need algorithms that work fast and use little memory.

Lalam: They are also looking at what happens when the monoid is something more complex, like when it’s aperiodic, which leads to some interesting results about NL-hardness under certain conditions.

The paper's summary: Tom: The paper summarizes that they establish several deterministic logspace algorithms depending on the properties of the monoid M and the accepting set F. It breaks things down based on what kind of monoid we are dealing with.

Jane: They find that for any finite monoid M, if we fix the accepting element to be the identity of M, they can solve it in deterministic logspace. But if that element is idempotent, things get much harder and it becomes NL-hard under certain constraints.

Lu: For a more general case with an arbitrary accepting set F, they show they have deterministic logspace algorithms for commutative monoids and for L-commutative or R-commutative union-of-groups monoids.

Meng: That’s useful because it tells us exactly which structures of the label space allow us to keep the memory usage low, which is crucial when we try to deploy these reachability checks on massive graphs.

Lalam: They also have specific results for when the accepting set is restricted to elements within the unit group Gtilde, or when dealing with union-of-groups monoids where all non-unit classes are right ideals.

The paper's improvements: Tom: One key improvement they point out is that for any finite monoid M, if we focus only on the unit group Gtilde, we can solve the problem for any accepting set F within that group using a deterministic logspace algorithm.

Jane: That means if you can reduce the label constraints to just the invertible elements of the monoid, you get a deterministic logspace solution regardless of what F is. That’s a significant simplification for computation.

Lu: They also show that for specific non-commutative building blocks like BA2 and U, they prove a dichotomy theorem: either the problem is NL-complete or it's in L, no matter what the accepting set F is.

Meng: That dichotomy is powerful because it gives us a clear complexity ceiling for those specific monoids—we know exactly where we stand in terms of space efficiency.

Lalam: And they also show that for certain union-of-groups monoids, if the non-unit classes are right ideals, we can solve it when the accepting set F is one of those other classes, not just the unit group.

Conclusion: Tom: So to wrap up on "On the Reachability Problem on Monoid-Labelled Undirected Graphs," they’ve shown that the difficulty hinges entirely on whether you are dealing with a group structure or a more complex monoid structure, and how the accepting set F interacts with that.

Jane: The big implication is that for many common structures, like commutative monoids, we can indeed find deterministic logspace solutions for reachability problems even when the label constraints seem arbitrary at first glance.

Lu: They proved that this structure-based analysis allows them to derive concrete complexity results, moving beyond just saying it's in L or NL without a specific structural reason why.

Meng: For someone trying to deploy an AI system that checks reachability under these constraints, knowing which monoid class your labels fall into tells you instantly if you can rely on a fast, low-memory algorithm or if you need something else entirely.

Lalam: The paper confirms that the structure of the monoid is the controlling factor here, and they've mapped out exactly when we can expect deterministic logspace algorithms for arbitrary accepting sets F.

Indian Institute of Technology Madras, Chennai, India

cs.CC

Submitted: 2026-06-19

Updated: 2026-11-12

Comments: Changes in new version: Weakened the statement of Theorem 1.2 and modified Theorem 1.6 as pointed out by a reviewer. The applicability of the theorems do not change. We have made modifications to the presentation of the paper by moving the earlier Remark 3.1 and Proposition 3.1 to a new section - See Section 3.3

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: The labelled reachability problem for undirected graphs where edges are labelled with elements from a monoid M is known to capture space-bounded complexity classes L and NL Given a labelled graph…

Key concepts

REACHM,F
This is the problem being studied: determining if there is a walk between two vertices in an undirected graph where the sequence of edge labels along that walk belongs to a specified accepting set F of the monoid M.
Monoid Structure (M)
The algebraic structure of the monoid M, such as whether it is commutative or a union-of-groups monoid, dictates the complexity of solving REACHM,F. Different structures allow for different algorithmic solutions, ranging from deterministic logspace to NL-hardness.
Deterministic Logspace Algorithm
An algorithm that solves a problem using only a limited amount of memory (logarithmic space relative to the input size). The paper proves that for certain monoid structures and accepting sets, this efficient solution exists for the reachability problem.

Terminology

Summary

The labelled reachability problem for undirected graphs where edges are labelled with elements from a monoid M is known to capture space-bounded complexity classes L and NL Given a labelled graph G(V, E) (labelled with ϕ: E → M), s, t ∈ V and an accepting subset F ⊆ M, the problem asks to test whether there is a walk P from s to t in G where ϕ(P) ∈ F When the accepting element is also part of the input, the problem has been studied by Ramaswamy et al (2019) [RSS19] Motivated by the success in designing space-bounded algorithms for the graph reachability problem in the undirected case, we study the labelled reachability problem when the accepting set is also fixed In fact, when the monoid M is a group or belongs to the monoid pseudovariety DA, the previous results imply a deterministic logspace algorithm for the undirected labelled reachability problem over the monoid M for any finite accepting subset as well

Problem Formulation and Key Results

The paper defines the monoid reachability problem REACHM,F as testing whether there is a walk P from s to t in an undirected graph G where the edge labels ϕ(P) ∈ F The authors establish several deterministic logspace algorithms based on the structure of the monoid M and the accepting set F

**)&For any finite monoid M, there is a deterministic logspace algorithm for solving the above problem when the accepting element is the identity of M In contrast, if the accepting element is an idempotent element, under suitable constraints, the problem is NL-hard **

**)&Considering the more general case of the problem when the accepting set is an arbitrary subset of M, we show a deterministic logspace algorithm for a commutative monoid M for all accepting sets F ⊆ M **

**)&Further, we prove that for any finite L-commutative or R-commutative union-of-groups monoid M, there is a deterministic logspace algorithm for all accepting sets F ⊆ M **

Reachability with Specific Accepting Elements

The paper investigates reachability when the accepting set is restricted to specific elements of the monoid M

**)&For any fixed finite monoid M, let G˜ denote the unit group of M. Then, REACHM,F can be solved using a deterministic logspace algorithm for all accepting sets F ⊆ G˜ (and so, in particular, when F = id, where id denotes the identity of M) **

**)&Consider any fixed finite union-of-groups monoid M. Let G˜ denote the unit group (i. p. 3

Where the paper says it

Consider any fixed finite monoid M. Let G˜ denote the unit group of M.

p. 3
Where the paper says it

Consider any fixed finite monoid M. Let G˜ denote the unit group of M.

e., the H-class containing the monoid identity id) of M. p. 5
Where the paper says it

1, there is a logspace algorithm for the problem when F = {id} or its complement by using the fact that the reachability problem reduces to its complement. 5The R-class containing unit group G˜ has only one H-class, namely G˜.

Then, REACHM,F can be solved using a deterministic logspace algorithm for all accepting sets F ⊆ G˜ **

**)&Consider any fixed finite aperiodic monoid M with monoid identity id. Then, REACHM,F with F = id can be solved using a deterministic logspace algorithm **

**)&Consider any fixed finite commutative monoid M. Let G˜ denote the unit group (i.e., set of all invertible elements) of M. p. 0

Where the paper says it

On the Reachability Problem on Monoid-Labelled Undirected Graphs* Nagashri Krishnakumar† Harshil Mittal∗ Jayalal Sarma∗ June 23, 2026 Abstract The labelled reachability problem for undirected graphs where the edges are labelled with elements from a monoid M (more generally, other groupoids or magmas) is known to capture space-bounded complexity classes L and NL. Given a labelled graph G(V, E) (labelled with ϕ : E → M), s, t ∈ V and an accepting subset F ⊆ M, the problem asks to test whether there is a walk P from s to t in G where ϕ(P) ∈ F.

Then, REACHM,F can be solved using a deterministic logspace algorithm for all accepting sets F ⊆ G˜ **

Reachability with Arbitrary Accepting Sets

The study extends to arbitrary subsets F ⊆ M

**)&Consider any fixed finite commutative monoid M. Then, REACHM,F can be solved using a deterministic logspace algorithm for all accepting sets F ⊆ M **

**)&Consider any fixed finite L-commutative or R-commutative union-of-groups monoid M. Then, REACHM,F can be solved using a deterministic logspace algorithm for all accepting sets F ⊆ M **

**)&Consider any fixed finite union-of-groups monoid M such that all R-classes other than the unit group (say G˜) are right ideals. Then, REACHM,F can be solved using a deterministic logspace algorithm when the accepting set F is any of the R-classes of M other than its unit group G˜ **

Complexity Dichotomies for Specific Monoids

The paper provides dichotomy theorems for specific non-commutative aperiodic monoids BA2 and U

**)&For the specific monoids BA2 and U, which are the building blocks of non-commutative aperiodic monoids, we prove a dichotomy theorem with respect to the accepting subsets by showing that for all subsets F ⊆ M, the reachability problem is either NL-complete or is in L **

**)&When the monoid M is BA2 (or U resp.), REACHM,F is NL-hard with accepting set F ⊂ M' where id denotes the identity of M **

Conclusion and Techniques

The main technique employed is the analysis of the product graph of a graph G whose edges are labelled over the monoid M The results classify the difficulty of the labelled reachability problem based on the structure of the monoid from which elements are used for labelling

Pruning redundant reasoning tokens

The analysis relies critically on Green’s equivalence relations in union-of-groups monoids and the properties of the product graph The authors exploit structural properties of the monoid to derive combinatorial structure for upper and lower bounds

How the training signal is built

The proof for NL-hardness involves a reduction from the Directed Reachability problem This reduction constructs a reduced graph G′ by splitting every edge of G and assigning labels a and b to the two edges so obtained The construction ensures that an s-to-t directed path in G exists if and only if there is an s-to-t walk of yield µ in G′

Where the gains come from

The deterministic logspace algorithms are achieved by leveraging properties like the Eulerian nature of product graphs for certain subgraphs The analysis of walk yields modulo cycle lengths is used to reduce the problem to checking a constant number of tuples The overall goal is to classify the difficulty based on monoid structure

References

[All07] Eric Allender. Reachability Problems: An Update. p. 2

Where the paper says it

Several striking finer characterisations of circuit complexity classes using these problems are also known [BT88, CFL83]. On the other side of complexity theory, the problem of testing reachability in directed graphs is a fundamental algorithmic problem that encapsulates many challenges in space-bounded complexity theory.

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

[Bar86] David A Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1

[Boo58] William W Boone. The word problem. p. 1

Where the paper says it

3 Dichotomy for BA2 and U Monoids . 24 5 Discussion and Conclusion 25 1 Introduction One of the fundamental computational problems related to a groupoid (A, ∗) 1 is that of a word problem - given two input words over the alphabet A, test whether they represent the same element.

Proceedings of the National Academy of Sciences, 44(10):1061–1065, 1958

[BT88] David A Mix Barrington and Denis Therien. Finite Monoids and the Fine Structure of NC1. p. 3

Where the paper says it

The above theorem establishes deterministic logspace algorithms for all finite monoids when the accepting element is the identity by using the embedding of the monoid into the transformation monoid of appropriate order. However, we note that for special classes of monoids, we can obtain such algorithms using the specific structure of the monoids, using different arguments, which may be of independent interest.

Journal of the ACM (JACM), 35(4):941–952, 1988

[CFL83] Ashok K Chandra, Steven Fortune, and Richard Lipton. Unbounded fan-in circuits and associative functions. p. 1

Where the paper says it

However, when the group is finite and fixed, the problem is indeed efficiently solvable and has interesting connections to low-level complexity theory. For example, the word problem over any finite non-solvable group exactly captures the class of problems efficiently solvable by logarithmic depth circuits with bounded fan-in ∧, ∨ and 1 also known as magma, A is a set closed under a binary operation ∗ 2

In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC 1983), pages 52–60, 1983

[Col11] Thomas Colcombet. Green’s Relations and Their Use in Automata Theory. p. 1

Where the paper says it

• For the specific monoids BA2 and U, which are the building blocks of non-commutative aperiodic monoids, we prove a dichotomy theorem with respect to the accepting subsets by showing that for all subsets F ⊆ M, the reachability problem is either NL-complete or is in L. To obtain our results, we critically exploit the relationships between Green’s equivalence relations in the union-of-groups monoids and the properties of the product graph (a graph introduced by [RSS19]).

In Language and Automata Theory and Applications (LATA 2011), volume 6638 of Lecture Notes in Computer Science, pages 1–21, Springer, 2011

[CP61] Alfred Hoblitzelle Clifford and GB Preston. The Algebraic Theory of Semigroups, Volume I, volume 7. p. 1

Where the paper says it

The general form of this, even on richer algebraic structures such as groups, when the groups are finitely presented, is undecidable [Boo58, Nov58]. However, when the group is finite and fixed, the problem is indeed efficiently solvable and has interesting connections to low-level complexity theory.

American Mathematical Soc., 1961

[DDG19] Yang Dandan, Igor Dolinka, and Victoria Gould. A group-theoretical interpretation of the word problem for free idempotent generated semigroups. p. 1

Where the paper says it

However, when the group is finite and fixed, the problem is indeed efficiently solvable and has interesting connections to low-level complexity theory. For example, the word problem over any finite non-solvable group exactly captures the class of problems efficiently solvable by logarithmic depth circuits with bounded fan-in ∧, ∨ and 1 also known as magma, A is a set closed under a binary operation ∗ 2

Advances in Mathematics, 345:998–1041, 2019

[Gig20] R.S. Gigo ´n. Some results on L-commutative semigroups. p. 1

Where the paper says it

• For the specific monoids BA2 and U, which are the building blocks of non-commutative aperiodic monoids, we prove a dichotomy theorem with respect to the accepting subsets by showing that for all subsets F ⊆ M, the reachability problem is either NL-complete or is in L. To obtain our results, we critically exploit the relationships between Green’s equivalence relations in the union-of-groups monoids and the properties of the product graph (a graph introduced by [RSS19]).

Semigroup Forum, 101(3):385–399, 2020

[How95] John M. Howie. Fundamentals of Semigroup Theory. p. 1

Where the paper says it

The general form of this, even on richer algebraic structures such as groups, when the groups are finitely presented, is undecidable [Boo58, Nov58]. However, when the group is finite and fixed, the problem is indeed efficiently solvable and has interesting connections to low-level complexity theory.

London Mathematical Society Monographs. Clarendon Press, Oxford, 1995

[KSS14] Balagopal Komarath, Jayalal Sarma, and K. S. Sunil. On the Complexity of Lreachability. p. 0

Where the paper says it

On the Reachability Problem on Monoid-Labelled Undirected Graphs* Nagashri Krishnakumar† Harshil Mittal∗ Jayalal Sarma∗ June 23, 2026 Abstract The labelled reachability problem for undirected graphs where the edges are labelled with elements from a monoid M (more generally, other groupoids or magmas) is known to capture space-bounded complexity classes L and NL. Given a labelled graph G(V, E) (labelled with ϕ : E → M), s, t ∈ V and an accepting subset F ⊆ M, the problem asks to test whether there is a walk P from s to t in G where ϕ(P) ∈ F.

In Descriptional Complexity of Formal Systems (DCFS 2014), pages 258–269, 2014

[KTT07] Ondˇrej Klíma, Pascal Tesson, and Denis Thérien. Dichotomies in the complexity of solving systems of equations over finite semigroups. p. 0

Where the paper says it

This allows us to reveal finer complexity upper and lower bounds, and dichotomies for the problem using the structure of the underlying monoid and the accepting set. In fact, when the monoid M is a group or belongs to the monoid pseudovariety DA, the previous results imply a deterministic logspace algorithm for the undirected labelled reachability problem over the monoid M for any finite accepting subset as well.

Theory of Computing Systems, 40(3):263–297, 2007

[Mar14] Xavier Mary. Classes of semigroups modulo Green’s relation H. p. 7

Where the paper says it

We study the reachability problem variant over different monoid classes. First, we look at some monoid classes defined via Green’s relations.

Semigroup Forum, 88(3):647–669, 2014

[MP84] Stuart W. Margolis and Jean-Eric Pin. Minimal Noncommutative Varieties and Power Varieties. Pacific Journal of Mathematics, 111(1):125–135, 1984

[Nag01] Attila Nagy. Special Classes of Semigroups, volume 1. p. 3

Where the paper says it

The above theorem establishes deterministic logspace algorithms for all finite monoids when the accepting element is the identity by using the embedding of the monoid into the transformation monoid of appropriate order. However, we note that for special classes of monoids, we can obtain such algorithms using the specific structure of the monoids, using different arguments, which may be of independent interest.

Springer Science & Business Media, 2001

[Nov58] Petr Sergeevich Novikov. Algorithmic Unsolvability of the Word Problem in Group Theory. p. 1

Where the paper says it

However, when the group is finite and fixed, the problem is indeed efficiently solvable and has interesting connections to low-level complexity theory. For example, the word problem over any finite non-solvable group exactly captures the class of problems efficiently solvable by logarithmic depth circuits with bounded fan-in ∧, ∨ and 1 also known as magma, A is a set closed under a binary operation ∗ 2

American Mathematical Society Translations, Series 2, 9:1–122, 1958

[Pin86] Jean-Eric Pin. Varieties of Formal Languages. Foundations of Computer Science. p. 0

Where the paper says it

We also design deterministic logspace algorithms for the union-of-groups case that are neither L-commutative nor R-commutative, under certain constraints. *A preliminary version of the paper appeared in the proceedings of the 22nd International Conference Relational and Algebraic Methods in Computer Science (RAMiCS 2026) † Indian Institute of Technology Madras, Chennai, India.

North Oxford Academic Publishing Co Ltd, 1986

[PKGP16] Nirutt Pipattanajinda, Ulrich Knauer, Boyko Gyurov, and Sayan Panma. The Endomorphism Monoids of (n − 3)-regular Graphs of Order n. p. 2

Where the paper says it

Indeed, the word problem is a special case, where the graph is a directed path from a source vertex s to the destination vertex t, with the labels on the edges to be the given sequence of symbols in A∗ in the same order, and F = {α}. Motivated by the fact that the reachability problem is known [Rei04] to be space efficiently solvable for undirected graphs, Ramaswamy et al [RSS19] studies the above problem restricted to undirected graphs.

Algebra and discrete mathematics, 22(2):284–300, 2016

[Rei04] Omer Reingold. Undirected ST-Connectivity in Log-Space. p. 2

Where the paper says it

Given a graph G(V, E) and two special vertices s and t, the problem asks to test if there is a path from the vertex s to t in the graph G. The problem in its most general form (directed graphs) is complete for the class NL (the class of problems that are solvable by non-deterministic Turing machines using only O(log n) space), and for undirected graphs it is known to be complete [Rei04] for the class L (the class of problems that are solvable by deterministic Turing machines that use only O(log n) space).

Electron. Colloquium Comput. Complex., TR04(094), 2004

[RSS19] Vidhya Ramaswamy, Jayalal Sarma, and K. S. Sunil. Space Complexity of Reachability Testing in Labelled Graphs. p. 2

Where the paper says it

Several striking finer characterisations of circuit complexity classes using these problems are also known [BT88, CFL83]. On the other side of complexity theory, the problem of testing reachability in directed graphs is a fundamental algorithmic problem that encapsulates many challenges in space-bounded complexity theory.

Journal of Computer and System Sciences, 105:40–53, 2019

[RTV06] Omer Reingold, Luca Trevisan, and Salil Vadhan. Pseudorandom Walks on Regular Digraphs and the RL vs. p. 2

Where the paper says it

Consider a directed graph G(V, E) with labelling function ϕ : E → A. This labelling naturally extends to walks in the graphs as well.

L Problem. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2006), page 457–466, 2006

[She95] Lev Naumovich Shevrin. On the theory of epigroups. p. 1

Where the paper says it

The general form of this, even on richer algebraic structures such as groups, when the groups are finitely presented, is undecidable [Boo58, Nov58]. However, when the group is finite and fixed, the problem is indeed efficiently solvable and has interesting connections to low-level complexity theory.

i. Russian Academy of Sciences. Sbornik Mathematics, 82(2):485–512, 1995

[Tes98] Pascal Tesson. An Algebraic Approach to Communication Complexity. p. 1

Where the paper says it

The general form of this, even on richer algebraic structures such as groups, when the groups are finitely presented, is undecidable [Boo58, Nov58]. However, when the group is finite and fixed, the problem is indeed efficiently solvable and has interesting connections to low-level complexity theory.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Deterministic logspace algorithm for undirected labelled reachability over group G˜: The system can solve REACHM,F when M is a finite monoid and F is a subset of the unit group G˜ by dropping edges labeled in M excluding G˜ and running the logspace algorithm for undirected labelled reachability over group G˜.

  2. NL-hardness detection for specific non-commutative monoids: The system can determine if REACHM,F is NL-hard when M is BA2 or U and F is a subset of M excluding the identity element, by checking if there is a walk from s to t using at least one edge not labelled with the identity of M.

  3. Logspace algorithm for commutative monoids with arbitrary accepting sets: The system can solve REACHM,F for any finite commutative monoid M and any accepting set F subset of M by iterating over tuples (n'1,..., n'k) and checking existence conditions in a resulting graph where the task reduces to checking for walks whose yield is a constant number of choices.

  4. Logspace algorithm for union-of-groups monoids with arbitrary accepting sets: The system can solve REACHM,F for any finite L-commutative or R-commutative union-of-groups monoid M and any accepting set F subset of M by partitioning the product graph V' into parts V x H and checking reachability within these Eulerian subgraphs.

  5. Logspace algorithm for union-of-groups monoids with specific accepting sets: For a finite union-of-groups monoid M where all R-classes other than the unit group G˜ are right ideals, the system can solve REACHM,F when F is any of these R-classes by checking conditions (a) and (b) involving walks in the original graph and reachability in a related group H.

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 and. Given a graph G(V, E) labelled by ϕ E to M, s,t in V and an accepting subset F M, the problem asks to test whether there is a walk P from s to t in G where ϕ(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 for any finite accepting subset when M is a group or belongs to. We prove the following (for finite monoids): 1) For any monoid M, the problem is in when the accepting element is the identity of M. If the accepting element is an idempotent, under suitable constraints, the problem is-hard. 2) For any commutative monoid M, the problem is in for all F M. 3) For any L(R) -commutative union-of-groups (UoG) monoid M, the problem is in for all F M. We show deterministic logspace algorithms for UoG monoids that are neither L-commutative nor R-commutative, under certain constraints. 4) For the monoids and, we show a dichotomy: for all F M, the problem is either-complete or in. 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)).

Related papers