Fair Vertex Problems Parameterized by Cluster Vertex Deletion

1. Definição do Problema e Contexto

Problemas de Vértice Justos (Fair Vertex Problems):
O artigo investiga variantes "justas" de problemas padrão em grafos. Diferentemente dos problemas tradicionais que buscam um conjunto solução $X$ de cardinalidade (tamanho) mínima, os problemas justos buscam um conjunto $X$ que minimize o custo justo.

• Custo Justo ($fc$): Definido como $fc(X) := \max_{v \in V(G)} |N(v) \cap X|$.
• Objetivo: Encontrar um conjunto $X$ que satisfaça uma propriedade lógica específica (por exemplo, $G \setminus X$ é uma floresta) de modo que nenhum vértice no grafo tenha mais de $k$ vizinhos em $X$.

Parametrização:
O estudo foca na parametrização estrutural pelo número de Cluster Vertex Deletion (CVD).

• Número CVD: O tamanho do menor conjunto $D \subseteq V(G)$ (chamado de modulador) tal que $G \setminus D$ é uma coleção de cliques disjuntos.
• Contexto: Trabalhos anteriores estabeleceram que problemas Fair MSO$_1$ são Tractáveis em Parâmetro Fixo (FPT) quando parametrizados por Twin Cover (um parâmetro mais forte). A questão em aberto era se isso se estendia ao parâmetro mais geral Cluster Vertex Deletion.

Estrutura Lógica:
Os problemas são definidos usando lógica Monádica de Segunda Ordem (MSO$_1$), que permite quantificação sobre vértices e conjuntos de vértices (mas não sobre arestas). O artigo considera duas variantes principais:

1. L-FairVD (Deleção): Encontrar $X$ tal que $G \setminus X \models \phi$.
2. L-FairVE (Avaliação): Encontrar conjuntos $W_1, \dots, W_\ell$ satisfazendo uma fórmula $\phi(W_1, \dots, W_\ell)$.

---

2. Contribuições Principais

O artigo fornece uma dicotomia para problemas Fair MSO$_1$ parametrizados por CVD:

1. Resultado de Dureza (Negativo):

   • Teorema 1: O problema Fair Vertex FO Deletion é W[1]-difícil quando parametrizado pelo número de cluster vertex deletion (para CVD $>3$) e pelo tamanho da fórmula.
   • Isso responde negativamente à questão em aberto de [16], provando que um algoritmo FPT geral para todos os problemas Fair MSO$_1$ sob parametrização CVD é impossível (a menos que FPT = W[1]).

2. Resultado Positivo (Metateorema):

   • Teorema 3 e 24: Os autores identificam uma condição suficiente sob a qual problemas Fair MSO$_1$ são FPT parametrizados por CVD.
   • A condição baseia-se no conceito de formas $\alpha$-coerentes. Se um problema admite uma solução onde a interação entre o conjunto solução e os cliques em $G \setminus D$ segue um padrão "coerente" específico (seja selecionando quase todos os vértices ou quase nenhum de tipos de vizinhança específicos dentro dos cliques), um algoritmo FPT existe.

3. Aplicação Algorítmica:

   • O metateorema é aplicado para resolver vários problemas naturais em tempo FPT, incluindo:
     • Fair Vertex Cover (Cobertura de Vértices Justa)
     • Fair Feedback Vertex Set (Conjunto de Vértices de Retroalimentação Justo)
     • Fair Odd Cycle Transversal (Transversal de Ciclos Ímpares Justo)
     • Fair Dominating Set (Conjunto Dominante Justo)
     • Fair $[\sigma, \rho]$-Domination (para $\sigma$ finito, ou $\sigma, \rho$ cofinitos).

---

3. Metodologia

Os autores empregam uma combinação sofisticada de técnicas de verificação de modelos, teoria estrutural de grafos e Programação Linear Inteira (ILP).

A. Decomposição Estrutural e "Formas"

O núcleo do algoritmo baseia-se na compressão do espaço de soluções usando Formas.

• Modulador ($D$): O grafo é dividido no modulador $D$ e uma coleção de cliques $\mathcal{C}$ em $G \setminus D$.
• Tipos de Clique: Vértices em um clique $C$ são categorizados pela sua vizinhança em $D$. Um Tipo de Clique é um vetor que conta quantos vértices em $C$ se conectam a cada subconjunto de $D$.
• Padrões de Solução: Para um clique $C$, a solução $X$ é descrita por quantos vértices ela seleciona de cada tipo de vizinhança.
• Formas: Uma "Forma" é uma representação compacta (uma matriz) que agrega as contagens de cliques de tipos específicos e os padrões de solução que eles seguem.
  • Limitação: O número de vértices selecionados de um tipo de vizinhança específico é limitado por um limite $\alpha$. Se a contagem exceder $\alpha$, é tratada como "ilimitada", mas categorizada como fina (poucos selecionados) ou grossa (poucos excluídos).
  • Coerência: Uma forma é $\alpha$-coerente se, para cada tipo de vizinhança ilimitado, a solução for consistentemente "fina" (selecionando poucos) ou "grossa" (selecionando a maioria) em todos os cliques desse tipo.

