Technische Samenvatting: Wat maakt de detectie van de Meerderheidsillusie eenvoudig?

Probleemdefinitie

Het artikel onderzoekt de computationele complexiteit van het detecteren van de meerderheidsillusie (Majority Illusion) in sociale netwerken. Formeel wordt een sociaal netwerk gemodelleerd als een ongerichte graaf $G = (N, E)$, waarbij knopen de agenten vertegenwoordigen en randen de sociale relaties. Agenten krijgen een binaire label toegewezen (bijv. "rood" of "blauw"). Een agent bevindt zich onder een meerderheidsillusie als deze de minderheidsetiket als dominant waarneemt binnen de lokale omgeving.

Het centrale beslissingsprobleem is het $q$-meerderheidsillusieprobleem: Gegeven een graaf $G$ en een rationale $q \in [0, 1]$, bestaat er een binaire etikettering van de agenten zodanig dat de meerderheidskleur één specifieke label is (bijv. blauw), maar ten minste een $q$-fractie van de agenten een strikte meerderheid aan buren met het minderheidsetiket (rood) heeft?

Vorig werk door Grandi et al. (2025) stelde vast dat dit probleem in het algemeen NP-volledig is, zelfs voor beperkte grafenklassen zoals bipartiete grafen, planaire grafen of grafen met een maximale graad van 6. Hoewel zij Fixed-Parameter Tractable (FPT) algoritmen leverden voor parameters zoals het vertex cover getal en neighborhood diversity, en aantoonden dat het probleem in XP zit voor treewidth, lieten zij de vraag open welke structurele beperkingen het probleem efficiënt oplosbaar (FPT) versus onhandelbaar maken.

Methodologie

De auteurs maken gebruik van het kader van de geparameteriseerde complexiteit om de handelbaarheid van het $q$-meerderheidsillusieprobleem te analyseren. Zij bestuderen systematisch het probleem met betrekking tot diverse structurele grafenparameters, waaronder:

• Vertex Integrity ($vi(G)$): De minimale grootte van een verzameling knopen waarvan de verwijdering componenten van begrensde grootte achterlaat.
• Feedback Edge Set ($fes(G)$) en Feedback Vertex Set ($fvs(G)$): Het minimale aantal randen of knopen dat verwijderd moet worden om de graaf acyclisch te maken.
• Afstand tot Grafenklassen: Parameters die de knoop- of randafstand meten tot specifieke klassen zoals disjuncte sterren, disjuncte paden en clustergrafen (disjuncte verenigingen van cliques).
• Treedepth ($td(G)$) en Treewidth ($tw(G)$): Standaard structurele parameters.

De methodologie omvat twee primaire algoritmische technieken:

1. N-voudige Integer Lineaire Programmering (ILP): Gebruikt om FPT-resultaten te bewijzen voor parameters zoals vertex integrity. Het probleem wordt geformuleerd als een N-voudige IP waarbij constraints worden gescheiden in globale constraints (het waarborgen van de globale meerderheid en de totale telling van geïllustreerde agenten) en lokale constraints (het waarborgen van lokale buurtcondities voor specifieke componenten).
2. Dynamisch Programmeren (DP): Gebruikt voor boomachtige structuren (bomen, paden) en grafen die dicht bij dergelijke structuren liggen. Voor bomen ontwerpen de auteurs een algoritme met polynomiale tijd voor een gerelateerd "Max List Majority Illusion"-probleem, dat dient als een subroutine voor FPT-algoritmen gebaseerd op feedback edge sets.

Voor de hardheidsresultaten leveren de auteurs geparameteriseerde reducties vanuit bekende W[1]-harde problemen, specifiek Multidimensionale Subset Sum (en de Halfset-variant daarvan) en Capacitated Vertex Cover.

Belangrijkste Bijdragen en Resultaten

1. Fixed-Parameter Tractability (FPT)

Het artikel stelt FPT-algoritmen vast voor verschillende nieuwe parametrisaties:

