A Tight Lower Bound for Cycle Detection in Grid Graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914509308821504 |
|---|---|
| author | Au, Andrew |
| author_facet | Au, Andrew |
| contents | We prove that any algorithm for detecting cycles in an $m \times n$ grid graph, where cells are colored and adjacency is defined by matching colors, must read all $mn$ cells in the worst case for all grids with $m \geq 2$ and $n \geq 2$. The proof is by adversary argument: we construct an adaptive adversary that maintains ambiguity -- one completion containing a cycle and one without -- until the final cell is read. The construction proceeds by tiling the grid with $2 \times 2$, $2 \times 3$, $3 \times 2$, and $3 \times 3$ blocks, each equipped with an independent block adversary, composed via a checkerboard isolation scheme. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_23894 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Tight Lower Bound for Cycle Detection in Grid Graphs Au, Andrew Data Structures and Algorithms We prove that any algorithm for detecting cycles in an $m \times n$ grid graph, where cells are colored and adjacency is defined by matching colors, must read all $mn$ cells in the worst case for all grids with $m \geq 2$ and $n \geq 2$. The proof is by adversary argument: we construct an adaptive adversary that maintains ambiguity -- one completion containing a cycle and one without -- until the final cell is read. The construction proceeds by tiling the grid with $2 \times 2$, $2 \times 3$, $3 \times 2$, and $3 \times 3$ blocks, each equipped with an independent block adversary, composed via a checkerboard isolation scheme. |
| title | A Tight Lower Bound for Cycle Detection in Grid Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.23894 |