A contagem de cliques máximas em um gráfico de incomparabilidade é # P-complete?

De acordo com este resumo de "A complexidade da contagem de cortes e da computação da probabilidade de um gráfico ser conectado" (SIAM J. Comput. 12 (1983), pp. 777-788), a contagem de anti-cadeias em uma ordem parcial é # P-completo. Não tenho acesso a este artigo, portanto, não sei dizer se esse resultado cobre o máximo de anti-cadeias ou não.

mhum
fonte

@ András: Eu acho que o resultado deles é a contagem de antichains (que não são necessariamente máximos). Pode ser fácil ver que a contagem de antichains máximos também é # P-completa, mas não consigo ver.

Tsuyoshi Ito

@ András: A questão é sobre antichains máximos, não antichains de cardinalidade máxima. Não estudei a redução no artigo, portanto, talvez a redução deles também prove a # P-perfeição de contar antichains máximos ao mesmo tempo, mas pelo menos são problemas diferentes.

Tsuyoshi Ito

@ Tsuyoshi: você está certo, o artigo da Provan / Ball mostra apenas que a contagem de antichains de cardinalidade máxima é difícil. De volta à prancheta ...

András Salamon

Na verdade, se você olhar para a prova, verá que a completude P é comprovada para uma classe de posets em que todos os antichains máximos têm a mesma cardinalidade. Nomeadamente, começar com qualquer bipartido gráfico

com

vértices e construir um gráfico bipartido

com

vértices por adição de

novos vértices

novas arestas

G = (V, E)

$G=(V,E)$

n

$n$

G^{'}

$G'$

2 n

$2n$

n

$n$

{v^{'} : v \in V}

$\{v' : v\in V\}$

n

$n$

. Então, se

é uma bipartição do conjunto de vértices de

, defina um poset em

configurando

são adjacentes em

. Então, isso responde à minha pergunta.

{(v, v^{'}) : v \in V}

$\{(v,v'): v\in V\}$

V_{1}

$V_1$

V_{2}

$V_2$

G^{'}

$G'$

V_{1} \cup V_{2}

$V_1\cup V_2$

x < y

$x<y$

x \in V_{1}

$x\in V_1$

y \in V_{2}

$y\in V_2$

x

$x$

y

$y$

G^{'}

$G'$

Timothy Chow

A contagem de cliques máximas em um gráfico de incomparabilidade é # P-complete?

Respostas: