Задача сэндвич-графа - Graph sandwich problem

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

Задачи сэндвича с графами обобщают проблему проверки принадлежности данного графа к семейству графов и привлекают внимание из-за своих приложений и как естественное обобщение задач распознавания.[1]

Постановка задачи

Точнее, учитывая набор вершин V, обязательный набор ребер E1, и больший набор ребер E2, график грамм = (V, E) называется бутерброд график для пары грамм1 = (V, E1), грамм2 = (V, E2) если E1 ⊆ E ⊆ E2. задача сэндвича с графом для свойства определяется следующим образом:[2][3]

Задача графического сэндвича для собственности Π:
Пример: Набор вершин V и кромочные наборы E1 ⊆ E2 ⊆ V × V.
Вопрос: Есть ли график грамм = (V, E) такие, что E1 ⊆ E ⊆ E2 и грамм удовлетворяет свойству Π?

В проблема распознавания для класса графов (удовлетворяющих свойству Π) эквивалентно конкретной задаче о сэндвиче графов, где E1 = E2, то есть необязательный набор ребер пуст.

Вычислительная сложность

Задача сэндвича с графом: НП-полный когда Π - свойство быть хордовый граф, график сопоставимости, граф перестановок, хордовый двудольный граф, или же цепной граф.[2][4] Ее можно решить за полиномиальное время для разбить графы,[2][5] пороговые графики,[2][5] и графы, в которых каждые пять вершин содержат не более одной четырехвершинной индуцированный путь.[6]Также установлен статус сложности для ЧАС-сэндвич-задачи со свободным графом для каждого из четырёхвершинных графов ЧАС.[7]

Рекомендации

  1. ^ Голумбик, Мартин Чарльз; Тренк, Энн Н. (2004), "Глава 4. Графики интервальных пробников и сэндвич-задачи", Графики допусков, Кембридж, стр. 63–83..
  2. ^ а б c d Голумбик, Мартин Чарльз; Каплан, Хаим; Шамир, Рон (1995), "Задачи сэндвича с графом", J. Алгоритмы, 19: 449–473, Дои:10.1006 / jagm.1995.1047.
  3. ^ Голумбик, Мартин Чарльз (2004), Алгоритмическая теория графов и совершенные графы, Анналы дискретной математики, 57 (2-е изд.), Elsevier, p. 279.
  4. ^ de Figueiredo, C.MH .; Faria, L .; Klein, S .; Sritharan, R. (2007), "О сложности сэндвич-задач для сильно хордовых графов и хордовых двудольных графов", Теоретическая информатика, 381 (1–3): 57–67, Дои:10.1016 / j.tcs.2007.04.007, МИСТЕР  2347393.
  5. ^ а б Махадев, Н.В.Р .; Пелед, Ури Н. (1995), Графики пороговых значений и связанные темы, Анналы дискретной математики, 57, Северная Голландия, стр. 19–22..
  6. ^ Дантас, С .; Klein, S .; Mello, C.P .; Моргана, А. (2009), "Задача сэндвича с графом для п4-резкие графики », Дискретная математика, 309: 3664–3673, Дои:10.1016 / j.disc.2008.01.014.
  7. ^ Дантас, Симона; де Фигейредо, Селина М.Х .; Маффре, Фредерик; Тейшейра, Рафаэль Б. (2013), "Сложность задач сэндвича с запрещенным подграфом и проблема сэндвича с косым разбиением", Дискретная прикладная математика: Доступно онлайн 11 октября 2013 г., Дои:10.1016 / j.dam.2013.09.004.

дальнейшее чтение

  • Дантас, Симона; де Фигейредо, Селина М.Х .; да Силва, Мурило В.Г .; Тейшейра, Рафаэль Б. (2011), "О запрещенной проблеме индуцированного сэндвича подграфа", Дискретная прикладная математика, 159: 1717–1725, Дои:10.1016 / j.dam.2010.11.010.