Сложность подсчета всех связанных подграфов

Пусть G связный граф.

Какова сложность подсчета всех связанных подграфов, если G имеет следующие типы?

G является общим.

Г плоская.

G является двудольным.

Я не забочусь о каких-либо структурах или ..., просто нужно сосчитать все связанные подграфы! Меня также интересует сложность подсчета всех связанных подграфов с ровно k узлами в G.

Указатели на документы и книги также приветствуются!

cc.complexity-theory graph-theory counting-complexity marjoonjan
источник

Знаете ли вы, что список в вопросе не отформатирован правильно? meta.cstheory.stackexchange.com/questions/300/… Если вас не интересует форматирование, это нормально. Но я не уверен, что кто-то захочет тратить время на ответ на ваш вопрос, если вы не хотите тратить время на его форматирование. (Я не говорю, что знаю ответ.)

Tsuyoshi Ito

Кроме того, вас интересует перечисление связанных подграфов произвольного размера / порядка / структуры / ... или вы хотите, чтобы они были связующими, или что-то еще?

Энтони Лабарр

Там, кажется, работает на подсчете связанных охватывающих подграфов. Страница 32 из "многомерного полинома Тутта" Сокаля связывает полином от охватывающего подграфа с полиномом надежности, который имеет огромную литературу

Ярослав Булатов

Извините, мой предыдущий ответ об использовании теоремы Кирхгофа был неверным. Я думал об аргументе включения-исключения, но это может быть неосуществимо.

2010 года,

Этот документ не совсем то, что вы просили, но документ и его ссылки могут помочь в разработке некоторых идей.

MS Dousti

Ответы:

Уэльс утверждает, что задача # P-завершена даже в самом ограниченном случае (считая числа связанных подграфов плоского двудольного графа). См. Стр. 305 в Welsh, Dominic (1997), «Приблизительный подсчет», « Обзоры в комбинаторике» , Bailey, RA, ed., Cambridge University Press, pp. 287–324.

В контексте, однако, мне интересно, действительно ли он имеет в виду связанные охватывающие подграфы. И это заставляет меня задаться вопросом, какую версию проблемы вы хотите: связанные охватывающие подграфы, связанные подграфы, которые не должны быть охватывающими, или связанные индуцированные подграфы?

Дэвид Эппштейн
источник

Это ответ на ответ Дэвида. Еще не взглянув на эту книгу, я бы предположил, что проблема заключается в подсчете связанных охватывающих подграфов, потому что это точка x = 1 y = 2 полинома Тутте, и автор заинтересовался этим. Но на самом деле я думаю, что эти три проблемы довольно легко сводятся к подсчету проблемы связного связующего подграфа. Следующие сокращения должны работать для точного подсчета или приближения, хотя я думаю, что проблема для приближения все еще открыта.

Подсчет связанных охватывающих подграфов сводится к подсчету связанных подграфов (эскиз): возьмем график G, в котором мы хотим подсчитать охватывающие подграфы. Прикрепите к каждой вершине. Если выбрано достаточно большим, типичные связанные подграфы полученного графа соответствуют N-to-1 связанным остовным подграфам в G, где N легко вычислить. $K_A$ $A$

Подсчет связанных охватывающих подграфов сводится к подсчету связанных индуцированных подграфов (эскиз): пусть G будет графом, в котором мы хотим подсчитать охватывающие подграфы. Разделите каждое ребро на два, так что теперь есть | V | + | E | Вершины. Прикрепите к каждой из исходных вершин, которые были в G. Если выбран достаточно большим, типичные связные индуцированные подграфы полученного графа соответствуют N-to-1 связным остовным подграфам в G, где N легко вычислить. $K_A$ $A$

Вот еще одна интерпретация вопроса: как насчет подсчета немаркированных связанных подграфов? Это трудно даже для деревьев: Л. Голдберг и М. Jerrum, Counting немаркированные поддеревьев дерева # Р-Complete, LMS Журнал вычислений и математики, 3 (2000) 117-124. $\#P$

Колин Маккуиллан
источник

Вам не нужно прикреплять клику, верно? Вы можете прикрепить все, что имеет много связанных подграфов, при условии, что вы прикрепляете одно и то же к каждой вершине. Таким образом, вы могли бы сделать эти сокращения, сохраняя при этом как планарность, так и двухчастность.

Дэвид Эппштейн