Ссылка для (нечетных, анти-дырочных) графиков?

16

Графы без X - это графы, которые не содержат графов из X в качестве индуцированного подграфа. Отверстие представляет собой цикл, по крайней мере 4 -х вершин. Нечетное отверстие представляет собой отверстие с нечетным числом вершин. Antihole является дополнением дырки.

Графики (нечетные дыры, нечетные дыры) являются в точности идеальными графами; это сильная теорема о совершенном графе . Можно найти самый большой независимый набор (и самую большую клику) в идеальном графе за полиномиальное время, но единственный известный способ сделать это требует создания полуопределенной программы для вычисления тэта-числа Ловаша .

Графы без дыр, без отверстий называются слабо хордовыми и представляют собой довольно легкий класс для многих задач (включая НЕЗАВИСИМЫЙ НАБОР и КЛИК ).

Кто-нибудь знает, были ли изучены или написаны (нечетные, анти-дырочные) графы?

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

Эквивалентно, каждый хочет найти самый большой независимый набор для (дырочных, нечетных-анти-дырочных) графов. Сянь-Чи Чанг ниже указывает, почему это более интересный класс для НЕЗАВИСИМОГО НАБОРА, чем (нечетные, анти-дырочные) графы.

Андраш Саламон
источник

Ответы:

12

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

В разделе 2 статьи « Триангулированные окрестности в графах без четных отверстий » да Сильва и Вускович заявили, что Фарбер впервые показывает

О(N2)

Тогда их основная теорема утверждала, что

О(N+м)О(N2м)

О(N2м)

К2,м¯


Редактировать:

О, еще одна мысль вышла. (дырочные, анти-дырочные) графы почти слабо хордальны в следующем смысле: поскольку без 4-дырочных подразумевает, что существуют только анти-дыры с размером 4 ~ 7 (любая k-анти-дырка с размером> 7 содержит 4 отверстия), и он также не содержит лишних отверстий, что ограничивает размер отверстий до 4 и 6, на графике почти нет отверстий / антиотверстий! Таким образом, алгоритм многовременности кажется правдоподобным для таких графиков.

Сянь-Чжи Чан 張顯 之
источник
К2,мм2
1
Благодарность! Еще раз посмотрев на мой результат с Питером Дживонсом, мы фактически показали, что задачи с древовидными ограничениями дают графы, не содержащие дыр, нечетных отверстий, в которых нужно найти наибольшее независимое множество. Я уточню вопрос - я неправильно предположил, что IS - это проблема, которую нужно решить.
Андрас Саламон
@ AndrásSalamon Можете ли вы дать открытый доступ к препринтам вашей работы на эту тему? Я не мог получить доступ через прокси моего университета ни
Диего де Эстрада
@DiegodeEstrada: Я был бы рад выслать вам препринт нашей статьи CP 2008, просто отправьте мне письмо. Тем не менее, это действительно бумага с ограничениями, поэтому она может быть вам не интересна.
Андрас Саламон