Resumo Técnico: O que torna a Ilusão de Maioria fácil de detectar?

Definição do Problema

O artigo investiga a complexidade computacional da detecção da Ilusão de Maioria em redes sociais. Formalmente, uma rede social é modelada como um grafo não direcionado $G = (N, E)$, onde os vértices representam agentes e as arestas representam relacionamentos sociais. Os agentes recebem um rótulo binário (por exemplo, "vermelho" ou "azul"). Um agente está sob ilusão de maioria se ele percebe o rótulo minoritário como dominante dentro de sua vizinhança local.

O problema de decisão central é o problema da $q$-Ilusão de Maioria: Dado um grafo $G$ e um racional $q \in [0, 1]$, existe um rótulo binário dos agentes tal que a cor da maioria seja um rótulo específico (digamos, azul), mas pelo menos uma fração $q$ de agentes tenha uma maioria estrita de vizinhos com o rótulo minoritário (vermelho)?

Trabalhos anteriores de Grandi et al. (2025) estabeleceram que este problema é NP-completo em geral, mesmo para classes de grafos restritas como grafos bipartidos, planos ou grafos com grau máximo 6. Embora tenham fornecido algoritmos FPT (Fixed-Parameter Tractable) para parâmetros como o número de cobertura de vértices e diversidade de vizinhança, e mostrado que o problema está em XP para largura de árvore (treewidth), eles deixaram em aberto a questão de quais restrições estruturais tornam o problema eficientemente solúvel (FPT) versus intratável.

Metodologia

Os autores empregam o framework de complexidade parametrizada para analisar a tratabilidade do problema da $q$-Ilusão de Maioria. Eles estudam sistematicamente o problema em relação a vários parâmetros estruturais de grafos, incluindo:

• Integridade de Vértice ($vi(G)$): O tamanho mínimo de um conjunto de vértices cuja remoção deixa componentes de tamanho limitado.
• Conjunto de Feedback de Arestas ($fes(G)$) e Conjunto de Feedback de Vértices ($fvs(G)$): O número mínimo de arestas ou vértices para remover para tornar o grafo acíclico.
• Distância para Classes de Grafos: Parâmetros que medem a distância de vértice ou aresta para classes específicas como estrelas disjuntas, caminhos disjuntos e grafos de agrupamento (cluster graphs - uniões disjuntas de cliques).
• Profundidade de Árvore ($td(G)$) e Largura de Árvore ($tw(G)$): Parâmetros estruturais padrão.

A metodologia envolve duas técnicas algorítmicas primárias:

1. Programação Inteira de N-dobras (N-fold ILP): Usada para provar resultados FPT para parâmetros como integridade de vértice. O problema é formulado como um IP de N-dobras onde as restrições são separadas em restrições globais (garantindo a maioria global e a contagem total de agentes com ilusão) e restrições locais (garantindo condições de vizinhança local para componentes específicos).
2. Programação Dinâmica (DP): Usada para estruturas do tipo árvore (árvores, caminhos) e grafos próximos a tais estruturas. Para árvores, os autores projetam um algoritmo de tempo polinomial para um problema relacionado de "Máxima Lista de Ilusão de Maioria", que serve como uma sub-rotina para algoritmos FPT baseados em conjuntos de feedback de arestas.

Para resultados de dureza, os autores fornecem reduções parametrizadas de problemas conhecidos como W[1]-difíceis, especificamente Subset Sum Multidimensional (e sua variante Halfset) e Cobertura de Vértice Capacitada.

Contribuições Principais e Resultados

1. Tratabilidade de Parâmetro Fixo (FPT)

O artigo estabelece algoritmos FPT para várias novas parametrizações:

