As relações de equivalência cobrem o problema (na teoria dos grafos)

Uma relação de equivalência em um conjunto de vértices finito pode ser representada por um gráfico não direcionado que é uma união disjunta de cliques. O conjunto de vértices representa os elementos e uma aresta representa que dois elementos são equivalentes.

Se eu tiver um gráfico e os gráficos , dizemos que é coberto por se o conjunto de arestas de for igual à união dos conjuntos de arestas de . Os conjuntos de de não precisam ser separados. Observe que qualquer gráfico não direcionado pode ser coberto por um número finito de relações de equivalência (ou seja, gráficos de união desunida de cliques). $G$ $G_1,\dots,G_k$ $G$ $G_1,\dots,G_k$ $G$ $G_1,\dots,G_k$ $G_1,\dots,G_k$ $G$

Eu tenho várias perguntas:

O que se pode dizer sobre o número mínimo de relações de equivalência necessárias para cobrir um gráfico ? $G$
Como podemos calcular esse número mínimo?
Como podemos calcular uma cobertura mínima explícita de , ou seja, um conjunto de relações de equivalência cujo tamanho é mínimo e que cobrem ? $G$ $G$
Esse problema tem algum aplicativo além da lógica da partição (a dupla da lógica dos subconjuntos )?
Esse problema tem um nome bem estabelecido?

Dados os vários mal-entendidos indicados pelos comentários, aqui estão algumas fotos para ilustrar esses conceitos. Se você tem uma idéia para uma terminologia mais fácil de entender (em vez de "capa", "relação de equivalência", "união dissociada de panelinhas" e "união não dissociada" de conjuntos de arestas), fique à vontade para me informar.

Aqui está uma imagem de um gráfico e uma relação de equivalência que o cobre:

Aqui está uma figura de um gráfico e duas relações de equivalência que o cobrem:
deve ser bastante óbvio que pelo menos duas relações de equivalência são necessárias.

Aqui está uma figura de um gráfico e três relações de equivalência que o cobrem:
É menos óbvio que pelo menos três relações de equivalência são necessárias. O lema 1.9 do Dual da lógica de subconjuntos pode ser usado para mostrar que isso é verdade. A generalização desse lema para operações de nand com mais de duas entradas foi a motivação para esta questão.

algorithms graph-theory clique Thomas Klimpel
fonte

É um problema conhecido do NP-Complete . en.wikipedia.org/wiki/Clique_cover_problem

gardenhead

@StephenBly Talvez seja um problema bem conhecido, mas o link da wikipedia que você forneceu não me ajuda. O artigo fala sobre um problema de cobertura de vértice, mas a questão aqui se refere a um problema de cobertura de borda. Observe também que uma relação de equivalência não é uma camarilha, mas uma união desunida de panelinhas.

Thomas Klimpel

Como assim, uma relação de equivalência é uma união desunida de panelinhas? O conjunto de vértices representa os elementos e uma aresta representa que dois elementos são equivalentes. Se essa não é a representação que você está usando, deixe claro.

gardenhead

@StephenBly Eu não acho que seja o mesmo problema, o problema de capa de clique pede o número mínimo de cliques que cobre os vértices do gráfico, aqui buscamos o número mínimo de relações de equivalência para cobrir as bordas do gráfico. É fácil ver que o limite superior é nesse caso, pois podemos particionar qualquer gráfico de vértices na maioria correspondências .

n - 1

$n-1$

n

$n$

n - 1

$n-1$

Chao Xu

@YuvalFilmus A pergunta é sobre o menor número de relações de equivalência cuja união é exatamente a relação de aresta do gráfico fornecido, e não cuja união apenas inclui o gráfico fornecido.

David Richerby

Respostas:

$\text{eq}(G)$ $\text{cc}(G)$

Existem classes gráficas especiais em que o valor exato ou um bom limite superior para qualquer número é conhecido. Em geral, até onde eu sei, os melhores limites são dados por Alon [1]:

{registro}_{2} n - {registro}_{2} d \leq eq (G) \leq cc (G) \leq 2 e^{2} (Δ + 1 1)^{2} em n,

$\log_2 n - \log_2 d \leq \text{eq}(G) \leq \text{cc}(G) \leq 2e^2 (\Delta+1)^2 \ln n,$

$\Delta$ $G$ $\lceil n^2/4 \rceil$

$\sf NP$ $\text{eq}(G)$ $\sf NP$

[1] Alon, Noga. "Cobrindo gráficos pelo número mínimo de relações de equivalência." Combinatorica 6.3 (1986): 201-206.

[2] Blokhuis, Aart e Ton Kloks. "Na equivalência, cobrindo o número de gráficos divididos." Information processing letters 54.5 (1995): 301-304.

[3] Kučera, Luděk, Jaroslav Nešetřil e Aleš Pultr. "Complexidade da dimensão três e algumas características relacionadas à cobertura de borda dos gráficos." Teórico Computer Science 11.1 (1980): 93-106.

Juho
fonte

O corolário 1.3 de [1] é exatamente o que eu precisava (na versão que se aplica aos complementos de um caminho). Agora não tenho mais uma desculpa para não escrever o artigo sobre a implicação geral "(A, B, C, ...) implica (Z, Y, X, ...)" (a sequência do cálculo sequencial) na partição lógica e lógicas não clássicas semelhantes. Mas acho que não vou escrever por pelo menos mais meio ano. E talvez até encontre uma nova desculpa enquanto isso.

22415 Thomas Thomas Klimpel em 11/03

@ThomasKlimpel Isso é ótimo! (Não é o fato de que você pode encontrar uma nova desculpa, mas que este foi útil :-))

Juho

Embora eu não saiba o nome para esse problema, posso mostrar que esse problema é difícil de NP.

Para um gráfico livre de triângulo, todas as classes de equivalência devem ser correspondentes. O número mínimo de classes de equivalência que cobre o gráfico é igual ao índice cromático do gráfico.

De acordo com este artigo , encontrar o índice cromático para um gráfico livre de triângulo é NP-completo.

Chao Xu
fonte