stringtranslate.com

Проблема графового сэндвича

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

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

Постановка проблемы

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

Задача о сэндвиче графа для свойства Π :
Пример: множество вершин V и множества ребер E 1 ⊆ E 2 ⊆ V × V .
Вопрос: Существует ли граф G = ( V , E ) такой, что E 1 ⊆ E ⊆ E 2 и G удовлетворяет свойству Π ?

Задача распознавания класса графов (удовлетворяющих свойству Π) эквивалентна конкретной задаче сэндвича графа, где E 1  =  E 2 , то есть необязательное множество ребер пусто.

Сложность вычислений

Задача сэндвича с графом является NP-полной , когда Π является свойством быть хордовым графом , графом сравнимости , графом перестановок , хордовым двудольным графом или цепным графом . [2] [4] Она может быть решена за полиномиальное время для разделенных графов , [2] [5] пороговых графов , [2] [5] и графов, в которых каждые пять вершин содержат не более одного четырехвершинного индуцированного пути . [6] Статус сложности также был установлен для задач сэндвича с графом без H для каждого из четырехвершинных графов H. [7]

Ссылки

  1. ^ Golumbic, Martin Charles; Trenk, Ann N. (2004), «Глава 4. Интервальные пробные графики и сэндвич-задачи», Tolerance Graphs , Cambridge, стр. 63–83.
  2. ^ abcd Golumbic, Martin Charles; Kaplan, Haim; Shamir, Ron (1995), "Проблемы сэндвича с графами", J. Algorithms , 19 (3): 449–473, doi :10.1006/jagm.1995.1047.
  3. ^ Golumbic, Martin Charles (2004), Алгоритмическая теория графов и совершенные графы, Annals of Discrete Mathematics, т. 57 (2-е изд.), Elsevier, стр. 279, ISBN 978-0-08-052696-6.
  4. ^ de Figueiredo, CMH; Faria, L.; Klein, S.; Sritharan, R. (2007), "О сложности сэндвич-задач для сильно хордовых графов и хордовых двудольных графов", Theoretical Computer Science , 381 (1–3): 57–67, doi : 10.1016/j.tcs.2007.04.007 , MR  2347393.
  5. ^ ab Mahadev, NVR; Peled, Uri N. (1995), Пороговые графы и смежные темы, Annals of Discrete Mathematics, т. 57, North-Holland, стр. 19–22, ISBN 978-0-08-054300-0.
  6. ^ Дантас, С.; Кляйн, С.; Мелло, К. П.; Моргана, А. (2009), «Проблема сэндвича с графами для P 4 -разреженных графов», Дискретная математика , 309 (11): 3664–3673, doi : 10.1016/j.disc.2008.01.014.
  7. ^ Dantas, Simone; de ​​Figueiredo, Celina MH; Maffray, Frédéric; Teixeira, Rafael B. (2013), «Сложность проблем сэндвича с запрещенными подграфами и проблема сэндвича с косым разбиением», Discrete Applied Mathematics , 182 : 15–24, doi : 10.1016/j.dam.2013.09.004.

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