B. Verificação de Modelos em Formas

• Vértices/Cliques Irrelevantes: Usando ferramentas lógicas (especificamente o lema do "vértice irrelevante" e o lema do "clique irrelevante"), os autores provam que, se um grafo tem muitos cliques do mesmo tipo, a verdade de uma fórmula MSO$_1$ depende apenas da forma da solução, e não do número exato de cliques (desde que o número seja grande o suficiente).
• Lema 13: Estabelece que, para $\alpha$ e $\gamma$ suficientemente grandes, $G \models \phi(X)$ se e somente se a forma de $(G, X)$ satisfizer a fórmula. Isso permite que o algoritmo verifique a condição lógica na forma comprimida em vez de no grafo completo.

C. Programação Linear Inteira (ILP)

Uma vez identificada uma forma válida (satisfazendo a fórmula lógica), o algoritmo deve reconstruir uma solução com custo justo mínimo.

• Formulação ILP: O problema de encontrar um conjunto $X$ correspondendo a uma forma específica com custo justo $\le k$ é formulado como um ILP.
  • Variáveis: Representam o número de cliques de um certo tipo atribuídos a um padrão de solução específico.
  • Restrições:
    1. Consistência: O número de cliques atribuídos deve corresponder às contagens na matriz de formas.
    2. Custo Justo: O número total de vizinhos em $X$ para qualquer vértice no modulador $D$ não deve exceder $k$.
• Complexidade: O número de variáveis no ILP depende apenas dos parâmetros (tamanho da fórmula, número CVD, $\alpha$, $\gamma$), e não do tamanho do grafo.
• Resolução: O ILP é resolvido usando o algoritmo de Lenstra (melhorado por Reis e Rothvoss), que roda em tempo $f(p) \cdot \text{poly}(n)$, onde $p$ é o número de variáveis. Isso garante que o algoritmo geral seja FPT.

---

4. Prova de Dureza (W[1]-dificuldade)

Para provar que o caso geral é W[1]-difícil, os autores reduzem o problema a Unary $\ell$-Bin Packing (conhecido por ser W[1]-difícil parametrizado por $\ell$).

1. Redução: Eles constroem um grafo onde o tamanho do modulador corresponde ao número de recipientes ($d = \ell$).
2. Cliques como Itens: Cada item na instância de Bin Packing é representado por um clique. O tamanho do clique e suas conexões ao modulador codificam o tamanho do item.
3. Lógica: Uma fórmula FO é construída para impor que, para cada clique, a solução deve "remover" um subconjunto específico de vértices correspondendo ao item sendo colocado em um recipiente específico.
4. Custo Justo: A restrição de custo justo garante que a capacidade dos recipientes não seja excedida.
5. Resultado: Uma solução para o problema Fair Vertex FO Deletion existe se e somente se a instância de Bin Packing for solucionável. Como Bin Packing é W[1]-difícil, o problema Fair Vertex geral sob CVD também o é.

---

5. Significado e Impacto

• Resolução de Questões em Aberto: O artigo resolve definitivamente a questão de saber se problemas Fair MSO$_1$ são FPT sob parametrização CVD. Ele mostra que, embora o problema geral seja intratável (W[1]-difícil), uma grande e natural subclasse de problemas é tratável.
• Metateorema para Problemas Justos: Fornece um poderoso metateorema (Teorema 24) que permite aos pesquisadores determinar se um problema justo específico é FPT verificando a "coerência" de sua estrutura de solução em cliques.
• Ponte entre Lógica e Otimização: O trabalho combina elegantemente a verificação de modelos MSO (lógica) com otimização combinatória (ILP) para lidar com restrições de justiça, que são notoriamente difíceis de parametrizar.
• Direções Futuras: O artigo destaca questões em aberto, como se a tratabilidade se estende ao parâmetro Modular Width (um parâmetro mais denso) e se todos os casos de Fair $[\sigma, \rho]$-Domination são FPT. Também levanta a questão de saber se esses problemas estão em XP (polinomial para parâmetro fixo) quando parametrizados por Clique-width.

Em resumo, este artigo estabelece uma fronteira matizada para a complexidade parametrizada de problemas justos em grafos, provando que, embora um algoritmo FPT universal seja impossível para CVD, existe um framework robusto para resolver muitos problemas fundamentais de forma eficiente.