Трудные задачи для графов высшего рода

17

Планарные графы имеют род ноль. Графы, встраиваемые в тор, имеют род не более 1. Мой вопрос прост:

Есть ли какие-нибудь проблемы, которые полиномиально разрешимы на плоских графах, но NP-трудны на графах рода один?
В более общем смысле, существуют ли проблемы, которые полиномиально разрешимы на графах рода g, но NP-трудны на графах рода> g?

cc.complexity-theory ds.algorithms graph-theory planar-graphs Шива Кинтали
источник

Что касается второго вопроса, хотите ли вы, чтобы задача была NP-трудной для графов рода> = k, где k - это константа, превышающая g? ИЛИ вы просто хотите, чтобы задача была NP-трудной для графов, род которых не меньше g (что эквивалентно тому, что NP-сложна для общих графов)?

Робин Котари

1

Я ищу задачи NP-Hard для графов рода> = k, где k - константа, большая чем g.

Шива Кинтали

16

Это гласность моей собственной работы, но число пересечений и 1-планарность тривиально разрешимы на плоских графах, но трудно для графов рода один. См. Http://arxiv.org/abs/1203.5944

кто то
источник

3

«График близок к плоскому, если его можно получить из плоского графа путем добавления ребра. График является 1-плоским, если на нем есть чертеж, где каждое ребро пересекается не более чем одним другим ребром. Мы показываем, что это NP -трудно решить, является ли данный близкий планарный граф 1-планарным. " Я должен что-то упустить. Почему не каждый почти плоский план также является 1-плоским?

Тайсон Уильямс

4

Я думаю, что вы говорите, что вы можете просто взять плоское вложение

и добавить ребро обратно. Однако этот дополнительный ребро может пересечь более одного ребра, нарушив 1-плоскость.

G - e

$G-e$

Тимоти Сан

@TimothySun Да. Каждое ребро, кроме

будет пересечено не более одного раза (

), но

может быть пересечено более чем одним другим ребром, что недопустимо. Благодарю.

e

$e$

e

$e$

e

$e$

Тайсон Уильямс

4

Если проблемы с игрушкой в порядке:

Пусть и некоторый граф рода . Для с CNF-формулы, пусть некоторого кодирование как плоский графом плюс дизъюнктной копию . $g\in\mathbb{N}$ $H$ $g+1$ $\phi$ $G_\phi$ $\phi$ $H$

Учитывая , который является графом рода , NP-трудно решить, выполнимо ли . Эта проблема, однако, становится тривиальной, когда она ограничена графами рода . $G_\phi$ $g+1$ $\phi$ $\leq g$

Раду Куртиканский
источник

2

что это за проблема на графах рода

\leq g

$\leq g$

Сашо Николов

1

Все графы

имеют род

. Таким образом, если вы ограничите задачу графами рода

, вы всегда можете отказаться.

G_{ϕ}

$G_\phi$

g + 1

$g+1$

g

$g$

Раду Куртикапей

ах, это становится действительно тривиальным, я вижу

Сашо Николов

2

РЕДАКТИРОВАТЬ (2012-09-05): Джефф и Раду комментарии правы. Приведенный результат не отвечает на вопрос. Для того, чтобы расширить комментарий Radu, вот является связанным алгоритмом с помощью Бравого , который дает алгоритм для контрактов matchgate тензоров на графу с родом с временем выполнения где - минимальное количество ребер, которые нужно удалить из , чтобы сделать его плоским. $G$ $g$ $T=poly(n) + 2^{2g} O(m^3)$ $m$ $G$

Cai, Lu и Xia недавно доказали следующую дихотомию проблем подсчета #CSP:

Доказаны теоремы о дихотомии сложности в рамках подсчета задач CSP. Локальные функции ограничения принимают логические входные данные и могут быть произвольными действительными симметричными функциями. Мы доказываем, что каждая проблема в этом классе принадлежит именно к трем категориям:

(1) те, которые можно вычислить (т. Е. Вычислить за полиномиальное время) на общих графах, или
(2) те, которые # P-сложны на общих графах, но прослеживаемы на плоских графах , или
(3) те, которые # P-сложны даже на плоских графиках.

Критерии классификации явные.

Мартин Шварц
источник

2

Это не отвечает на вопрос. Можно ли разделить категорию (2) на (2a), пригодные для плоских графов, но # P-hard для тороидальных графов и (2b), пригодные для графов ограниченного рода, но # P-hard для графов неограниченного рода?

Джефф

3

Случай (2) состоит из задач, которые могут быть сведены к подсчету идеальных совпадений в плоских графах путем введения локальных плоских гаджетов. Он также известен , что совершенные паросочетания можно пересчитать за полиномиальное время на ограниченном-роде граф. Таким образом, все задачи в случае (2) фактически разрешимы на графах ограниченного рода.

Раду Куртикапин

2

$g$ $g$ $X_g$ $g$ $g$ $g$ $X_g$ $g$

$\mathcal C$ $\mathcal C$

Дэвид Ричерби
источник

Трудные задачи для графов высшего рода

Ответы: