Двойственно хордальный граф

Неориентированный граф G двойственно хордален, если гиперграф его максимальных клик является гипердеревом. Имя происходит из факта, что граф хордален тогда и только тогда, когда гиперграф его максимальных клик двойственен гипердереву. Первоначально эти графы были определены по максимальному соседству и имеют ряд различных описаний[1][2][3]. В отличие от хордальных графов свойство двойственной хордальности не наследуется, то есть, порождённые подграфы двойственного хордального графа не обязательно двойственно хордальны (в смысле наследства двойственно хордальные графы являются в точности наследниками строго хордальных графов), и двойственно хордальный граф в общем случае не совершенный. Двойственно хордальные графы появились первоначально под именем HT-графы[4][5][6].

Описание

Двойственно хордальные графы являются графами клик хордальных графов[7][8], то есть, графами пересечений максимальных клик хордальных графов.

Следующие свойства эквивалентны[1][2][9][5][6]:

  • G имеет упорядочения максимального соседства (англ. maximum neighborhood ordering)[10].
  • Есть остовное дерево T графа G такое, что любая максимальная клика графа G порождает поддерево в T.
  • Гиперграф замкнутого соседства N(G) графа G является гипердеревом.
  • Гиперграф максимальных клик графа G является гипердеревом.
  • G является 2-секционным графом гипердерева.

Из условия на гиперграф замкнутого соседства также следует, что граф двойственно хордален тогда и только тогда, когда его квадрат хордален и его гиперграф замкнутого соседства имеет свойство Хелли.

В статье Де Кариа и Гутирреза[11] двойственные хордальные графы описываются в терминах свойств сепараторов. В статье Брешара[12] показано, что двойственные хордальные графы являются в точности графами пересечений максимальных гиперкубов графов ацикличных кубических комплексов.

Структуру и алгоритмическое использование дважды хордальных графов дала Марина Москарини[13]. Это хордальные графы, являющиеся одновременно и двойственно хордальными.

Распознавание

Двойственно хордальные графы могут быть распознаны за линейное время, а также упорядочение максимального соседства двойственного хордального графа может быть найдено за линейное время[2][4].

Сложность проблем

В то время как основные задачи, такие как поиск максимального независимого множества, максимальной клики, раскраски и кликового покрытия остаются NP-полными для двойственных хордальных графов, некоторые варианты задачи о минимальном доминирующем множестве и дереве Штейнера эффективно решаются для двойственных хордальных графов (но задача независимого доминирования остаётся NP-полной)[2][5][6]. См. статью Бранштэдта, Чепоя и Драгана[14] для использования свойств двойственных хордальных графов для задач с остовными деревьями, и статью Бранштэдта, Ляйтерта и Раутенбаха[15] для алгоритма линейного времени поиска доминирования вершин и рёбер.

Примечания
  1. Andreas Brandstädt, Feodor Dragan, Victor Chepoi, Vitaly Voloshin. Dually Chordal Graphs // Lecture Notes in Computer Science. — 1993. — Т. 790. — С. 237–251.
  2. Andreas Brandstädt, Victor Chepoi, Feodor Dragan. The algorithmic use of hypertree structure and maximum neighborhood orderings // Discrete Applied Mathematics. — 1998. — Т. 82. — С. 43–77. — doi:10.1016/s0166-218x(97)00125-x.
  3. Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — ISBN 0-89871-432-X.
  4. Feodor Dragan. Centers of Graphs and the Helly Property (in Russian). — Ph.D. thesis, Moldova State University, Moldova, 1989.
  5. Feodor Dragan, Chiril Prisacaru, Victor Chepoi. Location problems in graphs and the Helly property (in Russian) // Discrete Math. (Moscow). — 1992. — Т. 4. — С. 67–73.; Ф. Ф. Драган, К. Ф. Присакарь, В. Д. Чепой. Задачи размещения на графах и свойство Хелли // Дискрет. матем.. — 1992. — Т. 4, вып. 4. — С. 67–73.; Федор Федорович Драган. Центры в графах и свойство Хелли. — Минск: АН БССР. Ин-т математики, 1989. — (автореферат дис. кандидата физико-математических наук: 01.01.09).
  6. Feodor Dragan. HT-graphs: centers, connected r-domination and Steiner trees // Comput. Sci. J. of Moldova (Kishinev). — 1993. — Т. 1. — С. 64–83.
  7. Marisa Gutierrez, Oubina. Metric Characterizations of proper Interval Graphs and Tree-Clique Graphs // Journal of Graph Theory. — 1996. — Т. 21. — С. 199–205. — doi:10.1002/(sici)1097-0118(199602)21:2<199::aid-jgt9>3.0.co;2-m.
  8. Jayme L. Szwarcfiter, Claudson F. Bornstein. Clique Graphs of Chordal and Path Graphs // SIAM Journal on Discrete Mathematics. — 1994. — Т. 7. — С. 331–336. — doi:10.1137/s0895480191223191.
  9. Andreas Brandstädt, Feodor Dragan, Victor Chepoi, Vitaly Voloshin. Dually Chordal Graphs // SIAM Journal on Discrete Mathematics. — 1998. — Т. 11. — С. 437–455. — doi:10.1137/s0895480193253415.
  10. Понятие упорядочения максимального соседства не тривиально, в статье (Brandstädt, Dragan, Chepoi, Voloshin, 1998, стр. 440—442) оно занимает 2 страницы
  11. Pablo De Caria, Marisa Gutierrez. On Minimal Vertex Separators of Dually Chordal Graphs: Properties and Characterizations // Discrete Applied Mathematics. — 2012. — Т. 160. — С. 2627–2635. — doi:10.1016/j.dam.2012.02.022.
  12. Boštjan Brešar. Intersection graphs of maximal hypercubes // European Journal of Combinatorics. — 2003. — Т. = 24. — С. 195–209. — doi:10.1016/s0195-6698(02)00142-7.
  13. Marina Moscarini. Doubly Chordal Graphs, Steiner trees and connected domination // Networks. — 1993. — Т. 23. — С. 59–69. — doi:10.1002/net.3230230108.
  14. Andreas Brandstädt, Victor Chepoi, Feodor Dragan. Distance approximating trees for chordal and dually chordal graphs // Journal of Algorithms. — 1999. — Т. 30. — С. 166–184. — doi:10.1006/jagm.1998.0962.
  15. Andreas Brandstädt, Arne Leitert, Dieter Rautenbach. Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs // Lecture Notes in Computer Science. — 2012. — Т. 7676. — С. 267–277.

Литература
  • Terry A. McKee, McMorris F. R. Topics in Intersection Graph Theory. — SIAM Monographs on Discrete Mathematics and Applications, 1999.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.