Domando o Intratável
Coleção Escola de Lógica Matemática
JOÃO CARLOS MOREIRA
Doutor em Matemática
Universidade Federal de Uberlândia
Copyright©2013-2025 Coleção Escola de Lógica Matemática. Todos os direitos reservados.
Imagine que você administra uma rede social e precisa encontrar um grupo de influenciadores-chave. O problema parece impossível quando a rede tem milhões de usuários, mas e se você soubesse que precisa de apenas cinco influenciadores? De repente, o cenário muda completamente. Esta é a magia da complexidade parametrizada: transformar problemas intratáveis em desafios administráveis ao focar em aspectos específicos que, na prática, permanecem pequenos. Nesta jornada fascinante, descobriremos como uma mudança de perspectiva revolucionou nossa compreensão sobre o que é computacionalmente viável.
A teoria clássica da complexidade nos ensinou a separar problemas em categorias como P e NP, baseando-se no pior caso para instâncias de tamanho n. Mas esta visão binária esconde uma riqueza de nuances. Muitos problemas NP-completos tornam-se tratáveis quando certos aspectos da entrada permanecem pequenos. A complexidade parametrizada nasceu desta observação, oferecendo uma análise mais refinada que considera múltiplas dimensões do problema.
Na década de 1990, Downey e Fellows introduziram a complexidade parametrizada como uma nova lente para examinar problemas computacionais. Em vez de considerar apenas o tamanho n da entrada, passamos a analisar também um parâmetro k que captura algum aspecto estrutural do problema. Esta abordagem bidimensional revelou que muitos problemas considerados intratáveis são, na verdade, eficientemente solucionáveis quando o parâmetro é pequeno.
O conceito central da complexidade parametrizada é a tratabilidade por parâmetro fixo (FPT). Um problema está em FPT se pode ser resolvido em tempo f(k) · nᶜ, onde f é uma função computável que depende apenas do parâmetro k, e c é uma constante independente de k. Esta separação permite que a explosão combinatória fique confinada ao parâmetro, mantendo comportamento polinomial em n.
A escolha do parâmetro é crucial e pode vir de diversas fontes: tamanho da solução desejada, estrutura do grafo (largura de árvore, grau máximo), distância para casos especiais, ou características do domínio de aplicação. Um mesmo problema pode ter comportamentos completamente diferentes dependendo da parametrização escolhida, revelando a riqueza desta abordagem.
A complexidade parametrizada desenvolveu um arsenal impressionante de técnicas algorítmicas. Kernelização reduz instâncias grandes a núcleos pequenos equivalentes. Árvores de busca limitada exploram o espaço de soluções com poda inteligente. Programação dinâmica sobre estruturas de largura limitada resolve problemas difíceis em grafos especiais. Cada técnica explora diferentes aspectos da estrutura parametrizada.
Nem todos os problemas parametrizados são FPT. A W-hierarquia classifica problemas parametrizados em níveis crescentes de dificuldade: FPT ⊆ W[1] ⊆ W[2] ⊆ ... ⊆ XP. Problemas W[1]-difíceis provavelmente não admitem algoritmos FPT, estabelecendo uma teoria de intratabilidade parametrizada análoga à teoria NP-completude.
A complexidade parametrizada encontrou aplicações revolucionárias em bioinformática (análise de redes biológicas), redes sociais (detecção de comunidades), otimização (roteamento com restrições), inteligência artificial (inferência em modelos gráficos) e verificação de software (model checking). Em cada domínio, identificar e explorar parâmetros pequenos transformou problemas antes intratáveis em rotinas computacionais viáveis.
A complexidade parametrizada continua evoluindo com novas direções empolgantes. Análise multivariada considera múltiplos parâmetros simultaneamente. Complexidade parametrizada aproximada combina aproximação com parametrização. Algoritmos parametrizados paralelos exploram computação distribuída. Lower bounds condicionais estabelecem limites fundamentais baseados em conjecturas da complexidade.
A complexidade parametrizada representa mais que técnicas algorítmicas — é uma mudança fundamental em como abordamos problemas computacionais. Em vez de aceitar a intratabilidade como destino, buscamos estruturas que tornem o problema tratável. Esta mentalidade otimista mas rigorosa abriu portas para resolver problemas práticos que pareciam impossíveis.
Este capítulo introdutório estabeleceu o cenário para nossa exploração da complexidade parametrizada. Vimos como uma mudança de perspectiva — considerar parâmetros além do tamanho da entrada — revoluciona nossa capacidade de resolver problemas difíceis. Nos próximos capítulos, mergulharemos nas técnicas específicas, exploraremos a teoria profunda e descobriremos aplicações surpreendentes desta área vibrante da ciência da computação.
A complexidade parametrizada nos ensina que a intratabilidade raramente é absoluta — é uma questão de encontrar a perspectiva certa. Com as ferramentas que desenvolveremos, você aprenderá a identificar oportunidades escondidas em problemas aparentemente impossíveis, transformando desafios computacionais em soluções elegantes e eficientes. Vamos começar esta transformação explorando em detalhe o conceito fundamental de parâmetros!
Todo problema computacional esconde dimensões ocultas esperando para serem descobertas. Como um escultor que vê a estátua dentro do mármore bruto, o cientista da computação parametrizada aprende a identificar aspectos estruturais que transformam problemas intratáveis em desafios administráveis. Neste capítulo, exploraremos a arte e a ciência de escolher parâmetros, entendendo como diferentes parametrizações revelam diferentes facetas da complexidade computacional e abrem caminhos inesperados para algoritmos eficientes.
Um problema parametrizado é formalmente um subconjunto de Σ* × ℕ, onde Σ é um alfabeto finito. Cada instância consiste de uma entrada clássica x e um parâmetro k que captura algum aspecto estrutural. Esta separação entre entrada e parâmetro não é meramente técnica — ela reflete uma distinção fundamental entre o tamanho do problema e sua complexidade intrínseca.
Os parâmetros mais intuitivos surgem naturalmente da formulação do problema. No problema de Cobertura por Vértices, o parâmetro natural é k, o número de vértices na cobertura desejada. Para Caminho Mais Longo, é o comprimento k do caminho procurado. Estes parâmetros naturais frequentemente correspondem ao tamanho da solução, oferecendo um ponto de partida óbvio para análise parametrizada.
Muitos problemas tornam-se tratáveis quando a estrutura subjacente tem propriedades especiais. A largura de árvore (treewidth) é um parâmetro estrutural poderoso que mede o quão próximo um grafo está de ser uma árvore. Grafos com largura de árvore pequena admitem algoritmos eficientes para muitos problemas NP-difíceis, revelando como a estrutura topológica influencia a complexidade computacional.
Uma estratégia elegante é parametrizar pela distância a casos onde o problema é fácil. Por exemplo, muitos problemas são polinomiais em grafos bipartidos. Podemos então parametrizar pela distância de edição para tornar o grafo bipartido — quantas arestas precisamos remover. Esta abordagem transforma conhecimento sobre casos especiais em algoritmos parametrizados gerais.
Às vezes, o complemento de um parâmetro oferece melhores propriedades algorítmicas. Em vez de parametrizar Vertex Cover pelo tamanho k da cobertura, podemos usar n−k, o tamanho do conjunto independente complementar. Esta parametrização dual pode revelar estruturas diferentes e levar a algoritmos mais eficientes.
Problemas complexos frequentemente se beneficiam de múltiplos parâmetros considerados simultaneamente. A análise multivariada estuda como diferentes parâmetros interagem. Por exemplo, encontrar um ciclo de comprimento k em um grafo de grau máximo d pode ser mais fácil quando ambos k e d são pequenos, mesmo que cada parâmetro isoladamente não garanta tratabilidade.
Selecionar o parâmetro apropriado é uma arte que combina intuição teórica com conhecimento do domínio de aplicação. Um bom parâmetro deve ser pequeno nas instâncias práticas, capturar a dificuldade real do problema, e permitir algoritmos eficientes. Esta escolha pode determinar a diferença entre um resultado teórico elegante mas inútil e um algoritmo que revoluciona a prática.
Em aplicações modernas, parâmetros podem mudar durante a execução ou adaptar-se à estrutura local da instância. Algoritmos adaptativos ajustam sua estratégia baseados em parâmetros descobertos durante o processamento. Esta flexibilidade permite melhor desempenho em instâncias heterogêneas, onde diferentes partes têm características estruturais distintas.
Nem toda parametrização leva a algoritmos eficientes. Resultados de impossibilidade, frequentemente baseados na Exponential Time Hypothesis (ETH), estabelecem limites inferiores para o tempo de execução. Por exemplo, k-Clique não pode ser resolvido em tempo f(k) · nᵒ⁽ᵏ⁾ para nenhuma função f, assumindo ETH. Estes limites guiam a busca por parametrizações mais promissoras.
Parâmetros não existem em isolamento — formam uma rica ecologia de relações. Alguns parâmetros dominam outros (se k₁ é pequeno, k₂ também é). Outros são incomparáveis. Mapear estas relações revela a estrutura profunda dos problemas e sugere novas direções algorítmicas. Esta "ecologia de parâmetros" é uma área ativa de pesquisa.
A escolha e análise de parâmetros é o coração da complexidade parametrizada. Como vimos, diferentes parametrizações iluminam diferentes aspectos de um problema, revelando oportunidades algorítmicas escondidas. A arte está em identificar o parâmetro que captura a essência da dificuldade enquanto permanece pequeno na prática. Com este entendimento fundamental, estamos prontos para explorar a classe FPT — o reino dos problemas que se curvam à parametrização!
No universo da complexidade computacional, a classe FPT representa uma ilha de tratabilidade em um oceano de problemas difíceis. Como uma chave-mestra que abre portas antes consideradas impenetráveis, os algoritmos FPT transformam o impossível em viável através da magia da parametrização. Neste capítulo, exploraremos esta classe fundamental, entendendo sua definição formal, suas propriedades surpreendentes e as técnicas revolucionárias que a tornam tão poderosa na prática.
Um problema parametrizado pertence à classe FPT (Fixed-Parameter Tractable) se existe um algoritmo que o resolve em tempo f(k) · p(n), onde f é uma função computável dependendo apenas do parâmetro k, p é um polinômio em n, e n é o tamanho da entrada. Esta definição captura a essência da tratabilidade parametrizada: confinar a explosão combinatória ao parâmetro, mantendo dependência polinomial do tamanho da entrada.
O problema Vertex Cover exemplifica perfeitamente FPT. Podemos determinar se um grafo tem uma cobertura de tamanho k em tempo O(2ᵏ · n²). Apesar do fator exponencial em k, para valores pequenos de k (comuns na prática), o algoritmo é extremamente eficiente. Outros habitantes ilustres de FPT incluem k-Path, Feedback Vertex Set e Fixed Alphabet Longest Common Subsequence.
A classe FPT possui propriedades de fechamento elegantes que facilitam a construção de novos algoritmos. FPT é fechada sob união, concatenação e estrela de Kleene. Se dois problemas estão em FPT, sua composição apropriada também está. Estas propriedades permitem construir algoritmos complexos a partir de blocos mais simples, uma estratégia fundamental no design algorítmico.
Muitos algoritmos FPT baseiam-se em busca exaustiva limitada pelo parâmetro. A técnica de bounded search tree constrói uma árvore de decisões com profundidade limitada por k. Cada nível representa uma escolha, e o número de escolhas é limitado. Com podas inteligentes, estas árvores mantêm tamanho administrável, resultando em algoritmos práticos para problemas NP-difíceis.
Todo problema FPT admite um algoritmo de kernelização — uma redução polinomial que transforma a instância (x, k) em uma instância equivalente (x', k') onde |x'| ≤ g(k) para alguma função g. Esta propriedade fundamental conecta FPT com pré-processamento efetivo, permitindo reduzir instâncias grandes a núcleos pequenos antes de aplicar algoritmos mais pesados.
Programação dinâmica parametrizada explora estrutura do problema para evitar recomputação. A chave é identificar um espaço de estados de tamanho f(k) · poly(n) e relações de recorrência eficientes. Esta técnica é especialmente poderosa para problemas em grafos de largura de árvore limitada, onde o espaço de estados corresponde a configurações em separadores pequenos.
Color coding é uma técnica probabilística elegante para encontrar subestruturas pequenas. Para encontrar um caminho de tamanho k, colorimos aleatoriamente vértices com k cores e procuramos um caminho colorido (todas as cores distintas). A probabilidade de sucesso é k!/kᵏ ≈ e⁻ᵏ, suficiente para garantir algoritmo FPT randomizado após repetições.
Iterative compression constrói soluções incrementalmente, mantendo uma solução comprimida durante o processo. Começamos com solução trivial para instância pequena e iterativamente adicionamos elementos, recomprimindo a cada passo. Esta técnica produziu avanços significativos para problemas como Feedback Vertex Set e Odd Cycle Transversal.
Sob a Exponential Time Hypothesis (ETH), podemos estabelecer limites inferiores precisos para problemas FPT. Por exemplo, Vertex Cover não pode ser resolvido em tempo 2ᵒ⁽ᵏ⁾ · poly(n) assumindo ETH. Estes limites guiam a busca por algoritmos ótimos e revelam trade-offs fundamentais entre o crescimento de f(k) e o grau do polinômio em n.
Quando algoritmos FPT exatos são muito lentos, podemos buscar aproximações parametrizadas. Um algoritmo é FPT-aproximação de razão α se executa em tempo FPT e garante solução dentro de fator α do ótimo. Esta relaxação frequentemente permite funções f(k) dramaticamente melhores, tornando problemas viáveis para valores maiores de k.
A classe FPT representa o triunfo da análise refinada sobre o pessimismo da complexidade clássica. Como vimos, a combinação de técnicas sofisticadas — busca limitada, kernelização, programação dinâmica, color coding — permite atacar problemas antes considerados intratáveis. Mas FPT é apenas o início da história. Alguns problemas resistem à parametrização, levando-nos ao próximo capítulo: a arte sutil da kernelização, onde aprenderemos a comprimir o universo em um grão de areia!
Imagine comprimir uma biblioteca inteira em um único livro que contém toda a sabedoria essencial. Esta é a promessa da kernelização: reduzir instâncias gigantescas a núcleos minúsculos que preservam a essência do problema. Como alquimistas modernos destilando a quintessência computacional, os algoritmos de kernelização transformam montanhas de dados em cristais de informação pura. Neste capítulo, exploraremos esta técnica fundamental que conecta teoria e prática, revelando como pré-processamento inteligente pode fazer a diferença entre o possível e o impossível.
Um kernel é uma instância reduzida equivalente ao problema original. Formalmente, um algoritmo de kernelização transforma em tempo polinomial uma instância (x, k) em uma instância (x', k') tal que: (x, k) tem solução se e somente se (x', k') tem solução, k' ≤ k, e |x'| ≤ g(k) para alguma função g. O tamanho g(k) do kernel determina a qualidade da redução.
Kernelização constrói-se sobre regras de redução — transformações locais que simplificam a instância preservando a solução. Uma regra é segura se sua aplicação não altera a resposta do problema. Regras típicas eliminam elementos irrelevantes, consolidam estruturas redundantes, ou propagam decisões forçadas. A arte está em identificar e provar a correção destas regras.
O teorema seminal de Buss estabeleceu que Vertex Cover tem kernel com O(k²) vértices. Se após aplicar regras de redução simples o grafo tem mais de k² arestas, não existe cobertura de tamanho k. Caso contrário, o grafo tem no máximo 2k² vértices. Esta observação elegante inaugurou a era moderna da kernelização.
Crown decomposition é uma técnica sofisticada que identifica estruturas crown em grafos — partições especiais que permitem redução segura. Uma crown consiste de um conjunto independente H e sua vizinhança W com matching perfeito de W em H. Remover H e incluir W na solução preserva otimalidade. Esta técnica produz kernels lineares para vários problemas.
O Sunflower Lemma de Erdős-Rado é uma ferramenta combinatória poderosa para kernelização. Uma sunflower é uma coleção de conjuntos com interseção comum (o core). Se temos muitos conjuntos de tamanho limitado, existe uma grande sunflower. Para Hitting Set, isto implica kernel polinomial: muitos conjuntos formam sunflower que permite redução.
Kernels lineares (tamanho O(k)) são o ideal para aplicações práticas. Vertex Cover admite kernel com 2k vértices através de análise refinada usando LP-relaxation. Feedback Vertex Set em torneios tem kernel com 3k vértices. Estes resultados requerem técnicas avançadas combinando estrutura do problema com argumentos probabilísticos ou algébricos.
Nem todo problema FPT admite kernel polinomial. O framework de composição OR/AND estabelece limites inferiores. Se um problema parametrizado é compositional e NP-difícil, não tem kernel polinomial a menos que NP ⊆ coNP/poly (colapso improvável da hierarquia polinomial). k-Path e k-Clique são exemplos clássicos sem kernel polinomial.
Meta-teoremas estabelecem existência de kernels para classes inteiras de problemas. Problemas definíveis em lógica de primeira ordem têm kernels lineares em grafos de grau limitado. Problemas de otimização em grafos de gênero limitado frequentemente admitem kernels polinomiais. Estes resultados gerais poupam trabalho caso-a-caso.
Kernelização Turing permite múltiplas chamadas a kernels pequenos em vez de produzir um único kernel. Um problema tem Turing kernel de tamanho g(k) se pode ser resolvido com tempo polinomial mais chamadas a instâncias de tamanho ≤ g(k). Esta relaxação permite kernels melhores para problemas como Max Leaf Spanning Tree.
Implementações eficientes de kernelização fazem diferença dramática na prática. Regras de redução são aplicadas exaustivamente até ponto fixo. Ordenação inteligente de regras evita trabalho desnecessário. Estruturas de dados incrementais mantêm informação atualizada eficientemente. Experimentos mostram reduções de 90% ou mais no tamanho de instâncias reais.
Kernelização transforma a teoria em prática, destilando a essência computacional de problemas complexos. Como vimos, a arte está em identificar estruturas redundantes e regras de redução que preservam soluções enquanto dramaticamente reduzem o tamanho. Com kernels pequenos em mãos, podemos aplicar até mesmo algoritmos exponenciais. Mas kernelização é apenas uma ferramenta no arsenal FPT. No próximo capítulo, exploraremos outra técnica fundamental: árvores de busca limitada, onde aprenderemos a navegar o espaço de soluções com precisão cirúrgica!
Como um jardineiro que poda galhos mortos para fortalecer a árvore, algoritmos de busca limitada cortam caminhos impossíveis para focar no essencial. Esta técnica elegante transforma a busca exaustiva, normalmente impraticável, em exploração cirúrgica do espaço de soluções. Neste capítulo, descobriremos como construir e analisar árvores de busca que crescem exponencialmente no parâmetro mas permanecem administráveis na prática, revelando soluções escondidas em labirintos computacionais aparentemente infinitos.
Uma árvore de busca limitada organiza decisões em estrutura hierárquica onde cada nó representa um estado parcial e cada aresta uma escolha. A profundidade máxima é limitada pelo parâmetro k, garantindo que a árvore permaneça finita. Folhas correspondem a soluções completas ou becos sem saída. O desafio está em minimizar o fator de ramificação através de regras de branching inteligentes.
Regras de branching determinam como dividir um problema em subproblemas. Uma boa regra garante progresso (reduz o parâmetro) e minimiza o número de ramos. Para Vertex Cover, a regra clássica escolhe uma aresta e ramifica: incluir um endpoint ou incluir o outro. Análise cuidadosa mostra que isto leva a árvore com O(2ᵏ) nós.
O tamanho da árvore determina a complexidade do algoritmo. Para regra com b ramos reduzindo o parâmetro por a₁, a₂, ..., aᵦ, o número de ramificação é a maior raiz real de xᵏ = xᵏ⁻ᵃ¹ + xᵏ⁻ᵃ² + ... + xᵏ⁻ᵃᵇ. O algoritmo executa em tempo O(αᵏ · poly(n)) onde α é o número de ramificação. Minimizar α é crucial para eficiência.
Condições de parada determinam quando podemos resolver diretamente sem mais ramificação. Casos base incluem: parâmetro zero (verificar solução trivial), instância vazia (sucesso ou falha óbvia), ou estrutura especial (resolver em tempo polinomial). Identificar casos base amplos reduz significativamente o tamanho da árvore.
A técnica measure and conquer usa medidas mais sofisticadas que o simples parâmetro k. Por exemplo, para Vertex Cover, podemos usar μ = k + 0.5 × (número de vértices grau 2). Regras de branching podem não reduzir k mas reduzem μ, levando a análises mais precisas e algoritmos mais rápidos.
Árvores de busca tornam-se mais poderosas quando combinadas com outras técnicas. Aplicar kernelização antes de cada ramificação mantém instâncias pequenas. Usar programação dinâmica em subproblemas evita recomputação. Crown decomposition pode eliminar ramos inteiros. Esta sinergia produz algoritmos práticos superiores.
O algoritmo de Chen-Kanj-Xia alcança O(1.2738ᵏ + kn) para Vertex Cover através de análise extremamente refinada. Usa múltiplas regras de branching dependendo da estrutura local, medida sofisticada considerando vértices de diferentes graus, e integração com kernelização forte. Este resultado exemplifica o poder da otimização cuidadosa.
Encontrar regras de branching ótimas pode ser formulado como problema de otimização quasiconvex. Dado um conjunto de estruturas locais possíveis, queremos atribuir regras minimizando o número de ramificação global. Esta abordagem automatizada descobriu regras superiores às desenvolvidas manualmente para vários problemas.
Randomização pode simplificar árvores de busca. Em vez de tentar todos os ramos, escolhemos aleatoriamente com probabilidades adequadas. Para problemas como k-SAT, isto leva a algoritmos simples com expected runtime competitivo. A análise usa martingales e concentração para garantir alta probabilidade de sucesso.
Implementar árvores de busca eficientemente requer atenção a detalhes. Usar representações incrementais evita copiar toda a instância. Ordenação de variáveis influencia drasticamente o tamanho da árvore. Poda por limites elimina ramos ruins cedo. Paralelização explora independência entre subárvores.
Árvores de busca limitada transformam força bruta em precisão cirúrgica, navegando o espaço exponencial com elegância. Como vimos, a chave está em regras de branching inteligentes, análise refinada e integração com outras técnicas. Mas nem todos os problemas sucumbem facilmente à busca. No próximo capítulo, exploraremos outra arma poderosa do arsenal FPT: programação dinâmica parametrizada, onde aprenderemos a explorar sobreposição e estrutura para conquistar problemas que desafiam abordagens diretas!
Como um arquiteto que constrói arranha-céus usando blocos pré-fabricados, a programação dinâmica parametrizada constrói soluções complexas a partir de subsoluções cuidadosamente armazenadas. Quando o parâmetro limita o espaço de estados possíveis, esta técnica clássica ganha superpoderes, resolvendo problemas NP-difíceis com eficiência surpreendente. Neste capítulo, exploraremos como estruturar recursões parametrizadas, gerenciar tabelas de memorização exponenciais no parâmetro mas polinomiais no tamanho, e extrair soluções ótimas de problemas aparentemente intratáveis.
Programação dinâmica parametrizada funciona quando o espaço de estados relevantes tem tamanho f(k) · poly(n). A chave é identificar uma parametrização que limite estados possíveis enquanto preserva a propriedade de subestrutura ótima. Diferentemente da PD clássica que frequentemente tem espaço polinomial, aqui aceitamos espaço exponencial no parâmetro em troca de tempo FPT.
Largura de árvore é o parâmetro mais importante para PD em grafos. Para grafo com largura de árvore tw, muitos problemas NP-difíceis são solúveis em tempo 2ᴼ⁽ᵗʷ⁾ · n. A decomposição em árvore fornece uma ordem de processamento onde cada separador tem tamanho ≤ tw + 1, limitando estados possíveis em cada estágio.
Nice tree decompositions simplificam algoritmos de PD padronizando a estrutura. Cada nó é de um de quatro tipos: leaf (início), introduce (adiciona vértice), forget (remove vértice), ou join (combina subárvores). Esta uniformidade permite escrever recorrências limpas para cada tipo de nó, facilitando implementação e análise.
Subset convolution é uma operação fundamental em PD parametrizada que computa, para todos os subconjuntos S, a soma sobre partições S = A ∪ B de f(A) · g(B). Ingenuamente leva tempo 3ⁿ, mas usando transformada zeta reduz para 2ⁿ · n². Esta técnica acelera muitos algoritmos em grafos de largura de árvore limitada.
Color coding combina belamente com programação dinâmica. Após colorir vértices aleatoriamente com k cores, procuramos subestrutura colorida (cores distintas) usando PD. Para k-Path, mantemos para cada subconjunto de cores e vértice v, o comprimento do maior caminho colorido terminando em v. Tempo total: 2ᵏ · n · poly(k).
Representative sets reduzem o número de estados mantidos sem perder soluções. Para família de conjuntos F, um representative set R ⊆ F preserva todas as extensões possíveis: para todo X disjunto de algum S ∈ F, existe T ∈ R disjunto de X. Isto permite manter apenas poly(k) conjuntos em vez de todos os 2ᵏ possíveis.
Cut & Count é técnica revolucionária que usa contagem modulo 2 para detectar existência. Em vez de encontrar um ciclo Hamiltoniano, contamos o número de ciclos modulo 2. Se ímpar, existe pelo menos um. O truque é contar objetos relaxados (fácil) e garantir que apenas soluções verdadeiras contribuem número ímpar.
Para problemas de conectividade, o rank-based approach mantém bases de matroids representando conectividade parcial. Em vez de lembrar todas as partições possíveis de vértices vistos, mantemos uma base de vetores sobre GF(2) que captura a mesma informação. Isto reduz estados de 2ᵏ para 2ᵏ mas com operações mais eficientes.
PD parametrizada frequentemente permite trade-offs entre tempo e espaço. Usando técnica de divisão (meet-in-the-middle), podemos resolver problemas em tempo 2ᵏ/² · poly(n) e espaço 2ᵏ/² · poly(n), em vez de tempo e espaço 2ᵏ · poly(n). Esta redução torna problemas viáveis para valores maiores de k.
Implementar PD parametrizada eficientemente requer cuidado. Bit-packing permite representar estados compactamente. Ordenação de estados melhora localidade de cache. Poda elimina estados impossíveis. Paralelização explora independência entre estados. Tabelas hash evitam alocar memória para estados não-visitados.
Programação dinâmica parametrizada transforma problemas intratáveis em cálculos sistemáticos quando a estrutura certa é identificada. Como vimos, a combinação com decomposições em árvore, color coding, e técnicas algébricas produz algoritmos surpreendentemente eficientes. Mas nem todos os problemas sucumbem a estas técnicas. No próximo capítulo, exploraremos o lado sombrio da parametrização: a W-hierarquia, onde descobriremos problemas que resistem a todos os esforços de parametrização eficiente!
Nem toda montanha pode ser escalada pelo mesmo caminho. Na complexidade parametrizada, a W-hierarquia mapeia os picos intransponíveis — problemas que resistem a algoritmos FPT mesmo quando o parâmetro é pequeno. Como cartógrafos do impossível, exploraremos esta hierarquia de dureza, entendendo por que alguns problemas parametrizados permanecem teimosamente difíceis e como provar que um problema provavelmente não admite solução eficiente. Este conhecimento é poder: saber quando parar de procurar algoritmos impossíveis e buscar alternativas.
A W-hierarquia consiste de classes W[1], W[2], ..., W[P], cada uma capturando um nível diferente de intratabilidade parametrizada. FPT ⊆ W[1] ⊆ W[2] ⊆ ... ⊆ W[P] ⊆ XP, com conjectura de que todas as inclusões são estritas. Problemas W[1]-completos como k-Clique são os análogos parametrizados dos problemas NP-completos.
A W-hierarquia origina-se de problemas sobre circuitos booleanos. O weft de um circuito é a profundidade máxima de gates grandes (fan-in > 2). W[t] contém problemas redutíveis ao weighted satisfiability de circuitos de weft t. Esta caracterização conecta complexidade parametrizada com estrutura de circuitos, fornecendo ferramentas poderosas para provar dureza.
k-Clique pergunta se existe um subgrafo completo com k vértices. Apesar da simplicidade, não conhecemos algoritmo f(k) · nᴼ⁽¹⁾. A dureza de k-Clique estabelece intratabilidade de muitos outros problemas via reduções. Sob ETH, k-Clique requer tempo nᵒ⁽ᵏ⁾, estabelecendo limite inferior preciso.
Uma redução FPT de problema A para B transforma instância (x, k) de A em (x', k') de B onde: k' ≤ g(k) para alguma função g, a transformação leva tempo f(k) · poly(|x|), e (x, k) ∈ A ⟺ (x', k') ∈ B. Estas reduções preservam tratabilidade FPT e estabelecem dureza relativa.
k-Dominating Set (encontrar k vértices que dominam todo o grafo) é W[2]-completo, estritamente mais difícil que k-Clique (assumindo W[1] ≠ W[2]). A diferença intuitiva: Clique tem estrutura "local" (pares), enquanto Dominating Set tem estrutura "global" (cobertura). Esta distinção reflete-se na complexidade de circuitos correspondentes.
Subindo na hierarquia encontramos problemas ainda mais complexos. W[3] contém problemas com estrutura de três níveis, W[4] com quatro, e assim por diante. W[P] captura problemas parametrizados análogos a problemas completos para P, como Circuit Value com poucas gates. W[SAT] e W[P] representam o topo da complexidade parametrizada "razoável".
A classe XP contém problemas solucionáveis em tempo nᶠ⁽ᵏ⁾ para alguma função f. Todo problema em W[t] está em XP, mas nem todo problema XP está na W-hierarquia. XP representa o limite entre parametricamente tratável (mesmo que não FPT) e completamente intratável. k-Coloração está em XP mas não em FPT (assumindo W[1] ≠ FPT).
A Exponential Time Hypothesis (ETH) postula que 3-SAT não pode ser resolvido em tempo 2ᵒ⁽ⁿ⁾. ETH implica limites inferiores precisos para problemas parametrizados. Por exemplo, k-Clique não pode ser resolvido em tempo f(k) · nᵒ⁽ᵏ⁾ para nenhuma função f. Strong ETH (SETH) fornece bounds ainda mais refinados.
Problemas W[1]-difíceis não admitem kernels polinomiais (assumindo coNP ⊈ NP/poly). Esta conexão entre W-hierarquia e kernelização fornece ferramenta poderosa: provar W[1]-dureza implica automaticamente ausência de kernel polinomial. Composition frameworks estabelecem estes resultados formalmente.
Quando um problema é W[1]-difícil para parâmetro natural, alternativas incluem: considerar parâmetros diferentes (re-parametrização), buscar aproximações FPT, restringir a classes especiais de instâncias, ou aceitar algoritmos XP para casos com k muito pequeno. A intratabilidade raramente é absoluta — é questão de perspectiva.
A W-hierarquia revela a paisagem da intratabilidade parametrizada, mapeando os limites do possível. Como vimos, nem todo problema sucumbe à parametrização, e entender estas barreiras é crucial para direcionar esforços produtivamente. Mas mesmo quando algoritmos exatos FPT são impossíveis, nem tudo está perdido. No próximo capítulo, exploraremos como aproximação e parametrização se combinam para produzir soluções práticas para problemas W-difíceis!
Quando a perfeição é impossível, a excelência ainda pode ser alcançável. Os algoritmos de aproximação parametrizada navegam o espaço entre o ideal inatingível e o prático necessário, oferecendo soluções com garantias de qualidade em tempo FPT. Como artesãos que sabem quando o acabamento perfeito daria trabalho infinito, estes algoritmos trocam precisão absoluta por eficiência dramática. Neste capítulo, descobriremos como combinar as duas grandes estratégias para lidar com intratabilidade — aproximação e parametrização — criando algoritmos que são simultaneamente rápidos e bons.
Um algoritmo de α-aproximação FPT encontra, em tempo f(k) · poly(n), uma solução de tamanho no máximo α · k quando existe solução de tamanho k. Esta definição captura o melhor de dois mundos: tempo de execução eficiente quando o parâmetro é pequeno e garantia de qualidade da solução. Para problemas W[1]-difíceis, esta pode ser a única esperança de algoritmos práticos.
Vertex Cover admite 2-aproximação simples: escolher ambos endpoints de um matching maximal. Surpreendentemente, combinar com parametrização produz algo mais forte: podemos decidir em tempo O(1.2738ᵏ + kn) se existe cobertura de tamanho k, ou produzir cobertura de tamanho no máximo 2k. Este algoritmo é simultaneamente FPT exato e 2-aproximação.
Um FPT approximation scheme (FPT-AS) produz (1+ε)-aproximação em tempo f(k, 1/ε) · poly(n). Para problemas em grafos planares, muitos admitem FPT-AS via técnica de Baker: particionar em camadas, resolver otimamente em cada camada, combinar soluções. O erro vem de ignorar arestas entre camadas, controlável escolhendo largura apropriada.
Frequentemente existe trade-off suave entre qualidade da aproximação e tempo de execução. Para k-Center em grafos, podemos obter 3-aproximação em tempo O(n²), 2-aproximação em tempo 2ᴼ⁽ᵏ⁾ · n², ou solução exata em tempo nᴼ⁽ᵏ⁾. A escolha depende do valor de k e da qualidade desejada.
Problemas W[1]-difíceis como k-Clique resistem a algoritmos FPT exatos, mas admitem aproximações interessantes. Podemos encontrar clique de tamanho Ω(k/log n) quando existe clique de tamanho k, em tempo FPT. Para k-Dominating Set, existe O(log k)-aproximação FPT, dramaticamente melhor que O(log n) possível em tempo polinomial.
Reduções que preservam aproximação são cruciais para estabelecer limites de aproximabilidade. Uma gap-creating reduction de A para B transforma instâncias sim de A em instâncias com solução ≤ k em B, e instâncias não em instâncias com solução > α·k. Isto implica que α-aproximar B é tão difícil quanto decidir A.
Programação linear parametrizada oferece caminho para aproximação FPT. Relaxamos o problema para LP, resolvemos otimamente, então arredondamos considerando o parâmetro. Para Vertex Cover, o LP-relaxation naturalmente produz kernel de tamanho 2k, que pode ser resolvido exatamente. Esta técnica generaliza para muitos problemas de covering e packing.
Randomização facilita aproximação parametrizada. Para Maximum Agreement Forest, sampling aleatório de árvores produz aproximação esperada dependendo de k. Color coding naturalmente dá aproximação: se não encontramos caminho colorido, ainda temos garantia probabilística. Derandomização preserva aproximação mas aumenta complexidade.
Sob hipóteses da complexidade, podemos provar limites precisos de aproximabilidade FPT. Assumindo Gap-ETH, k-Independent Set em grafos bipartidos admite PTAS mas não FPTAS (assumindo W[1] ≠ FPT).
Algoritmos adaptativos ajustam a razão de aproximação baseados na estrutura da instância. Para grafos com treewidth tw, muitos problemas admitem (1 + ε)-aproximação em tempo 2ᴼ⁽ᵗʷ/ε⁾ · n. A aproximação melhora automaticamente quando a instância tem estrutura favorável, sem conhecimento prévio desta estrutura.
A aproximação parametrizada representa o pragmatismo na complexidade computacional — reconhecendo que perfeição nem sempre é necessária ou possível. Como vimos, combinar aproximação com parametrização produz algoritmos práticos para problemas teoricamente intratáveis. Esta abordagem híbrida oferece esperança onde métodos puros falham. No próximo capítulo, exploraremos o domínio onde estas técnicas mais brilham: problemas em grafos, onde estrutura e parametrização se encontram!
Grafos são o playground natural da complexidade parametrizada. Como teias que capturam relações entre objetos, grafos modelam redes sociais, circuitos, moléculas, mapas e infinitas outras estruturas. A riqueza de parâmetros em grafos — grau, conectividade, largura de árvore, gênero — oferece múltiplas perspectivas para atacar problemas difíceis. Neste capítulo, exploraremos como a complexidade parametrizada revolucionou algoritmos em grafos, transformando problemas clássicos intratáveis em rotinas computacionais eficientes quando a estrutura certa é explorada.
Grafos oferecem zoo rico de parâmetros estruturais. Largura de árvore mede proximidade a árvores. Degenerescência captura esparsidade. Gênero quantifica complexidade topológica. Cada parâmetro revela diferentes aspectos da estrutura, e problemas intratáveis em geral frequentemente tornam-se FPT quando estes parâmetros são pequenos.
Vertex Cover e seus primos formam família central em grafos parametrizados. Edge Cover, Connected Vertex Cover, Feedback Vertex Set — cada variante tem suas peculiaridades. Vertex Cover admite kernel linear e algoritmo O(1.2738ᵏ). Feedback Vertex Set, mais complexo, tem algoritmo O(3.592ᵏ · n²) após décadas de melhorias.
Encontrar caminhos com propriedades especiais é fundamental em grafos. k-Path (caminho com k vértices) é FPT via color coding em tempo O(2ᵏ · n³). k-Disjoint Paths, surpreendentemente, também é FPT com algoritmo complexo de Robertson-Seymour. Longest Path parametrizado por treewidth admite algoritmo 2ᴼ⁽ᵗʷ ˡᵒᵍ ᵗʷ⁾ · n.
Problemas de coloração mostram dicotomia interessante. Chromatic Number é W[1]-difícil parametrizado pelo número de cores, mas FPT parametrizado por treewidth. List Coloring é mais difícil ainda. Graph Coloring em grafos de grau máximo d admite algoritmo O((d+1)ᵏ · n), mostrando como restrições estruturais ajudam.
Dominating Set é W[2]-completo, fundamentalmente mais difícil que Vertex Cover. Mas em grafos planares, admite kernel linear e algoritmo 2ᴼ⁽√ᵏ⁾ · n. Em grafos de degenerescência d, é FPT com algoritmo (d+1)ᵏ · n. Variantes como Connected Dominating Set e Independent Dominating Set têm complexidades distintas.
Grafos planares e, mais geralmente, H-minor-free admitem algoritmos dramaticamente melhores. Muitos problemas NP-difíceis têm algoritmos 2ᴼ⁽√ᵏ⁾ · n em planares via técnica de branch-decomposition. Bidimensionality theory fornece framework geral: problemas que crescem com o tamanho da grade admitem algoritmos subexponenciais.
Tree decomposition é a ferramenta mais poderosa para grafos estruturados. Computar treewidth ótimo é NP-difícil, mas FPT parametrizado pelo próprio treewidth. Uma vez obtida decomposição, muitos problemas NP-difíceis são solucionáveis em tempo 2ᴼ⁽ᵗʷ⁾ · n ou 2ᴼ⁽ᵗʷ ˡᵒᵍ ᵗʷ⁾ · n via programação dinâmica.
Robertson-Seymour Graph Minor Theory tem conexões profundas com complexidade parametrizada. Todo problema closed under minors é FPT (Graph Minor Theorem). k-Disjoint Paths, fundamental na teoria, tem algoritmo f(k) · n³ extremamente complexo. Minor testing é FPT mas com constantes astronômicas.
Manter soluções em grafos dinâmicos sob mudanças é desafiador. Para Vertex Cover, podemos manter 2-aproximação com update time O(log n). Solução exata de tamanho k pode ser mantida com updates em tempo f(k) · log n. Esta área conecta complexidade parametrizada com algoritmos dinâmicos.
Em grafos aleatórios, muitos parâmetros têm valores típicos conhecidos. Treewidth de G(n,p) é Θ(n) com alta probabilidade. Mas problemas específicos podem ser mais fáceis: Vertex Cover em G(n,p) tem kernel esperado O(k²/p). Análise smoothed parametrizada estuda comportamento típico em vez de pior caso.
Grafos são o domínio onde complexidade parametrizada mais brilha, oferecendo algoritmos práticos para problemas centrais em ciência da computação. A riqueza de parâmetros estruturais, desde grau até treewidth, fornece múltiplas avenidas para atacar problemas difíceis. Como vimos, escolher o parâmetro certo transforma o impossível em rotineiro. No capítulo final, veremos como estas técnicas impactam o mundo real, desde redes sociais até biologia computacional!
A teoria encontra a prática quando algoritmos parametrizados resolvem problemas reais que afetam milhões de pessoas. De redes sociais que conectam bilhões a descobertas de medicamentos que salvam vidas, a complexidade parametrizada silenciosamente potencializa tecnologias transformadoras. Neste capítulo final, exploraremos aplicações concretas onde identificar e explorar parâmetros pequenos faz a diferença entre o computacionalmente impossível e o rotineiramente solucionável, revelando como ideias abstratas se materializam em impacto tangível.
Redes sociais massivas parecem intratáveis, mas exibem parâmetros pequenos cruciais. O fenômeno small-world significa diâmetro pequeno. Comunidades têm alta modularidade. Influenciadores formam conjuntos dominantes pequenos. Algoritmos FPT para k-community detection, influence maximization e link prediction exploram estas estruturas, processando redes com bilhões de nós.
Redes de interação proteína-proteína, vias metabólicas e redes regulatórias gênicas exibem estruturas parametrizadas. Motifs funcionais são pequenos (k ≤ 10). Pathways críticos têm comprimento limitado. Algoritmos FPT para motif finding, pathway extraction e module detection revolucionaram a biologia computacional, permitindo descobertas impossíveis com força bruta.
Compiladores modernos usam extensivamente algoritmos parametrizados. Register allocation em blocos básicos tem treewidth pequeno. Instruction scheduling tem dependências limitadas. Loop optimization explora profundidade de aninhamento pequena. Estes parâmetros permitem otimizações agressivas que seriam impossíveis em grafos gerais.
Verificar propriedades de software é computacionalmente desafiador, mas sistemas reais têm estrutura explorável. Bounded model checking limita profundidade de execução. Programas têm treewidth pequeno em seu control flow graph. Algoritmos FPT verificam propriedades críticas de segurança em sistemas que controlam aviões, usinas e dispositivos médicos.
Redes de telecomunicações enfrentam problemas de roteamento complexos com restrições rígidas. O número de caminhos alternativos k é tipicamente pequeno. Wavelength assignment em redes ópticas tem poucos comprimentos de onda. Algoritmos FPT para k-disjoint paths e wavelength routing permitem comunicação global instantânea e confiável.
Seleção de features é crucial em machine learning. O número k de features relevantes é geralmente pequeno comparado ao total. Algoritmos FPT para k-feature selection, sparse regression e rule learning encontram modelos interpretáveis e eficazes. Regularização naturalmente induz sparsidade, criando parâmetros pequenos.
Query optimization em bancos de dados é NP-difícil, mas queries reais têm estrutura. O número de joins k é pequeno. Query graphs frequentemente têm treewidth baixo. Algoritmos FPT otimizam queries complexas em tempo viável, permitindo analytics em tempo real sobre petabytes de dados.
IA para jogos usa extensivamente técnicas parametrizadas. Árvores de busca têm profundidade limitada. Branching factor é pequeno após podas. Pathfinding em mapas tem estrutura (grids, navmeshes). Algoritmos FPT permitem IA competitiva em tempo real, criando experiências imersivas e desafiadoras.
Problemas criptográficos exploram dureza parametrizada. Lattice problems com dimensão pequena são FPT mas difíceis para dimensão crescente. Code-based cryptography usa distância de Hamming como parâmetro. Post-quantum schemes frequentemente baseiam segurança em problemas parametrizados, preparando-nos para era de computação quântica.
Cidades inteligentes enfrentam problemas de otimização massivos com estrutura parametrizada. Roteamento de veículos tem frota limitada. Smart grids têm profundidade hierárquica pequena. Alocação de recursos considera poucos tipos. Algoritmos FPT otimizam energia, transporte e recursos, criando cidades mais sustentáveis e habitáveis.
A complexidade parametrizada continuará expandindo fronteiras. Quantum parameterized complexity explorará algoritmos quânticos FPT. Distributed parameterized algorithms resolverão problemas em escala planetária. Machine-learned parameters descobrirão estruturas automaticamente. A interseção de parametrização com outras áreas promete revoluções que mal podemos imaginar.
A complexidade parametrizada transformou nossa compreensão do que é computacionalmente possível. Ao identificar e explorar estruturas escondidas, resolvemos problemas que pareciam impossíveis. Das redes sociais que conectam humanidade à descoberta de medicamentos que salvam vidas, algoritmos parametrizados silenciosamente potencializam o mundo digital. A mensagem é clara: a intratabilidade raramente é absoluta — é questão de encontrar o parâmetro certo. Com as ferramentas que exploramos neste livro, você está equipado para identificar oportunidades onde outros veem apenas impossibilidade, transformando desafios computacionais em soluções elegantes que fazem diferença real no mundo!
Este volume sobre Complexidade Parametrizada reúne décadas de pesquisa revolucionária que transformou nossa compreensão sobre algoritmos e complexidade. As referências abrangem desde os trabalhos seminais de Downey e Fellows até desenvolvimentos recentes em algoritmos quânticos parametrizados. Esta bibliografia oferece recursos essenciais para aprofundamento em cada aspecto da área, desde fundamentos teóricos até aplicações práticas transformadoras.
CYGAN, Marek et al. Parameterized Algorithms. Cham: Springer, 2015.
DOWNEY, Rodney G.; FELLOWS, Michael R. Parameterized Complexity. New York: Springer-Verlag, 1999.
DOWNEY, Rodney G.; FELLOWS, Michael R. Fundamentals of Parameterized Complexity. London: Springer, 2013.
FLUM, Jörg; GROHE, Martin. Parameterized Complexity Theory. Berlin: Springer, 2006.
FOMIN, Fedor V.; KRATSCH, Dieter. Exact Exponential Algorithms. Berlin: Springer, 2010.
NIEDERMEIER, Rolf. Invitation to Fixed-Parameter Algorithms. Oxford: Oxford University Press, 2006.
BRASIL. Base Nacional Comum Curricular: Educação é a Base. Brasília: MEC/CONSED/UNDIME, 2018.
ALON, Noga; YUSTER, Raphael; ZWICK, Uri. Color-coding. Journal of the ACM, v. 42, n. 4, p. 844-856, 1995.
BODLAENDER, Hans L. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, v. 25, n. 6, p. 1305-1317, 1996.
BODLAENDER, Hans L. et al. On problems without polynomial kernels. Journal of Computer and System Sciences, v. 75, n. 8, p. 423-434, 2009.
BUSS, Jonathan F.; GOLDSMITH, Judy. Nondeterminism within P. SIAM Journal on Computing, v. 22, n. 3, p. 560-572, 1993.
CAI, Liming; CHEN, Jianer. On fixed-parameter tractability and approximability of NP optimization problems. Journal of Computer and System Sciences, v. 54, n. 3, p. 465-474, 1997.
CHEN, Jianer; KANJ, Iyad A.; XIA, Ge. Improved upper bounds for vertex cover. Theoretical Computer Science, v. 411, n. 40-42, p. 3736-3756, 2010.
CHEN, Jianer et al. Tight lower bounds for certain parameterized NP-hard problems. Information and Computation, v. 201, n. 2, p. 216-231, 2005.
CHITNIS, Rajesh et al. Directed subset feedback vertex set is fixed-parameter tractable. ACM Transactions on Algorithms, v. 11, n. 4, article 28, 2015.
COURCELLE, Bruno. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation, v. 85, n. 1, p. 12-75, 1990.
CYGAN, Marek et al. On problems as hard as CNF-SAT. ACM Transactions on Algorithms, v. 12, n. 3, article 41, 2016.
DEMAINE, Erik D.; HAJIAGHAYI, MohammadTaghi. Bidimensionality: new connections between FPT algorithms and PTASs. In: Proceedings of SODA 2005, p. 590-601.
DIESTEL, Reinhard. Graph Theory. 5th ed. Berlin: Springer, 2017.
DOM, Michael; LOKSHTANOV, Daniel; SAURABH, Saket. Kernelization lower bounds through colors and IDs. ACM Transactions on Algorithms, v. 11, n. 2, article 13, 2014.
DREYFUS, Stuart E.; WAGNER, Robert A. The Steiner problem in graphs. Networks, v. 1, n. 3, p. 195-207, 1971.
DRUCKER, Andrew. New limits to classical and quantum instance compression. SIAM Journal on Computing, v. 44, n. 5, p. 1443-1479, 2015.
ERDŐS, Paul; KO, Chao. On a combinatorial problem in Latin rectangles. Canadian Journal of Mathematics, v. 13, p. 177-198, 1961.
FELLOWS, Michael R. et al. The complexity ecology of parameters: An illustration using bounded max leaf number. Theory of Computing Systems, v. 45, n. 4, p. 822-848, 2009.
FERNAU, Henning. Parameterized Algorithmics: A Graph-Theoretic Approach. Habilitationsschrift, Universität Tübingen, 2005.
FOMIN, Fedor V. et al. Kernels for feedback arc set in tournaments. Journal of Computer and System Sciences, v. 77, n. 6, p. 1071-1078, 2011.
FOMIN, Fedor V.; LOKSHTANOV, Daniel; SAURABH, Saket. Efficient computation of representative sets with applications in parameterized and exact algorithms. Journal of the ACM, v. 63, n. 6, article 53, 2016.
FOMIN, Fedor V. et al. Sharp separation and applications to exact and parameterized algorithms. Algorithmica, v. 63, n. 3, p. 692-706, 2012.
GAREY, Michael R.; JOHNSON, David S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1979.
GRAMM, Jens et al. Data reduction and exact algorithms for clique cover. Journal of Experimental Algorithmics, v. 13, article 2, 2008.
GUO, Jiong; NIEDERMEIER, Rolf. Invitation to data reduction and problem kernelization. ACM SIGACT News, v. 38, n. 1, p. 31-45, 2007.
HERMELIN, Danny; WU, Xi. Weak compositions and their applications to polynomial lower bounds for kernelization. In: Proceedings of SODA 2012, p. 104-113.
IMPAGLIAZZO, Russell; PATURI, Ramamohan. On the complexity of k-SAT. Journal of Computer and System Sciences, v. 62, n. 2, p. 367-375, 2001.
IMPAGLIAZZO, Russell; PATURI, Ramamohan; ZANE, Francis. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, v. 63, n. 4, p. 512-530, 2001.
JANSEN, Bart M. P.; BODLAENDER, Hans L. Vertex cover kernelization revisited. Theory of Computing Systems, v. 53, n. 2, p. 263-299, 2013.
KABANETS, Valentine; CAI, Jin-Yi. Circuit minimization problem. In: Proceedings of STOC 2000, p. 73-79.
KARP, Richard M. Reducibility among combinatorial problems. In: MILLER, R. E.; THATCHER, J. W. (Eds.). Complexity of Computer Computations. New York: Plenum Press, 1972. p. 85-103.
KLOKS, Ton. Treewidth: Computations and Approximations. Berlin: Springer, 1994.
KNEIS, Joachim et al. Divide-and-color. In: Proceedings of WG 2006, LNCS 4271, p. 58-67.
KOUTIS, Ioannis; WILLIAMS, Ryan. Limits and applications of group algebras for parameterized problems. ACM Transactions on Algorithms, v. 12, n. 3, article 31, 2016.
KRATSCH, Stefan. Recent developments in kernelization: A survey. Bulletin of the EATCS, n. 113, p. 58-97, 2014.
LOKSHTANOV, Daniel et al. Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS, n. 105, p. 41-72, 2011.
MARX, Dániel. Parameterized graph separation problems. Theoretical Computer Science, v. 351, n. 3, p. 394-406, 2006.
MARX, Dániel. Parameterized complexity and approximation algorithms. The Computer Journal, v. 51, n. 1, p. 60-78, 2008.
MOREIRA, João C. Algoritmos e Estruturas de Dados. São Paulo: Editora UFU, 2019.
NAOR, Moni; SCHULMAN, Leonard J.; SRINIVASAN, Aravind. Splitters and near-optimal derandomization. In: Proceedings of FOCS 1995, p. 182-191.
NEMHAUSER, George L.; TROTTER, Leslie E. Vertex packings: Structural properties and algorithms. Mathematical Programming, v. 8, n. 1, p. 232-248, 1975.
PAPADIMITRIOU, Christos H. Computational Complexity. Reading: Addison-Wesley, 1994.
REED, Bruce; SMITH, Kaleigh; VETTA, Adrian. Finding odd cycle transversals. Operations Research Letters, v. 32, n. 4, p. 299-301, 2004.
ROBERTSON, Neil; SEYMOUR, Paul D. Graph minors XIII: The disjoint paths problem. Journal of Combinatorial Theory, Series B, v. 63, n. 1, p. 65-110, 1995.
SAURABH, Saket; ZEHAVI, Meirav. Parameterized complexity of multi-node hubs. Journal of Computer and System Sciences, v. 119, p. 60-74, 2021.
SOUZA, Alexander. Teoria da Computação: Uma Introdução. 3ª ed. Rio de Janeiro: Elsevier, 2018.
THOMASSÉ, Stéphan. A 4k² kernel for feedback vertex set. ACM Transactions on Algorithms, v. 6, n. 2, article 32, 2010.
WILLIAMS, Ryan. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, v. 348, n. 2-3, p. 357-365, 2005.