Le comptage des cliques maximales dans un graphique d'incomparabilité # P-complet?

Selon cet abrégé pour «La complexité du comptage des coupes et du calcul de la probabilité qu'un graphique soit connecté» (SIAM J. Comput. 12 (1983), pp. 777-788), compter les anti-chaînes dans un ordre partiel est # P-complet. Je n'ai pas accès à ce document, donc je ne peux pas dire si ce résultat couvre ou non les chaînes maximales.

mhum
la source

@ András: Je pense que leur résultat est de compter les antichaines (qui ne sont pas forcément maximales). Il peut être facile de voir que le comptage des antichaines maximales est également # P-complet, mais je ne le vois pas.

Tsuyoshi Ito

@ András: La question concerne les antichaines maximales, pas les antichaines à cardinalité maximale. Je n'ai pas étudié la réduction du papier, alors peut-être que leur réduction prouve également la complétude # P de compter les antichaines maximales en même temps, mais au moins ce sont des problèmes différents.

Tsuyoshi Ito

@Tsuyoshi: vous avez raison, le papier Provan / Ball montre seulement que compter les antichaines à cardinalité maximale est # P-difficile. Retour à la planche à dessin ...

András Salamon

En fait, si vous regardez la preuve, vous verrez que l'exhaustivité # P est prouvée pour une classe de posets dans laquelle toutes les antichaines maximales ont la même cardinalité. A savoir, commencez par n'importe quel graphe biparti

avec

sommets et construisez un graphe biparti

avec

sommets en ajoutant

nouveaux sommets

nouveaux arêtes

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$

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

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

V_{1}

$V_1$

V_{2}

$V_2$ est une bipartition de l'ensemble de sommets de

, définir un poset sur

en réglant

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'$

Le comptage des cliques maximales dans un graphique d'incomparabilité # P-complet?

Réponses: