Encontre todos os sub-gráficos completos em um gráfico

Question

Existe um algoritmo ou método conhecido para encontrar todos os sub-gráficos completos em um gráfico? Eu tenho um gráfico não direcionado e não ponderado e preciso encontrar todos os subgrafos dentro dele, onde cada nó no subgrafão está conectado um ao outro no subgraf.

Existe um algoritmo existente para isso?

Answer 1

Isso é conhecido como o Problema de clique; É difícil e está no NP-completo em geral, e sim, há muitos algoritmos para fazer isso.

Se o gráfico possui propriedades adicionais (por exemplo, é bipartido), o problema se tornará consideravelmente mais fácil e é solucionável no tempo polinomial, mas, caso contrário, é muito difícil e é completamente solucionável apenas para pequenos gráficos.

Da Wikipedia

Na ciência da computação, o problema da camarilha refere -se a qualquer um dos problemas relacionados à localização de subgrafos completos específicos ("Cliques") em um gráfico, ou seja, conjuntos de elementos em que cada par de elementos está conectado.

Os problemas de clique incluem:

• Encontrando a camarilha máxima (uma camarilha com o maior número de vértices),
• Encontrar uma camarilha de peso máxima em um gráfico pesado,
• Listando todas as panelinhas máximas (panelinhas que não podem ser ampliadas)
• Resolvendo o problema de decisão de testar se um gráfico contém uma camarilha maior que um determinado tamanho.

Esses problemas são difíceis: o problema da decisão da camarilha é o NP-Presente (um dos 21 problemas de preenchimento de 21 np do KARP), o problema de encontrar a camarilha máxima é o parâmetro fixo intratável e difícil de se aproximar, e listar todos os cliques máximos podem exigir Tempo exponencial, pois existem gráficos com exponencialmente muitas panelinhas máximas. No entanto, existem algoritmos para esses problemas que são executados em tempo exponencial ou que lidam com certos gráficos de entrada mais especializados no tempo polinomial.

Veja também

• Algoritmo Bron -Kebosch

Answer 2

Bem, o problema de encontrar um sub-vertex K em um gráfico de tamanho n é de complexidade

O (n^kk^2)

Já que existem n^k subgrafos para verificar e cada um deles tem k^2 arestas.

O que você está solicitando, encontrar todos os subgrafos em um gráfico é um problema de preenchimento NP e é explicado no algoritmo Bron-Berbosch listado acima.