Onderzoekers hebben een significante verbetering gerealiseerd in de snelheid waarmee het zogenaamde ARRIVAL-probleem kan worden opgelost. In een recent wetenschappelijk artikel wordt een nieuw algoritme gepresenteerd dat de rekentijd drastisch reduceert door gebruik te maken van subexponentiële tijd in de vorm van een kubikwortel.
Wat is het ARRIVAL-probleem?
Het ARRIVAL-probleem is een theoretisch vraagstuk binnen de informatica waarbij een 'token' zich door een zogenaamde switch digraph beweegt. In dit model bevindt het token zich op knooppunten (vertices), waarbij elk knooppunt twee uitgaande verbindingen heeft. De regel is dat deze twee verbindingen afwisselend worden gebruikt: de eerste keer dat een token een knooppunt bereikt, gaat het via de ene weg, de tweede keer via de andere.
De kernvraag van het probleem is om te bepalen welke van de twee eindpunten (terminals) het token als eerste bereikt. Hoewel het probleem is geclassificeerd binnen de complexiteitsklassen $\mathsf{NP} \cap \mathsf{coNP}$, bestond er tot voor kort geen algoritme dat dit in polynomiale tijd kon oplossen.
De nieuwe methodiek en tijdwinst
In de publicatie arxiv.org, ingediend op 20 oktober 2026 door Ebrahim Ghorbani, Raul Lopes en Matthias Mnich, wordt een nieuwe benadering beschreven. De auteurs bouwen voort op eerdere methoden waarbij bepaalde knooppunten als terminals worden beschouwd om consistente schattingen te maken van het aantal tokens dat deze knooppunten versturen.
Voorheen waren er twee dominante benaderingen:
1. Een methode van Gärtner et al. (ICALP 2021), die alle knooppunten gelijktijdig doorzocht met een algoritme voor vaste punten van monotone mappen.
2. Een methode van Haslebacher (ICALP 2025), die één knooppunt tegelijk doorzocht via een binaire zoekmethode.
De nieuwe aanpak van Ghorbani en zijn collega's combineert deze extremen door knooppunten in blokken van $k$ te schatten. Hierbij wordt gebruikgemaakt van de connectie tussen ARRIVAL en $\ell_1$-contracties, een concept dat reeds was vastgesteld in het werk van Haslebacher. Door gebruik te maken van $\ell_1$-centerpoints, die deterministisch worden benaderd, kan het algoritme veel efficiënter opereren.
Concrete resultaten en impact
De impact van deze nieuwe methode is vooral zichtbaar in de theoretische rekentijd. Voor een switch digraph met $n$ knooppunten is de rekentijd verbeterd naar $2^{\mathcal{O}(n^{1/3} \cdot \log^{2/3} n)}$. Dit is een aanzienlijke verbetering ten opzichte van de voorgaande tijdslimiet, die werd uitgedrukt als $n^{\mathcal{O}(\sqrt{n})}$.
Daarnaast hebben de onderzoekers hun resultaten uitgebreid naar het meer algemene $\text{gARRIVAL}$-probleem. In deze variant zijn er sprake van meerdere tokens en verschillende terminals. Volgens de kan dit probleem in dezelfde versnelde tijd worden opgelost, mits er maximaal $2^n$ tokens aanwezig zijn.
Context en wetenschappelijke basis
Het onderzoek is ingediend in de categorieën Data Structures and Algorithms (cs.DS) en Discrete Mathematics (cs.DM). De bewijsvoering steunt op het vinden van de kleinste vaste punten van mappen van ${0, \ldots, N}^k$ naar zichzelf die unit-incrementen hebben.
Hoewel de term "Arrival" ook voorkomt in andere contexten, zoals in de entertainmentindustrie waar de film rottentomatoes.com bekend is, betreft dit specifieke onderzoek uitsluitend de theoretische informatica en algoritmische complexiteit. De publicatie is beschikbaar via de en biedt een nieuwe standaard voor het efficiënter doorzoeken van complexe digraph-structuren.