Является ли подсчет максимальных кликов в графе несопоставимости # P-полным?

Этот вопрос мотивирован вопросом MathOverflow Пэна Чжана . Валиант показал, что подсчет максимальных клик в общем графе является # P-полным, но что если мы ограничимся графами несопоставимости (т. Е. Мы хотим подсчитать максимальные антицепи в конечном множестве)? Этот вопрос кажется достаточно естественным, и я подозреваю, что он рассматривался ранее, но я не смог найти его в литературе.

cc.complexity-theory counting-complexity partial-order clique Тимоти Чоу
источник

Согласно этому реферату для «Сложности подсчета срезов и вычисления вероятности того, что граф связан» (SIAM J. Comput. 12 (1983), pp. 777-788), подсчет антицепей в частичном порядке равен # P-полной. У меня нет доступа к этой статье, поэтому я не могу сказать, охватывает ли этот результат максимальные антицепи или нет.

mhum
источник

@ Андрас: Я думаю, что их результат о подсчете антицепей (которые не обязательно максимальны). Может быть легко увидеть, что подсчет максимальных антицепей также # P-завершен, но я не вижу этого.

Цуёси Ито

@ Андрас: Вопрос о максимальных антицепях, а не максимальных кардинальных антицепях. Я не изучал сокращение в статье, поэтому, возможно, их сокращение также доказывает # P-полноту подсчета максимальных антицепей одновременно, но, по крайней мере, это разные проблемы.

Цуёси Ито

@ Tsuyoshi: вы правы, бумага Provan / Ball показывает, что подсчет антицепей максимальной мощности равен # P-hard. Вернуться к чертежной доске ...

Андрас Саламон

На самом деле, если вы посмотрите на доказательство, то увидите, что # P-полнота доказана для класса множеств, в котором все максимальные антицепи имеют одинаковую мощность. А именно, начните с любого двудольного графа

вершинами и постройте двудольный граф

вершинами, добавив

новых вершин

новых ребер

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$

. Затем, если

- это двоякое разделение множества вершин

, определите poset на

, задав

если

смежны в

. Так что это ответ на мой вопрос.

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

Тимоти Чоу

Является ли подсчет максимальных кликов в графе несопоставимости # P-полным?

Ответы: