Проблема сэндвича с графом
В теории графов и информатике проблема сэндвича графов — это проблема поиска графа, который принадлежит определенному семейству графов и «зажат» между двумя другими графами, один из которых должен быть подграфом, а другой — подграфом. суперграф искомого графа.
Сэндвич-задачи графов обобщают проблему проверки принадлежности данного графа семейству графов и привлекают внимание из-за ихприложений и как естественное обобщение задач распознавания. [1]
Постановка задачи [ править ]
Точнее, для данного набора вершин V обязательное множество ребер E 1 , и большее множество ребер E 2 , граф G = ( V , E ) называется сэндвич -графом для пары Г 1 = ( В , Е 1 ), Г 2 = ( В , Е 2 ) если Э 1 ⊆ Е ⊆ Е 2 .Проблема сэндвича с графами для свойства Π определяется следующим образом: [2] [3]
- Проблема сэндвича с графом для свойства Π :
- Экземпляр: набор вершин V и наборы ребер E. 1 ⊆ Е 2 ⊆ V × V .
- Вопрос: Существует ли граф G = ( V , E ) такой, что E 1 ⊆ Е ⊆ Е 2 и G удовлетворяет свойству Π ?
Проблема распознавания класса графов (удовлетворяющих свойству Π)эквивалентно конкретной проблеме сэндвича с графами, где Э 1 = Е 2 , то есть необязательный набор ребер пуст.
Вычислительная сложность [ править ]
Проблема сэндвича с графами является NP-полной, когда Π является свойством быть хордальным графом , графом сравнимости , графом перестановок , хордальным двудольным графом или цепным графом . [2] [4] ее можно решить за полиномиальное время Для разделенных графов . [2] [5] пороговые графики , [2] [5] четырьмя вершинами и графы, в которых каждые пять вершин содержат не более одного пути, индуцированного . [6] Статус сложности также был установлен для H. задач сэндвича с графами без для каждого из четырёхвершинных графов H . [7]
Ссылки [ править ]
- ^ Голумбик, Мартин Чарльз; Тренк, Энн Н. (2004), «Глава 4. Интервальные пробные графы и сэндвич-задачи», Графики толерантности , Кембридж, стр. 63–83 .
- ↑ Перейти обратно: Перейти обратно: а б с д Голумбик, Мартин Чарльз; Каплан, Хаим; Шамир, Рон (1995), «Проблемы сэндвича с графами», J. Algorithms , 19 : 449–473, doi : 10.1006/jagm.1995.1047 .
- ^ Голумбик, Мартин Чарльз (2004), Алгоритмическая теория графов и совершенные графы , Анналы дискретной математики, том. 57 (2-е изд.), Elsevier, с. 279 .
- ^ де Фигейредо, CMH; Фариа, Л.; Кляйн, С.; Шритаран, Р. (2007), «О сложности сэндвич-задач для сильно хордальных графов и хордальных двудольных графов», Theoretical Computer Science , 381 (1–3): 57–67, doi : 10.1016/j.tcs.2007.04 .007 , МР 2347393 .
- ↑ Перейти обратно: Перейти обратно: а б Махадев, NVR; Пелед, Ури Н. (1995), Пороговые графики и связанные с ними темы , Анналы дискретной математики, том. 57, Северная Голландия, стр. 19–22 .
- ^ Дантас, С.; Кляйн, С.; Мелло, CP; Моргана, А. (2009), «Проблема сэндвича с графами для P 4 -разреженных графов», Discrete Mathematics , 309 : 3664–3673, doi : 10.1016/j.disc.2008.01.014 .
- ^ Дантас, Симона; де Фигейредо, Селина М.Х.; Маффрэ, Фредерик; Тейшейра, Рафаэль Б. (2013), «Сложность сэндвич-проблем с запрещенными подграфами и сэндвич-проблем с косыми разбиениями», Дискретная прикладная математика : доступно онлайн с 11 октября 2013 г., номер документа : 10.1016/j.dam.2013.09.004 .
Дальнейшее чтение [ править ]
- Дантас, Симона; де Фигейредо, Селина М.Х.; да Силва, Мурило В.Г.; Тейшейра, Рафаэль Б. (2011), «О сэндвич-проблеме с запрещенными индуцированными подграфами», Discrete Applied Mathematics , 159 : 1717–1725, doi : 10.1016/j.dam.2010.11.010 .