Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913149781803008 |
|---|---|
| author | Lagerkvist, Victor Groven, Johanna Eriksson, Leif |
| author_facet | Lagerkvist, Victor Groven, Johanna Eriksson, Leif |
| contents | The region connection calculus ($RCC$) and Allen's interval algebra ($IA$) are two well-known NP-hard spatial-temporal qualitative reasoning problems. They are solvable in $2^{O(n \log n)}$ time, where $n$ is the number of variables, and $IA$ is additionally known to be solvable in $o(n)^n$ time. However, no improvement over exhaustive search is known for $RCC$, and if they are also solvable in single exponential time $2^{O(n)}$ is unknown. We investigate multiple avenues towards reaching such bounds. First, we show that branching is insufficient since there are too many non-redundant constraints. Concretely, we classify the maximum number of non-redundant constraints in $RCC$ and $IA$. Algorithmically, we make two significant contributions based on dynamic programming (DP). The first algorithm runs in $4^n$ time and is applicable to a non-trivial, NP-hard fragment of $IA$, which includes the well-known interval graph sandwich problem of Golumbic and Shamir (1993). For the richer $RCC$ problem with 8 basic relations we use a more sophisticated approach which asymptotically matches the $o(n)^n$ bound for $IA$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_21267 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming Lagerkvist, Victor Groven, Johanna Eriksson, Leif Computational Complexity 68R07, 68Q27, 90C39, 68Q17 F.2.2; I.2.4 The region connection calculus ($RCC$) and Allen's interval algebra ($IA$) are two well-known NP-hard spatial-temporal qualitative reasoning problems. They are solvable in $2^{O(n \log n)}$ time, where $n$ is the number of variables, and $IA$ is additionally known to be solvable in $o(n)^n$ time. However, no improvement over exhaustive search is known for $RCC$, and if they are also solvable in single exponential time $2^{O(n)}$ is unknown. We investigate multiple avenues towards reaching such bounds. First, we show that branching is insufficient since there are too many non-redundant constraints. Concretely, we classify the maximum number of non-redundant constraints in $RCC$ and $IA$. Algorithmically, we make two significant contributions based on dynamic programming (DP). The first algorithm runs in $4^n$ time and is applicable to a non-trivial, NP-hard fragment of $IA$, which includes the well-known interval graph sandwich problem of Golumbic and Shamir (1993). For the richer $RCC$ problem with 8 basic relations we use a more sophisticated approach which asymptotically matches the $o(n)^n$ bound for $IA$. |
| title | Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming |
| topic | Computational Complexity 68R07, 68Q27, 90C39, 68Q17 F.2.2; I.2.4 |
| url | https://arxiv.org/abs/2605.21267 |