Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.05762 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918048860995584 |
|---|---|
| author | Kiefer, Stefan Ryzhikov, Andrew |
| author_facet | Kiefer, Stefan Ryzhikov, Andrew |
| contents | The period of a strongly connected digraph is the greatest common divisor of the lengths of all its cycles. The period of a digraph is the least common multiple of the periods of its strongly connected components. These notions play an important role in the theory of Markov chains and the analysis of powers of nonnegative matrices. While the time complexity of computing the period is well-understood, little is known about its space complexity. We show that the problem of computing the period of a digraph is NL-complete, even if all its cycles are contained in the same strongly connected component. However, if the digraph is strongly connected, we show that this problem becomes L-complete. For primitive digraphs (that is, strongly connected digraphs of period one), there always exists a number $m$ such that there is a path of length exactly $m$ between every two vertices. We show that computing the smallest such $m$, called the exponent of a digraph, is NL-complete. The exponent of a primitive digraph is a particular case of the index of convergence of a nonnegative matrix, which we also show to be computable in NL, and thus NL-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_05762 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The complexity of computing the period and the exponent of a digraph Kiefer, Stefan Ryzhikov, Andrew Discrete Mathematics Combinatorics The period of a strongly connected digraph is the greatest common divisor of the lengths of all its cycles. The period of a digraph is the least common multiple of the periods of its strongly connected components. These notions play an important role in the theory of Markov chains and the analysis of powers of nonnegative matrices. While the time complexity of computing the period is well-understood, little is known about its space complexity. We show that the problem of computing the period of a digraph is NL-complete, even if all its cycles are contained in the same strongly connected component. However, if the digraph is strongly connected, we show that this problem becomes L-complete. For primitive digraphs (that is, strongly connected digraphs of period one), there always exists a number $m$ such that there is a path of length exactly $m$ between every two vertices. We show that computing the smallest such $m$, called the exponent of a digraph, is NL-complete. The exponent of a primitive digraph is a particular case of the index of convergence of a nonnegative matrix, which we also show to be computable in NL, and thus NL-complete. |
| title | The complexity of computing the period and the exponent of a digraph |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2408.05762 |