Приближаемость проблемы рода

11

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


источник

Ответы:

8

Лучшие опубликованные результаты представлены в статье 1997 года Джианера Чена, Сароджи П. Канчи и Аркадия Каневского.

  • Для любого фиксированного вычисление рода графа с аддитивной ошибкой O ( n ε ) является NP-трудным.ε>0O(nε)

  • ngmax{4g,g+4n}

  • O(n)

Остается открытым вопрос, существует ли эффективный алгоритм аппроксимации с постоянным множителем.

Jeffε
источник
2
O(nε)O(nε)
Да, ты прав. Я обновил свой ответ в свете твоего.
Джефф
5

Я хотел бы добавить к исчерпывающему ответу JɛE, что, насколько мне известно, нет нижних границ для коэффициента аппроксимации для этой задачи. Насколько нам известно, может существовать алгоритм аппроксимации, который всегда дает приближение с постоянным множителем (даже если род очень мал).

O(n1ε)Ggenus(G)ggenus(G)g+1gnGkN=nkGGgenus(G)Nggenus(G)N(g+1)genus(G)N=(Nn)k/k+1=|V(G)|k/k+1=|V(G)|1εε=1/(k+1)N(g+1)Ngg+1g

Юрий
источник