• Integridade de Vértice ($vi(G)$): Os autores provam que a $q$-Ilusão de Maioria é FPT quando parametrizada pela integridade de vértice. O algoritmo supõe o rótulo do conjunto "separador" $M$ e usa N-fold ILP para estender esse rótulo para os componentes restantes de tamanho pequeno. Este resultado também produz um tempo de execução melhorado para o número de cobertura de vértices ($vc(G)$), reduzindo a complexidade de duplamente exponencial ($2^{2^{O(vc)}}$) para exponencial simples ($2^{O(vc^2 \log vc)}$).
• Conjunto de Feedback de Arestas ($fes(G)$): O problema mostra ser FPT quando parametrizado pelo número de conjunto de feedback de arestas. A abordagem envolve supor o rótulo dos vértices incidentes às arestas de feedback, transformando o grafo em uma árvore com "gadgets" (folhas pendentes) e resolvendo a instância resultante usando um algoritmo de programação dinâmica em árvores de tempo polinomial.
• Número de Deleção de Arestas de Agrupamento ($cdn(G)$): Para grafos que se tornam uma união disjunta de cliques após a remoção de um número limitado de arestas, o problema é FPT. O algoritmo supõe o rótulo dos pontos finais das arestas removidas e usa programação dinâmica sobre os cliques, aproveitando o fato de que o status dos agentes dentro de um clique depende apenas do número de agentes vermelhos e das conexões externas fixas.

2. W[1]-Dureza e Intratabilidade

O artigo fornece fortes resultados negativos, mostrando que o problema permanece difícil mesmo para grafos que estão "próximos" de estruturas simples:

• Distância para Estrelas Disjuntas ($dds(G)$): O problema é W[1]-difícil quando parametrizado pela distância de vértice para estrelas disjuntas. Isso é provado via uma redução de Multidimensional Halfset Sum.
• Distância para Caminhos Disjuntos ($ddp(G)$): Da mesma forma, o problema é W[1]-difícil quando parametrizado pela distância de vértice para caminhos disjuntos.
• Profundidade de Árvore ($td(G)$): O problema é W[1]-difícil quando parametrizado pela profundidade de árvore. Isso resolve uma questão aberta significativa de Grandi et al. (2025), implicando que um algoritmo FPT para largura de árvore (que é limitada pela profundidade de árvore) é improvável sob suposições de complexidade padrão.
• Distância para Grafos de Agrupamento ($dcg(G)$): O problema está em XP, mas é W[1]-difícil quando parametrizado pela distância de vértice para grafos de agrupamento. Isso contrasta com o resultado FPT para a distância de aresta para grafos de agrupamento ($cdn(G)$).

3. Solubilidade em Tempo Polinomial em Classes Específicas

Os autores fornecem um algoritmo de tempo linear para grafos que são uniões de caminhos disjuntos. Eles derivam uma expressão de forma fechada para o número máximo de agentes sob ilusão de maioria em um caminho baseando-se apenas no número de agentes, mostrando que o problema é trivialmente solúvel em caminhos e caminhos disjuntos.

Significância e Conclusão

A principal contribuição do artigo é um "mapa" abrangente do cenário de complexidade computacional para o problema de detecção da Ilusão de Maioria. Ele esclarece a fronteira entre instâncias tratáveis e intratáveis ao identificar propriedades estruturais específicas que permitem a detecção eficiente.

Os autores concluem que, para o problema ser tratável (FPT), a rede social deve satisfazer uma de três condições:

1. Ela está dentro de uma distância de aresta limitada de uma classe onde o problema é solúvel em tempo polinomial (ex: árvores via conjunto de feedback de arestas, ou grafos de agrupamento via deleção de arestas de agrupamento).
2. Ela está dentro de uma distância de vértice limitada de componentes de tamanho limitado (ex: via integridade de vértice).
3. Consiste em um número limitado de blocos bem estruturados (ex: diversidade de vizinhança limitada).

Os resultados destacam um díptico agudo: enquanto remover um pequeno número de arestas para alcançar uma estrutura simples frequentemente resulta em algoritmos FPT, remover um pequeno número de vértices para alcançar a mesma estrutura frequentemente leva à W[1]-dureza. O artigo deixa em aberto a complexidade do problema quando parametrizado pelo número de cobertura de gêmeos (twin-cover number), observando que ele situa-se entre a distância de vértice para grafos de agrupamento (XP) e a distância de aresta para grafos de agrupamento (FPT), e questiona se a estrutura adicional de gêmeos permite um algoritmo FPT.