Maximum Independent Set: het rekenraadsel achter slimme netwerken en nieuwe kwantumchips
Stel je voor: je organiseert een feest en een aantal gasten kunnen elkaar niet uitstaan. Je wilt zo veel mogelijk mensen uitnodigen, maar nooit twee ruziënde gasten tegelijk. Welke, en hoeveel, gasten kun je maximaal uitnodigen zonder dat er ergens twee vijanden samen aan tafel zitten? Dat is in essentie het Maximum Independent Set-probleem (afgekort MIS), een van de oudste en hardnekkigste puzzels uit de informatica.
Achter de speelse analogie schuilt een probleem dat overal opduikt waar dingen elkaar in de weg zitten: zendmasten die niet dezelfde frequentie mogen gebruiken, examens die niet op hetzelfde tijdstip mogen vallen, of routers in een netwerk die niet gelijktijdig mogen zenden. MIS is de wiskundige kern van al dit soort planningsvraagstukken, en de reden dat het de laatste jaren weer volop in de belangstelling staat, is een onverwachte: nieuwe kwantumcomputers met arrays van individuele atomen blijken dit probleem als het ware in hun natuurlijke taal te 'spreken'.
Wat is het precies?
In de wiskunde beschrijf je zo'n probleem met een graaf: een verzameling punten (knopen) die met lijnen (verbindingen, of 'edges') met elkaar verbonden zijn. In het feest-voorbeeld is elke gast een knoop, en een lijn tussen twee knopen betekent 'deze twee mogen niet samen aanwezig zijn'.
Een independent set (onafhankelijke verzameling) is een groep knopen waarbij geen enkel paar rechtstreeks met elkaar verbonden is. De maximum independent set is de grootst mogelijke zo'n groep die je in een gegeven graaf kunt vinden.
Voor een graaf met een handvol punten is dat met wat puzzelen wel te doen. Het venijn zit in de schaal: bij honderden of duizenden knopen groeit het aantal mogelijke combinaties zo explosief dat zelfs de snelste supercomputer, als hij alles domweg zou uitproberen, er te lang over zou doen. Informatici noemen dit een NP-moeilijk probleem: er is geen bekende methode die het antwoord voor elke willekeurige graaf snel (in wat wiskundigen 'polynomiale tijd' noemen) exact berekent, en er zijn goede theoretische redenen om aan te nemen dat zo'n methode ook niet bestaat.
Sterker nog, onderzoekers Johan HÃ¥stad (1999) en later David Zuckerman (2007) bewezen dat het probleem niet alleen moeilijk exact op te lossen is, maar dat zelfs een goede benadering van het antwoord voor grote, willekeurige grafen rekenÂkundig onhaalbaar is, tenzij enkele fundamentele aannames in de complexiteitstheorie onjuist blijken. Dat maakt MIS tot een van de 'lastigste' problemen binnen een toch al lastige probleemklasse.
Wat wil men ermee bereiken?
Het directe doel is simpel: voor praktische toepassingen een zo groot mogelijke, conflictvrije selectie vinden, en dat liefst snel genoeg om bruikbaar te zijn. Denk aan het toewijzen van radiofrequenties aan zendmasten die elkaar niet mogen storen, het plannen van taken die niet gelijktijdig dezelfde hulpbron mogen gebruiken, of het plaatsen van kaartlabels op een landkaart zonder overlap.
Maar er is ook een dieperliggend doel. Omdat MIS zo'n zuivere, algemene vorm van 'conflictvermijding' vertegenwoordigt, gebruiken onderzoekers het als testcase: een probleem waarmee ze nieuwe algoritmen, hardware of rekenmethoden op de proef stellen. Als een nieuwe aanpak MIS efficiënter kan aanpakken dan bestaande methoden, is dat een teken dat die aanpak mogelijk ook voor een hele familie van verwante planning- en optimalisatieproblemen iets te bieden heeft. Dat is precies waarom MIS de laatste jaren een belangrijke rol speelt in het onderzoek naar kwantumcomputers: het is een ideale, goed gedefinieerde graadmeter om te zien of kwantumhardware daadwerkelijk iets kan wat klassieke computers niet (efficiënt) kunnen.
Voorbeelden uit de praktijk
Een van de meest aansprekende recente voorbeelden komt uit de kwantumwereld. In 2022 publiceerde een onderzoeksgroep rond natuurkundige Mikhail Lukin van Harvard University, in samenwerking met het bedrijf QuEra Computing, een studie in het tijdschrift Science waarin ze een processor met 256 individueel gevangen atomen gebruikten om Maximum Independent Set-problemen op te lossen. De atomen werden met laserpincetten (optical tweezers) precies zo gerangschikt dat hun onderlinge afstand overeenkwam met de structuur van de graaf.
Dat werkt omdat atomen in een aangeslagen 'Rydberg-toestand' elkaar op korte afstand blokkeren: twee naburige atomen kunnen niet tegelijk aangeslagen worden. Die natuurkundige blokkade is fysiek precies wat een independent-set-beperking wiskundig voorschrijft, waardoor dit type graaf (een zogeheten unit disk graph, waarbij knopen punten in het vlak zijn die verbonden zijn als ze dicht genoeg bij elkaar liggen) als het ware vanzelf door de natuurkunde wordt 'opgelost'.
Het Franse bedrijf Pasqal, opgericht in 2019 als spin-off van het Institut d'Optique met onder meer Nobelprijswinnaar Alain Aspect als mede-oprichter, werkt met vergelijkbare Rydberg-atoomtechnologie en presenteert MIS-achtige optimalisatieproblemen eveneens als een van de voorbeeldtoepassingen van hun platform.
Buiten de kwantumwereld is MIS al decennia een terugkerend onderwerp in de klassieke informatica: de DIMACS Implementation Challenges, een reeks academische benchmarkwedstrijden die teruggaat tot de jaren negentig, bevatte een specifieke ronde gewijd aan het snel benaderen van maximale onafhankelijke verzamelingen (en het nauw verwante 'clique'-probleem) in grote testgrafen, en de daar verzamelde testgevallen worden nog steeds gebruikt om nieuwe algoritmen te vergelijken.
Ook in de telecomsector duikt het probleem op: bij het indelen van frequentiekanalen voor draadloze netwerken, waarbij zendmasten die elkaar kunnen storen als verbonden knopen worden gemodelleerd, wordt in essentie naar een zo groot mogelijke onafhankelijke verzameling conflictvrije toewijzingen gezocht.
Hoe ver is de techniek?
Op de klassieke computer is er geen wondermiddel, maar wel een rijk gereedschapskist. Voor kleine tot middelgrote grafen bestaan exacte methoden (zoals 'branch-and-bound'-algoritmen en oplossers voor geheeltallige lineaire optimalisatie) die het precieze maximum vinden, mits men genoeg rekentijd geeft. Voor grote, praktische grafen grijpt men naar heuristieken: 'gulzige' algoritmen, lokale zoekmethoden en meta-heuristieken die snel een goede, maar niet gegarandeerd optimale oplossing leveren. Deze aanpak werkt in de praktijk vaak verrassend goed, ondanks de sombere theoretische limieten van HÃ¥stad en Zuckerman, omdat echte grafen zelden de 'ergst denkbare' worst-case vorm hebben.
De kwantumaanpak staat nog veel prilder in de kinderschoenen. De experimenten met Rydberg-atoomarrays zijn indrukwekkende technische prestaties en laten zien dat de hardware in staat is problemen van honderden knopen te 'coderen' en te meten. Maar tot nu toe is er geen overtuigend bewijs van een praktisch kwantumvoordeel: voor de graaftypes die op deze hardware natuurlijk passen (unit disk graphs), kunnen ook slimme klassieke algoritmen vaak nog vergelijkbaar goed of beter presteren. Voor algemene, willekeurige grafen die niet op de fysieke geometrie van atomen lijken, is de kwantumaanpak bovendien veel minder vanzelfsprekend toepasbaar.
Kortom: de fundamenten staan, de proof-of-concept is geleverd, maar of en wanneer kwantumhardware voor MIS-achtige problemen een reëel, praktisch voordeel oplevert ten opzichte van de beste klassieke methoden, is nog een open vraag. Dat is een eerlijke onzekerheid die ook de onderzoekers zelf benadrukken.
Wie werken eraan?
Op het snijvlak van MIS en kwantumcomputing zijn vooral twee spelers zichtbaar: QuEra Computing, een spin-off van onderzoek aan Harvard University en het Massachusetts Institute of Technology (MIT), voortbouwend op het werk van de onderzoeksgroep van Mikhail Lukin, en het Franse Pasqal, met wortels in het Franse onderzoeksinstituut Institut d'Optique en het CNRS. Beide bedrijven bouwen kwantumprocessors op basis van neutrale atomen en Rydberg-blokkade, en gebruiken MIS als een van hun belangrijkste demonstratieproblemen.
Op het klassieke, algoritmische vlak is het onderzoek breder verspreid over universiteiten wereldwijd, met een lange traditie in de theoretische informatica die teruggaat tot het werk van Richard Karp, die in 1972 aantoonde dat MIS nauw verwant is aan een kern van 21 klassieke NP-complete problemen (via de wiskundig equivalente 'clique'- en 'vertex cover'-problemen). Onderzoeksgroepen op het gebied van combinatorische optimalisatie, complexiteitstheorie en operations research, verspreid over de Verenigde Staten, Europa en Azië, blijven nieuwe benaderingsalgoritmen en heuristieken ontwikkelen.