• Vertex Integrity ($vi(G)$): De auteurs bewijzen dat $q$-meerderheidsillusie in FPT zit wanneer geparameteriseerd door vertex integrity. Het algoritme raadt de etikettering van de "separator" verzameling $M$ en gebruikt N-voudige ILP om deze etikettering uit te breiden naar de overige kleine componenten. Dit resultaat levert ook een verbeterde looptijd op voor het vertex cover getal ($vc(G)$), waarbij de complexiteit wordt verminderd van dubbel exponentieel ($2^{2^{O(vc)}}$) naar enkel exponentieel ($2^{O(vc^2 \log vc)}$).
• Feedback Edge Set ($fes(G)$): Het probleem is in FPT wanneer geparameteriseerd door het feedback edge set getal. De aanpak houdt in dat de etikettering van de knopen die incident zijn aan de feedback randen wordt geraden, waarna de graaf wordt getransformeerd naar een boom met "gadgets" (pendant leaves), en het resulterende instantie wordt opgelost met een dynamisch programmeeralgoritme voor bomen.
• Cluster Edge Deletion Number ($cdn(G)$): Voor grafen die een disjuncte vereniging van cliques worden na het verwijderen van een begrensd aantal randen, is het probleem in FPT. Het algoritme raadt de etikettering van de eindpunten van de verwijderde randen en gebruikt dynamisch programmeren over de cliques, waarbij gebruik wordt gemaakt van het feit dat de status van agenten binnen een clique alleen afhangt van het aantal rode agenten en de vaste externe verbindingen.

2. W[1]-Hardheid en Onhandelbaarheid

Het artikel biedt sterke negatieve resultaten door aan te tonen dat het probleem hard blijft, zelfs voor grafen die "dichtbij" eenvoudige structuren liggen:

• Distance to Disjoint Stars ($dds(G)$): Het probleem is W[1]-hard wanneer geparameteriseerd door de knoopafstand tot disjuncte sterren. Dit wordt bewezen via een reductie van Multidimensionale Halfset Sum.
• Distance to Disjoint Paths ($ddp(G)$): Vergelijkbaar is het probleem W[1]-hard wanneer geparameteriseerd door de knoopafstand tot disjuncte paden.
• Treedepth ($td(G)$): Het probleem is W[1]-hard wanneer geparameteriseerd door treedepth. Dit lost een belangrijke openstaande vraag van Grandi et al. (2025) op, wat impliceert dat een FPT-algoritme voor treewidth (die begrensd is door treedepth) onwaarschijnlijk is onder standaard complexiteitsaannames.
• Distance to Cluster Graphs ($dcg(G)$): Het probleem zit in XP maar is W[1]-hard wanneer geparameteriseerd door de knoopafstand tot clustergrafen. Dit staat in contrast met het FPT-resultaat voor de randafstand naar clustergrafen ($cdn(G)$).

3. Polynomial-Time Oplosbaarheid op Specifieke Klassen

De auteurs bieden een lineaire-tijd algoritme voor grafen die verenigingen zijn van disjuncte paden. Zij leiden een gesloten vormelijke expressie af voor het maximale aantal agenten onder de meerderheidsillusie in een pad, uitsluitend gebaseerd op het aantal agenten, wat aantoont dat het probleem triviaal oplosbaar is op paden en disjuncte paden.

Betekenis en Conclusie

De primaire bijdrage van het artikel is een uitgebreide "kaart" van het computationele complexiteitslandschap voor de detectie van de meerderheidsillusie. Het verheldert de grens tussen handelbare en onhandelbare instanties door specifieke structurele eigenschappen te identificeren die efficiënte detectie mogelijk maken.

De auteurs concluderen dat voor het probleem om handelbaar (FPT) te zijn, het sociale netwerk aan een van de drie voorwaarden moet voldoen:

1. Het bevindt zich binnen een begrensde randafstand van een klasse waar het probleem in polynomiale tijd oplosbaar is (bijv. bomen via feedback edge set, of clustergrafen via cluster edge deletion).
2. Het bevindt zich binnen een begrensde knoopafstand van componenten van begrensde grootte (bijv. via vertex integrity).
3. Het bestaat uit een begrensd aantal goed gestructureerde blokken (bijv. begrensde neighborhood diversity).

De resultaten benadrukken een scherpe dichotomie: terwijl het verwijderen van een klein aantal randen om een eenvoudige structuur te bereiken vaak FPT-algoritmen oplevert, leidt het verwijderen van een klein aantal knopen om dezelfde structuur te bereiken vaak tot W[1]-hardheid. Het artikel laat de complexiteit van het probleem open wanneer het geparameteriseerd is door het twin-cover getal, waarbij wordt opgemerkt dat dit tussen de knoopafstand tot clustergrafen (XP) en de randafstand tot clustergrafen (FPT) ligt, en stelt de vraag of de aanvullende twin-structuur een FPT-algoritme mogelijk maakt.