Localizando o maior subgrafo induzido sem cliques

Considere este problema:

Dado um gráfico não direcionado $G = (V, E)$ , encontrar $G' = (V', E')$ de tal modo que:

$G'$ é um subgrafo induzido de $G$

$G'$ não tem 3 panelinhas

$|V'|$ é máximo

Portanto, o menor número de vértices deve ser eliminado de $G$ para que 3 cliques sejam eliminados.

Um problema equivalente seria encontrar uma coloração 2 para $G$ tal que se $(v_1, v_2, v_3) \in V$ e $((v_1, v_2), (v_2, v_3), (v_3, v_1)) \in V$ ,

$(v_1.color == v_2.color \wedge v_2.color == v_3.color \wedge v_3.color == v_1.color) = False$
A diferença (absoluta) entre o número de nós com a cor 1 e o número de nós com a cor 2 é máxima.

Alguém pode pensar em um algoritmo de tempo polinomial para resolver um desses problemas?

algorithms graph-theory graphs optimization Alexandre
fonte

Você sabe que não é um algoritmo de tempo polinomial, ou você está apenas esperando por um?

Luke Mathieson

Acabei de perceber que suas duas definições do problema não correspondem! O segundo impõe a condição de que o subgráfico induzido por

V - V^{'}

$V-V'$ também é livre de triângulo. Eu sei que é NP-Complete determinar até se existe uma partição: cstheory.stackexchange.com/questions/65/h-free-cut-problem . Embora a descrição inicial permita o gráfico induzido de

V - V^{'}

$V-V'$ para conter triângulos. Qual é o correto?

Aryabhata

@LukeMathieson: Eu acredito que os gráficos de uma classe têm soluções em tempo polinomial porque cheguei ao problema acima com o seguinte problema, que tem solução em tempo polinomial: "Dado um conjunto de N intervalos inteiros, escolha o maior número possível, para que nenhum 3 se cruze . "

Alexandre

@ Alexandre: Os gráficos de intervalo são especiais. Problemas conhecidos de NP-Hard estão em P, quando restritos a gráficos de intervalo.

Aryabhata

@Aryabhata: O subgráfico induzido é G 'e não pode ter três cliques. Portanto, ele não pode ter triângulos, exatamente o mesmo que a segunda descrição.

Alexandre

Localizando o maior subgrafo induzido sem cliques

Respostas: