¿Está contando camarillas máximas en un gráfico de incomparabilidad # P-completo?

De acuerdo con este resumen para "La complejidad de contar cortes y calcular la probabilidad de que un gráfico esté conectado" (SIAM J. Comput. 12 (1983), pp. 777-788), contar anti-cadenas en un orden parcial es # P-completo. No tengo acceso a este documento, así que no puedo decir si este resultado cubre el máximo anti-cadenas o no.

mhum
fuente

@ András: Creo que su resultado es contar las antichains (que no son necesariamente máximas). Puede ser fácil ver que contar antichains máximos también es # P-completo, pero no puedo verlo.

Tsuyoshi Ito

@ András: La pregunta es sobre antichains máximas, no antichains de máxima cardinalidad. No he estudiado la reducción en el documento, por lo que tal vez su reducción también demuestre la completitud # P de contar las antichains máximas al mismo tiempo, pero al menos son problemas diferentes.

Tsuyoshi Ito

@ Tsuyoshi: tienes razón, el papel Provan / Ball solo muestra que contar antichains de máxima cardinalidad es # P-difícil. Volver a la mesa de dibujo ...

András Salamon

En realidad, si observa la prueba, verá que la compleción de # P se prueba para una clase de posets en la que todas las antichains máximas tienen la misma cardinalidad. Es decir, comience con cualquier gráfico bipartito

con

vértices y construya un gráfico bipartito

con

vértices agregando

vértices nuevos

. Entonces, si

es una bipartición del conjunto de vértices de

, defina un poset en

G = (V, E)

$G=(V,E)$

n

$n$

G^{'}

$G'$

2 n

$2n$

n

$n$

nuevas aristas

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

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

n

$n$

configurando

son adyacentes en

. Entonces esto responde mi pregunta.

{(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 el

¿Está contando camarillas máximas en un gráfico de incomparabilidad # P-completo?

Respuestas: